bzoj 4836: 二元运算

时间：2024-03-28 19:07:26

死活TLE....求助

update 4.3 23:08 求助了tls之后终于过了...分治里次数界写崩了...r-l+1就行...

分治的做法很神奇！本题的限制在于操作类型与权值相对大小有关，而用[l,mid]更新[mid+1,r]正好适应了本题的要求

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N = (1<<17) + 5;

const double PI = acos(-1.0);

inline int read() {

	char c=getchar();int x=0,f=1;

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

	return x*f;

}

struct meow{

	double x, y;

	meow(double x=0, double y=0):x(x), y(y){}

};

meow operator + (meow a, meow b) {return meow(a.x + b.x, a.y + b.y);}

meow operator - (meow a, meow b) {return meow(a.x - b.x, a.y - b.y);}

meow operator * (meow a, meow b) {return meow(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);}

meow conj(meow a) {return meow(a.x, -a.y);}

typedef meow cd;

namespace fft {

	int maxlen = 1<<17, rev[N];

	cd omega[N], omegaInv[N];

	void init() {

		for(int i=0; i<maxlen; i++) {

			omega[i] = cd(cos(2*PI/maxlen*i), sin(2*PI/maxlen*i));

			omegaInv[i] = conj(omega[i]);

		}

	}

	void dft(cd *a, int n, int flag) {

		cd *w = flag == 1 ? omega : omegaInv;

		for(int i=0; i<n; i++) if(i < rev[i]) swap(a[i], a[rev[i]]);

		for(int l=2; l<=n; l<<=1) {

			int m = l>>1;

			for(cd *p = a; p != a+n; p += l)

				for(int k=0; k<m; k++) {

					cd t = w[maxlen/l*k] * p[k+m];

					p[k+m] = p[k] - t;

					p[k] = p[k] + t;

				}

		}

		if(flag == -1) for(int i=0; i<n; i++) a[i].x /= n;

	}

	void mul(cd *a, cd *b, int n) {

		int k = 0; while((1<<k) < n) k++;

		for(int i=0; i<n; i++) rev[i] = (rev[i>>1]>>1) | ((i&1)<<(k-1));

		dft(a, n, 1); dft(b, n, 1);

		for(int i=0; i<n; i++) a[i] = a[i] * b[i];

		dft(a, n, -1);

	}

}

cd f[N], g[N];

int n, m, Q, a[N], b[N]; ll c[N];

void cdq(int l, int r) {

	if(l == r) {c[0] += (ll) a[l] * b[l]; return;} 

	int mid = (l+r)>>1;

	int n = 1, lim = r-l+1;

	if(r-l < 200) {

		for(int i=l; i<=mid; i++) if(a[i] || b[i])

			for(int j=mid+1; j<=r; j++) c[i+j] += (ll) a[i] * b[j], c[j-i] += (ll) a[j] * b[i];

	} else {

		while(n < lim) n<<=1;

		for(int i=0; i<n; i++) f[i] = g[i] = cd();

		for(int i=l; i<=mid; i++) f[i-l].x += a[i];

		for(int i=mid+1; i<=r; i++) g[i-mid].x += b[i];

		fft::mul(f, g, n);

		for(int i=0; i<lim; i++) c[i+l+mid] += (ll) floor(f[i].x + 0.5);

		for(int i=0; i<n; i++) f[i] = g[i] = cd();

		for(int i=mid+1; i<=r; i++) f[i-mid].x += a[i];

		for(int i=l; i<=mid; i++) g[mid-i].x += b[i];

		fft::mul(f, g, n);

		for(int i=0; i<lim; i++) c[i] += (ll) floor(f[i].x + 0.5);

	}

	cdq(l, mid); cdq(mid+1, r);

}

int main() {

	//freopen("in", "r", stdin);

	int T=read();

	fft::init();

	while(T--) {

		n=read(); m=read(); Q=read();

		int l=0, r=0, x;

		memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); memset(c, 0, sizeof(c));

		for(int i=1; i<=n; i++) x=read(), a[x]++, r = max(r, x);

		for(int i=1; i<=m; i++) x=read(), b[x]++, r = max(r, x);

		cdq(l, r);

		while(Q--) printf("%lld\n", c[read()]);

	}

}

相关文章