题解 P4887 【模板】莫队二次离线（第十四分块(前体)）

· · 题解

题面传送门

莫队二次离线 mol ban tea，大概是这道题让我第一次听说有这东西？

首先看到这类数数对的问题可以考虑莫队，记 S 为二进制下有 k 个 1 的数集，我们实时维护一个桶 cnt_i 表示当前区间中值为 i 的数有多少个，那么加入一个数 v 的时候，答案会增加 \sum\limits_{y\in S}cnt_{y\oplus v}，这样暴力莫队复杂度是 n\sqrt{n}\dbinom{14}{k}，如果你过了我请你吃糖

考虑优化，我们记 f(x,l,r) 表示当前区间为 [l,r]，加入 a_x 后答案的增量，记 \sum\limits_{y\in S}cnt_{y\oplus a_x}。考虑莫队中每个端点的移动对答案的贡献，我们以右端点为例，设右端点由 r 移动到了 r'，这里我们不妨设 r'>r，r'<r 的情况也同理，那么答案显然会增加 \sum\limits_{i=r+1}^{r'}f(i,l,i-1)，这东西不太好直接求，考虑用差分的思想，将这东西拆成 f(i,1,i-1)-f(i,1,l-1)，那么 \Delta=\sum\limits_{i=r+1}^{r'}f(i,1,i-1)-\sum\limits_{i=r+1}^{r'}f(i,1,l-1)，不难发现第一个 \sum 里的东西只与 i 有关，我们可以预处理 f(i,1,i-1) 的前缀和即可 \mathcal O(1) 求出，至于怎么求 f(i,1,i-1)……这个看不出来就有点【数据删除】了罢，就从左往右扫一遍并实时维护一个桶 cnt，扫到 a_i 的时候 f(i,1,i-1) 的值就是当时 \sum\limits_{x\in S}cnt_{x\oplus a_i}。后面那坨东西在线求出不太容易，不过既然叫“莫队二次离线”那就离线一下呗，不难发现所有这样的东西都可以用一个三元组 (x,l,r) 表示 \sum\limits_{i=l}^rf(i,1,x)，我们将这样的询问都挂在 x 上然后从左往右扫描一遍，还是实时维护一个桶 cnt，不过这时候 cnt_v 的含义为 [1,i] 中有多少个数 j 满足 v\oplus a_j\in S，这显然可以在 \mathcal O(n\dbinom{14}{k}) 的时间内求出，然后每遇到一个询问 (i,l,r)，就暴力枚举 t\in[l,r] 并令贡献加上/减去 cnt_{a_t}，由于莫队指针移动的总距离为 n\sqrt{n} 级别的，因此这里的 \sum r-l+1 也是 n\sqrt{n} 级别的，可以通过。

上文所叙述的都是右端点移动的情况，左端点移动的情况大体上也差不多，还是设左端点由 l 移动到了 l'，l'<l那么答案的增量就是 \sum\limits_{i=l'}^{l-1}f(i,i+1,r)，这里有一个小小的区别就是不能差分前缀和，而要差分后缀和，即 f(i,i+1,r)=f(i,i+1,n)-f(i,r+1,n)，这两项都可以用类似的方式维护。

最后，由于我们求出的是每次莫队后答案的增量，还需对每次询问的结果求一遍前缀和即可得到每次询问真正的答案。

时间复杂度 n\sqrt{n}+n\dbinom{14}{k}

const int MAXN=1e5;
const int MAXV=1<<14;
int n,qu,k,a[MAXN+5],blk_sz,blk_cnt;
int bel[MAXN+5],L[MAXN+5],R[MAXN+5];
ll pre[MAXN+5],suf[MAXN+5],anss[MAXN+5];
int buc[MAXV+5];
struct query{
    int l,r,id;ll ans;
    bool operator <(const query &rhs) const{
        if(bel[l]^bel[rhs.l]) return bel[l]<bel[rhs.l];
        else if(bel[l]&1) return r<rhs.r;
        else return r>rhs.r;
    }
} q[MAXN+5];
struct qwq{int l,r,id,op;};
vector<qwq> vl[MAXN+5],vr[MAXN+5];
int main(){
    scanf("%d%d%d",&n,&qu,&k);vector<int> v;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=0;i<MAXV;i++) if(__builtin_popcount(i)==k) v.pb(i);
    blk_sz=(int)pow(n,0.5);blk_cnt=(n-1)/blk_sz+1;
    for(int i=1;i<=blk_cnt;i++){
        L[i]=(i-1)*blk_sz+1;R[i]=min(i*blk_sz,n);
        for(int j=L[i];j<=R[i];j++) bel[j]=i;
    }
    for(int i=1;i<=qu;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
    sort(q+1,q+qu+1);int cl=1,cr=0;
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1];
        for(int j:v) pre[i]+=buc[j^a[i]];
        buc[a[i]]++;
    } memset(buc,0,sizeof(buc));
    for(int i=n;i;i--){
        suf[i]=suf[i+1];
        for(int j:v) suf[i]+=buc[j^a[i]];
        buc[a[i]]++;
    }
    for(int i=1;i<=qu;i++){
        q[i].ans=pre[q[i].r]-pre[cr]+suf[q[i].l]-suf[cl];
        if(cl<q[i].l) vr[cr+1].pb({cl,q[i].l-1,i,1});
        if(cl>q[i].l) vr[cr+1].pb({q[i].l,cl-1,i,-1});
        if(cr<q[i].r) vl[q[i].l-1].pb({cr+1,q[i].r,i,-1});
        if(cr>q[i].r) vl[q[i].l-1].pb({q[i].r+1,cr,i,1});
        cl=q[i].l;cr=q[i].r;
    } memset(buc,0,sizeof(buc));
    for(int i=1;i<=n;i++){
        for(int j:v) buc[a[i]^j]++;
        for(int j=0;j<vl[i].size();j++){
            int l=vl[i][j].l,r=vl[i][j].r,id=vl[i][j].id;
            ll sum=0;for(int t=l;t<=r;t++) sum+=buc[a[t]];
            q[id].ans+=sum*vl[i][j].op;
        }
    } memset(buc,0,sizeof(buc));
    for(int i=n;i;i--){
        for(int j:v) buc[a[i]^j]++;
        for(int j=0;j<vr[i].size();j++){
            int l=vr[i][j].l,r=vr[i][j].r,id=vr[i][j].id;
            ll sum=0;for(int t=l;t<=r;t++) sum+=buc[a[t]];
            q[id].ans+=sum*vr[i][j].op;
        }
    }
    for(int i=2;i<=qu;i++) q[i].ans+=q[i-1].ans;
    for(int i=1;i<=qu;i++) anss[q[i].id]=q[i].ans;
    for(int i=1;i<=qu;i++) printf("%lld\n",anss[i]);
    return 0;
}
/*
6 1 0
1 2 3 1 2 3
1 6

6 5 1
1 2 3 4 5 6
1 5
1 6
2 5
2 6
3 6

14 5 1
1 2 3 4 5 6 7 1 2 3 4 5 6 7
1 14
2 13
3 9
1 12
4 11
*/