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

传送门

此题思路还是非常巧妙的。

考虑我们莫队的 Add 函数，本质上是往原本的区间里面加上一个数，然后算这个数的贡献。

比如说我们设 $f(x,[l,r])$ 为 $\sum _{i=l}^r [cnt(x \oplus a[i])=k]$ （中括号里面为真时，值为 1， $cnt$ 代表计算二进制里面 1 的个数）

那么我们右边界扩展到 $r$ 时，答案加上 $f(a[r],[l,r-1])$ 。

当我们能 $O(1)$ 或者 $O(\log n)$ 地算出 $f$ 时，时间复杂度正确的，但是显然在这道题里面我们不能。

考虑将 $f(x,[l,r])$ 拆成两个区间 $f(x,[1,l-1]),f(x,[1,r])$ （注意图中下标可能有点不同）

注意到 $x$ 永远为 $a[r+1]$ ，所以 $f(x,[1,r])$ 能够预处理出来。

考虑计算 $f(x,[1,l-1])$ 。

如果把莫队的移动过程画出来， $f(x,[1,l-1])$ 大概长成什么样子？

长成这个鬼样子。

考虑我们莫队的时间复杂度是如何保证？所有移动次数不超过 $O(n \sqrt n)$ ，所以我们按照左边绿色区间的长度排序，然后跑一个大暴力，统计所有绿色圆圈的值即可。

#include <bits/stdc++.h>
#define MAXN 100005
#define MAXM 16384
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int pos[MAXN],a[MAXN],cnt[MAXN],buc[MAXN],Size;
int top,stk[MAXN],sum[MAXN],Ans[MAXN];
struct Query{
    int l,r,f,id,ans;
}Q[MAXN];
inline bool operator < (const Query &a,const Query &b){
    return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&((pos[a.l]&1)?a.r<b.r:a.r>b.r));//奇偶性排序的压行写法
}
int n,m,k;
inline void Init(){
    cnt[0]=0;
    for (register int i=1;i<MAXM;++i){
        cnt[i]=cnt[i>>1]+(i&1);
        if (cnt[i]==k) stk[++top]=i;
    }
    if (cnt[0]==k) stk[++top]=0;
    Size=sqrt(n);
    for (register int i=1;i<=n;++i){
        pos[i]=(i-1)/Size+1;
    }
}
vector<Query> S[MAXN];
inline void AddQuery(int pos,int l,int r,int f,int id){
    if (pos!=0&&l<=r) S[pos].push_back(Query{l,r,f,id,0});
}
#undef int
int main(){
#define int long long
    n=read(),m=read(),k=read();
    Init();
    if (k>14){
        for (register int i=1;i<=m;++i){
            puts("0");
        }
        return 0;
    }
    for (register int i=1;i<=n;++i){
        a[i]=read();
    }
    for (register int i=1;i<=m;++i){
        int l=read(),r=read();
        Q[i]=Query{l,r,0,i,0};
    }
    sort(Q+1,Q+1+m);
    //a[i] xor a[j]==x -> a[j]=a[i] xor x
    for (register int i=1;i<=n;++i){
        for (register int j=1;j<=top;++j) buc[a[i]^stk[j]]++;
        sum[i]=buc[a[i+1]];
    }
    int l=1,r=0;
    for (register int i=1;i<=m;++i){
        AddQuery(r,l,Q[i].l-1,-1,i);
        while (l<Q[i].l) Q[i].ans+=sum[l++-1];

        AddQuery(r,Q[i].l,l-1,1,i);
        while (l>Q[i].l) Q[i].ans-=sum[--l-1];

        AddQuery(l-1,r+1,Q[i].r,-1,i);
        while (r<Q[i].r) Q[i].ans+=sum[++r-1];
        
        AddQuery(l-1,Q[i].r+1,r,1,i);
        while (r>Q[i].r) Q[i].ans-=sum[r---1];
    }
    memset(buc,0,sizeof(buc));
    for (register int i=1;i<=n;++i){
        for (register int j=1;j<=top;++j) buc[a[i]^stk[j]]++;
        for (register int p=0;p<S[i].size();++p){
            int l=S[i][p].l, r=S[i][p].r, f=S[i][p].f, id=S[i][p].id;
            for (register int j=l;j<=r;++j){
                int temp=buc[a[j]];
                if (k==0&&j<=i) temp--;
                Q[id].ans+=f*temp;
            }
        }
    }
    for (register int i=1;i<=m;++i) Q[i].ans+=Q[i-1].ans,Ans[Q[i].id]=Q[i].ans;
    for (register int i=1;i<=m;++i) printf("%lld\n",Ans[i]);
}