M_sea

BZOJ4836 [Lydsy1704月赛]二元运算
BZOJ分析这题思路好奇妙啊qwq首先把$a$和$b$里的数存到桶里。现在$a_i$代表原来的$a$数组里$i$的...
扫描右侧二维码阅读全文
03
2019/01

BZOJ4836 [Lydsy1704月赛]二元运算

BZOJ

分析

这题思路好奇妙啊qwq

首先把$a$和$b$里的数存到桶里。现在$a_i$代表原来的$a$数组里$i$的个数,$b_i$同理。

现在假设我们要求$x+y$相同的,显然$ans_i=\sum\limits_{j=0}^ia_jb_{i-j}$。

这个东西显然可以用$\mathrm{FFT}$来优化。

$x-y$相同的差不多,把$b$数组翻转就行。

问题是现在还有括号里的条件,题目开始变得神仙起来qwq

考虑对值域进行分治。假如我们把值域分成了$[l,mid]$和$[mid+1,r]$两部分,可以分两种情况:

  • $x<y$,我们按上面的第一种方法来算。
  • $x>y$,我们按上面的第二种方法来算。

当$l=r$时为边界,此时的情况为$x=y$,自己贡献一下就行了。

具体时限见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;
 
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}
 
const int MAXN=100000+10;
const double PI=acos(-1.0);
 
struct Complex {
    double r,i;
    Complex(double r_=0,double i_=0) { this->r=r_,this->i=i_; }
    Complex operator +(const Complex x) { return Complex(r+x.r,i+x.i); }
    Complex operator -(const Complex x) { return Complex(r-x.r,i-x.i); }
    Complex operator *(const Complex x) { return Complex(r*x.r-i*x.i,r*x.i+i*x.r); }
};
 
int r[MAXN];
 
inline void FFT(Complex* a,int type,int n) {
    for (re int i=0;i<n;++i)
        if (i<r[i]) swap(a[i],a[r[i]]);
    for (re int i=1;i<n;i<<=1) {
        Complex rot(cos(PI/i),type*sin(PI/i));
        for (re int j=0;j<n;j+=i<<1) {
            Complex w(1,0);
            for (re int k=0;k<i;++k,w=w*rot) {
                Complex x=a[j+k],y=w*a[j+k+i];
                a[j+k]=x+y,a[j+k+i]=x-y;
            }
        }
    }
    if (type==-1)
        for (re int i=0;i<n;++i) a[i].r=(ll)(a[i].r/n+0.5);
}
 
int a[MAXN],b[MAXN];
ll ans[MAXN];
Complex f[MAXN],g[MAXN];
 
inline void solve(int L,int R) {
    if (L==R) {
        ans[0]+=1ll*a[L]*b[L];
        return;
    }
    int mid=(L+R)>>1,limit=1,l=0;
    for (;limit<=R-L+1;limit<<=1,++l);
    for (re int i=0;i<limit;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
     
    for (re int i=0;i<limit;++i) f[i]=g[i]=Complex(0,0);
    for (re int i=L;i<=mid;++i) f[i-L].r=a[i];
    for (re int i=mid+1;i<=R;++i) g[i-mid-1].r=b[i];
    FFT(f,1,limit); FFT(g,1,limit);
    for (re int i=0;i<limit;++i) f[i]=f[i]*g[i];
    FFT(f,-1,limit);
    for (re int i=0;i<=R-L+1;++i) ans[i+L+mid+1]+=(ll)(f[i].r+0.5);
 
    for (re int i=0;i<limit;++i) f[i]=g[i]=Complex(0,0);
    for (re int i=mid+1;i<=R;++i) f[i-mid-1].r=a[i];
    for (re int i=L;i<=mid;++i) g[mid-i].r=b[i];
    FFT(f,1,limit); FFT(g,1,limit);
    for (re int i=0;i<limit;++i) f[i]=f[i]*g[i];
    FFT(f,-1,limit);
    for (re int i=0;i<=R-L+1;++i) ans[i+1]+=(ll)(f[i].r+0.5);
    solve(L,mid); solve(mid+1,R);
}
 
inline void init() {
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(ans,0,sizeof(ans));
}
 
int main() {
    int T=read();
    while (T--) {
        init();
        int n=read(),m=read(),q=read();
        for (re int i=1;i<=n;++i) ++a[read()];
        for (re int i=1;i<=m;++i) ++b[read()];
        solve(0,50000);
        for (re int i=1;i<=q;++i) printf("%lld\n",ans[read()]);
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 03 : 57 PM

1 条评论

  1. smy

    tql%%%

发表评论