这是一道很有意思的 裸题 。
首先我们可以考虑 a 和 b 的值域是固定在 0~50000之间的，当 ai < bi 时，根据题意对答案 ai+bi的贡献为 ai的个数*bi的个数
所以我们可以把值得个数记下来。（下文中的Ai表示值为a中值为i的数的个数，Bi同理，Ci为值为i的答案的个数）
考虑使用cdq分治¿
首先 对于 Ai 与 Bj ，如果 i < j，则对答案Ci+j 有Ai*Bj的贡献，对于 i > j ，则对答案Ci-j有Ai*Bj的贡献
显然，这是cdq分治的经典题目，对于算贡献，我们可以使用 fft 进行加速
(然而因为手懒使用系统的复数complex结果T到怀疑人生)
/************************************************************** Problem: 4836 User: MiEcoku Language: C++ Result: Accepted Time:3988 ms Memory:10980 kb****************************************************************/ #include#include #include #include #include using namespace std;#define fp(i, a, b) for ( register int i = (a), I = (b); i <= I; ++ i)#define mid ( l + r >> 1)#define mem(o) memset(o, 0, sizeof(o))struct cp { double x, y; cp ( double x, double y) : x(x), y(y) {} cp () {}};cp operator + (const cp &a, const cp &b) { return cp ( a.x+b.x, a.y+b.y); }cp operator - (const cp &a, const cp &b) { return cp ( a.x-b.x, a.y-b.y); }cp operator * (const cp &a, const cp &b) { return cp ( a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x); }typedef long long LL;const double pi = acos(-1);const int maxn = 200000;int rve[maxn];inline void fft(cp *a, int n, int f) { fp(i, 1, n) if( i < rve[i]) swap(a[i], a[rve[i]]); for ( int i = 1; i < n; i <<= 1) { cp wn (cos(pi/i), f*sin(pi/i)); for ( int j = 0; j < n; j += (i << 1)) { cp w (1, 0); for ( int k = 0; k < i; ++ k, w = w * wn) { cp x = a[j+k], y = w * a[j+k+i]; a[j+k] = x + y; a[j+k+i] = x - y; } } } if( f == -1) fp(i, 0, n) a[i].x /= n;}template inline void Max(T &x, const T &a) { if( a > x) x = a; return ;}//template inline void G(int &x) { x = 0; char o; for ( ; !isdigit(o = getchar()); ) ;//if( o == '-') f = -1; for ( ; isdigit(o); o = getchar()) x = (x << 1) + (x << 3) + (o & 15);}int a[maxn], b[maxn];LL C[maxn];cp t1[maxn], t2[maxn];inline void cdq(int l, int r) {// printf("%d if( l == r) { C[0] += 1LL * a[l] * b[l]; return ; } if( r - l < 200) { // 网上学的，据说可以加速很多？（雾） fp(i, l, mid) if( a[i] || b[i]) { fp(k, mid+1, r) C[i+k] += 1LL * a[i] * b[k], C[k-i] += 1LL * a[k] * b[i]; } cdq(l, mid); cdq(mid+1, r); return ; } int n = 1, len = 0; while ( n < r - l + 1) n <<= 1, ++ len; fp(i, 1, n) rve[i] = (rve[i >> 1] >> 1) | ((i&1) << len-1); fp(i, 0, n) t1[i] = cp(0,0), t2[i] = cp(0,0); fp(i, l, mid) t1[i-l].x = a[i]; fp(i, mid+1, r) t2[i-mid].x = b[i]; fft(t1, n, 1); fft(t2, n, 1); fp(i, 0, n) t1[i] = t1[i] * t2[i]; fft(t1, n, -1); fp(i, 0, r - l) C[i+l+mid] += (LL) floor (t1[i].x + 0.5); fp(i, 0, n) t1[i] = cp(0,0), t2[i] = cp(0,0); fp(i, l, mid) t2[mid-i].x = b[i]; fp(i, mid+1, r) t1[i-mid].x = a[i]; fft(t1, n, 1); fft(t2, n, 1); fp(i, 0, n) t1[i] = t1[i] * t2[i]; fft(t1, n, -1); fp(i, 1, r - l) C[i] += (LL) floor (t1[i].x + 0.5); cdq(l, mid); cdq(mid+1, r);}int T, n, m, q;int main() {#ifndef ONLINE_JUDGE freopen("1.in", "r", stdin); freopen("a.out", "w", stdout);#endif G(T); while ( T -- ) { mem(a); mem(b); mem(C); G(n); G(m); G(q); int L = 0, R = 0, x; fp(i, 1, n) G(x), ++ a[x], Max(R, x); fp(i, 1, m) G(x), ++ b[x], Max(R, x); cdq(L, R); while ( q --) G(x), printf("%lld\n", C[x]); } return 0;}
