题意：给定两个长度为n的数组a与长度为m的数组b, 给定一个操作符op满足 x op y = x < y ? x+y : x-y. 有q个询问，每次给出询问c，问：有多少对(i, j)满足a[i] op b[j] = c ？
0 <= c <= 100000, 其余数据范围在[0, 50000].
题解：问题的关键在于如何分隔开 x < y与x >= y. cdq分治，合并的时候a[l, mid]与b[mid+1, r]卷积一次计算a[] < b[] ， a[mid+1, r]与b[l, mid]再卷积一次a[] > b[]即可。
卡时，memset的时候优化了一下。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5+;
struct comp{
double r,i;comp(double _r=,double _i=){r=_r;i=_i;}
comp operator+(const comp x){return comp(r+x.r,i+x.i);}
comp operator-(const comp x){return comp(r-x.r,i-x.i);}
comp operator*(const comp x){return comp(r*x.r-i*x.i,r*x.i+i*x.r);}
}x[N<<], y[N<<];
const double pi=acos(-1.0);
void FFT(comp a[],int n,int t){
for(int i=,j=;i<n-;i++){
for(int s=n;j^=s>>=,~j&s;);
if(i<j)swap(a[i],a[j]);
}
for(int d=;(<<d)<n;d++){
int m=<<d,m2=m<<;
double o=pi/m*t;comp _w(cos(o),sin(o));
for(int i=;i<n;i+=m2){
comp w(,);
for(int j=;j<m;j++){
comp &A=a[i+j+m],&B=a[i+j],t=w*A;
A=B-t;B=B+t;w=w*_w;
}
}
}
if(t==-)for(int i=;i<n;i++)a[i].r/=n;
}
int a[N], b[N], n, m, q;
ll ans[N];
void cdq(int l, int r){
if(l == r){
ans[] += a[l]*b[l];
return;
}
int mid = l+r >> ;
cdq(l, mid);
int len = ;
while(len <= (r-l+)) len <<= ;
memset(x, , sizeof(comp)*len );
memset(y, , sizeof(comp)*len );
for(int i = l; i <= mid; i++)
x[i-l] = comp(a[i], );
for(int i = mid+; i <= r; i++)
y[i-mid-] = comp(b[i], );
FFT(x, len, ); FFT(y, len, );
for(int i = ; i < len; i++)
x[i] = x[i]*y[i];
FFT(x, len, -);
for(int i = l+mid+; i <= mid+r; i++)
ans[i] += x[i-l-mid-].r+0.5;
for(int i = ; i < len; i++)
x[i] = y[i] = comp(, );
for(int i = mid+; i <= r; i++)
x[i-mid-] = comp(a[i], );
for(int i = l; i <= mid; i++)
y[mid+-i] = comp(b[i], );
FFT(x, len, ); FFT(y, len, );
for(int i = ; i < len; i++)
x[i] = x[i]*y[i];
FFT(x, len, -);
for(int i = ; i <= r-l; i++)
ans[i] += x[i].r+0.5;
cdq(mid+, r);
} int main(){
int t, x, maxn; scanf("%d", &t);
while(t--){
scanf("%d%d%d", &n, &m, &q);
maxn = ;
for(int i = ; i < n; i++){
scanf("%d", &x);
maxn = max(maxn, x);
a[x]++;
}
for(int i = ; i < m; i++){
scanf("%d", &x);
maxn = max(maxn, x);
b[x]++;
}
cdq(, maxn);
while(q--){
scanf("%d", &x);
printf("%lld\n", ans[x]);
}
memset(a, , sizeof(int)*(maxn+));
memset(b, , sizeof(int)*(maxn+));
memset(ans, , sizeof(ll)*(maxn*+));
}
return ;
}