BZOJ4836: [Lydsy1704月赛]二元运算

https://lydsy.com/JudgeOnline/problem.php?id=4836

分析:

分开做，维护两个桶。
分治每次求\([l,mid]\)和\([mid+1,r]\)的贡献。
两次\(fft\)即可。

代码:

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef double f2;

const f2 pi=acos(-1);

typedef long long ll;

#define N 400050

int n,m,q,C[50050],D[50050];

ll ans[100050];

struct cp {

	f2 x,y;

	cp() {}

	cp(f2 x_,f2 y_) {x=x_,y=y_;}

	cp operator + (const cp &u) const {

		return cp(x+u.x, y+u.y);

	}

	cp operator - (const cp &u) const {

		return cp(x-u.x, y-u.y);

	}

	cp operator * (const cp &u) const {

		return cp(x*u.x-y*u.y, x*u.y+y*u.x);

	}

}a[N],b[N];

void fft(cp *a,int len,int flg) {

	int i,j,k,t;

	cp w,wn,tmp;

	for(i=k=0;i<len;i++) {

		if(i>k) swap(a[i],a[k]);

		for(j=len>>1;(k^=j)<j;j>>=1) ;

	}

	for(k=2;k<=len;k<<=1) {

		t=k>>1;

		wn=cp(cos(2*pi*flg/k),sin(2*pi*flg/k));

		for(i=0;i<len;i+=k) {

			w=cp(1,0);

			for(j=i;j<i+t;j++) {

				tmp=a[j+t]*w;

				a[j+t]=a[j]-tmp;

				a[j]=a[j]+tmp;

				w=w*wn;

			}

		}

	}

	if(flg==-1) {

		for(i=0;i<=len;i++) a[i].x/=len;

	}

}

void solve(int l,int r) {

	if(l==r) return ;

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

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

	int i,n=mid-l+1,m=r-mid;

	int len=1;

	while(len<=(n+m)) len<<=1;

	for(i=0;i<n;i++) a[i].x=C[l+i];

	for(i=0;i<m;i++) b[i].x=D[mid+i+1];

	fft(a,len,1), fft(b,len,1);

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

	fft(a,len,-1);

	for(i=0;i<n+m;i++) {

		ans[l+mid+i+1]+=ll(a[i].x+0.5);

	}

	for(i=0;i<len;i++) a[i]=b[i]=cp(0,0);

	int t=0;

	for(i=mid;i>=l;i--) a[t++].x=D[i];

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

	fft(a,len,1), fft(b,len,1);

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

	fft(a,len,-1);

	for(i=1;i<=r-l;i++) {

		ans[i]+=ll(a[i-1].x+0.5);

	}

	for(i=0;i<len;i++) a[i]=b[i]=cp(0,0);

}

int main() {

	int T;

	scanf("%d",&T);

	while(T--) {

		memset(C,0,sizeof(C));

		memset(D,0,sizeof(D));

		memset(ans,0,sizeof(ans));

		scanf("%d%d%d",&n,&m,&q);

		int i,x;

		for(i=1;i<=n;i++) scanf("%d",&x),C[x]++;

		for(i=1;i<=m;i++) scanf("%d",&x),D[x]++;

		for(i=0;i<=50000;i++) {

			ans[0]+=ll(C[i])*D[i];

		}

		solve(0,50000);

		while(q--) {

			scanf("%d",&x);

			printf("%lld\n",ans[x]);

		}

	}

}

巴特西

BZOJ4836: [Lydsy1704月赛]二元运算

BZOJ4836: [Lydsy1704月赛]二元运算

最新文章

热门文章