[noi simulation] interval distance (block and convolution)

Topic

5s , 512mb

Answer key

Do this question , First, be bold .

We can divide it into pieces , Calculation $a$ Each block is associated with $b$ The result of each suffix match ：$a$ The five values of are considered separately , Set the value of the current enumeration to $d$ , Calculate each $|b_i-d|$ , take $a$ Medium is equal to $d$ Fu Wei of 1, Otherwise 0, And then $b$ Flip and $a$ Convolute each block of .

We use it $sum[i][j]$ Express $a$ From $i$ The beginning of a block to $n$ And $b$ The suffix $j$ Matching answers , When you ask, you have to make a difference , Just check the pieces again .

Let the value range be $D$ （$D=5$）, Block size is $B$, The time complexity is $O(Dn\cdot \frac{n}{B}\log n+qB)$ , You can't pass the card ！

Consider how to put this $D$ Get rid of .

Five cases $b$ The polynomial point value expression can be preprocessed , The point value expression after convolution in five cases of each block can not be busy with inverse transformation first , Add it all up and reverse it .

At this time, the trouble is the initial polynomial of each block in five cases , It seems that you have to change it once . But we find that the length of the polynomial is only $O(B)$ , in other words ,$B$ The following positions are 0, After bitwise flipping , Beginning with a non-zero position $\log B$ It's a place to have 1, do $NTT$ It's easy to Chakra . Let's skip the empty part , This part of the complexity can reach $O((1+\epsilon )n)$ .

So the complexity will be $O(n\cdot \frac{n}{B}\log n+qB)$ .

CODE

It just skips a lot of modulo taking in this way , It just reduces the constant , still $O(Dn\cdot \frac{n}{B}\log n+qB)$ Code for .

Block long open $1345$ .

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<random>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#pragma GCC optimize(2)
using namespace std;
#define MAXN 100005
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define SQ 1345
int xchar() {
    
	static const int maxn = 1000000;
	static char b[maxn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
#define getchar() xchar()
LL read() {
    
	LL f = 1,x = 0;int s = getchar();
	while(s < '0' || s > '9') {
    if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
	while(s >= '0' && s <= '9') {
    x = (x<<1) + (x<<3) + (s^48);s = getchar();}
	return f*x;
}
void putpos(LL x) {
    if(!x)return ;putpos(x/10);putchar((x%10)^48);}
void putnum(LL x) {
    
	if(!x) {
    putchar('0');return ;}
	if(x<0) putchar('-'),x = -x;
	return putpos(x);
}
void AIput(LL x,int c) {
    putnum(x);putchar(c);}

const int MOD = 998244353;
int n,m,s,o,k;
inline int qkpow(int a,int b) {
    
	int res = 1;
	while(b > 0) {
    
		if(b & 1) res = res*1ll*a % MOD;
		a = a *1ll* a % MOD; b >>= 1;
	}return res;
}
inline int Abs(int x) {
    return x<0 ? -x:x;}
int a[MAXN],b[MAXN];
int bel[MAXN],bl[MAXN],br[MAXN];
int xm[MAXN<<2],om,rev[MAXN<<2];
LL v;
void initn(int n) {
    
	for(int i = 1;i < n;i ++) {
    
		rev[i] = (rev[i>>1]>>1) | ((i&1) ? (n>>1):0);
	} om = qkpow(3,(MOD-1)/n); xm[0] = 1;
	for(int i = 1;i <= n;i ++) xm[i] = xm[i-1]*1ll*om % MOD;
	v = qkpow(n,MOD-2); return ;
}
void NTT(int *s,int n,int op) {
    
	for(int i = 1;i < n;i ++) {
    
		if(rev[i] < i) swap(s[rev[i]],s[i]);
	}
	for(int k = 2,t = n>>1;k <= n;k <<= 1,t >>= 1) {
    
		for(int j = 0;j < n;j += k) {
    
			for(int i = j,l = 0;i < j+(k>>1);i ++,l += t) {
    
				int A = s[i],B = s[i+(k>>1)];
				if(!(A|B)) continue; //  Omit the modulo key statement ！！！
				s[i] = (A + xm[op < 0 ? n-l:l]*1ll*B) % MOD;
				s[i+(k>>1)] = (A +MOD- xm[op < 0 ? n-l:l]*1ll*B % MOD) % MOD;
			}
		}
	}
	if(op < 0) {
    
		for(int i = 0;i < n;i ++) s[i] = s[i] * v % MOD;
	} return ;
}
int A[MAXN<<2],B[5][MAXN<<2],C[MAXN<<2];
int sm[MAXN/SQ+5][MAXN+SQ];
int que(int s,int o) {
    
	if(s > n || o > n) return 0;
	int B = bel[s],le = s-bl[B];
	if(o-le < 1) {
    
		le -= br[B]-bl[B]+1;
		B ++; int as = sm[B][o-le];
	// printf("as: %d",as);
		for(int i = s,j = o;i <= br[B-1] && j <= n;i ++,j ++) as += Abs(a[i]-b[j]);
	// printf("->%d ",as);
		return as;
	}
	int as = sm[B][o-le];
	// printf("(%d,%d)as: %d",as,B,o-le);
	for(int i = bl[B],j = o-le;i < s && j <= n;i ++,j ++) as -= Abs(a[i]-b[j]);
	// printf("->%d ",as);
	return as;
}
int main() {
    
	freopen("dist.in","r",stdin);
	freopen("dist.out","w",stdout);
	n = read();m = read();
	for(int i = 1;i <= n;i ++) {
    
		a[i] = read();
		int B = i/SQ+1; bel[i] = B;
		if(!bl[B]) bl[B] = i;
		br[B] = i;
	}
	for(int i = 1;i <= n;i ++) {
    
		b[i] = read();
	}
	int le = 1;while(le <= n+SQ) le <<= 1;
	initn(le);
	for(int d = 1;d <= 5;d ++) {
    
		for(int i = 0;i < le;i ++) B[d-1][i] = 0;
		for(int i = 1;i <= n;i ++) B[d-1][n-i] = Abs(d-b[i]);
		NTT(B[d-1],le,1);
	}
	for(int i = 1;i <= bel[n];i ++) {
    
		for(int j = 0;j < le;j ++) C[j] = 0;
		for(int d = 1;d <= 5;d ++) {
    
			int st = bl[i],sz = br[i]-bl[i]+1;
			for(int j = 0;j < le;j ++) A[j] = 0;
			for(int j = 0;j < sz;j ++) A[j] = (a[st+j] == d ? 1:0);
			NTT(A,le,1);
			for(int j = 0;j < le;j ++) C[j] = (C[j] + A[j] *1ll* B[d-1][j]) % MOD;
		}
		NTT(C,le,-1);
		for(int j = 1;j <= n;j ++) sm[i][j] += C[n-j];
	}
	for(int i = bel[n]-1;i > 0;i --) {
    
		int nm = bl[i+1] - bl[i];
		for(int j = 1;j+nm <= n;j ++) sm[i][j] += sm[i+1][j+nm];
	}
	for(int i = 1;i <= m;i ++) {
    
		s = read();o = read();k = read();
		int s2 = s+k,o2 = o+k;
		AIput(que(s,o) - que(s2,o2),'\n');
	}
	return 0;
}