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

· · 题解

二次离线莫队

适用范围：

二次离线莫队，通过扫描线，再次将更新答案的过程离线处理，降低时间复杂度。假设更新答案的复杂度为O(k)，它将莫队的复杂度从O(nk\sqrt n)降到了O(nk + n\sqrt n)，大大简化了计算。 设x对区间[l..r]的贡献为\mathrm f(x,[l,r])
我们考虑区间端点变化对答案的影响： 以[l..r] 变成 [l..(r+k)]为例

\forall x \in [r+1,r+k]

求

\mathrm f(x,[l,x-1])

我们可以进行差分：

\mathrm f(x,[l,x-1])=f(x,[1,x-1])-f(x,[1,l-1])

这样转化为了一个数对一个前缀的贡献。保存下来所有这样的询问，从左到右扫描数组计算就可以了。
但是这样做，空间是O(n\sqrt n)的，不太优秀，而且时间常数巨大。。
这样的贡献分为两类：

  1. 减号左边的贡献永远是一个前缀 和它后面一个数的贡献。这可以预处理出来。
  2. 减号右边的贡献对于一次移动中所有的x来说，都是不变的。我们打标记的时候，可以只标记左右端点。
    这样，减小时间常数的同时，空间降为了O(n)级别。是一个很优秀的算法了。

例题：第十四分块（前体）

处理前缀询问的时候，我们利用异或运算的交换律，即a\ \mathrm{xor} \ b=c \Longleftrightarrow a\ \mathrm{xor}\ c=b 开一个桶t,t[i]表示当前前缀中与i异或有k个数位为1的数有多少个。 则每加入一个数a[i]，对于所有\mathrm{popcount}(x)==k的x，++t[a[i]\ \mathrm{xor}\ x]即可。

代码：
求评价码风qwq

#include <cstdio>
#include <cmath>
#include <cstdint>
#include <vector>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <utility>
#include <tuple>

using std::tuple;
using std::make_pair;
using std::vector;
using std::sort;
using std::sort;
using std::pair;
using std::get;

const int maxn=1e5+100;

int blo[maxn],a[maxn];

struct Qry
{
    int l,r,id;
    int64_t ans;
    inline bool operator< (const Qry& q){return blo[l]==blo[q.l]?r<q.r:l<q.l;}
}Q[maxn];

vector<tuple<int,int,int>> v[maxn];

int main()
{
    // freopen("data.in","r",stdin);
    // freopen("my.out","w",stdout);
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    if (k>14)
    {
        for (int i=1;i<=m;++i) puts("0");
        return 0;
    }
    for (int i=1;i<=n;++i)
        scanf("%d",a+i);
    for (int i=1;i<=m;++i)
        scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id=i;
    vector<int> buc;
    for (int i=0;i<16384;++i)
        if (__builtin_popcount(i)==k) buc.push_back(i);
    // for (auto x:buc)
    //     fprintf(stderr,"%d ",x);
    int T=sqrt(n);
    for (int i=1;i<=n;++i) blo[i]=(i-1)/T+1;
    sort(Q+1,Q+m+1);

     /***************/
     /*  L右移：l正r负 *\
     /*  l左移：l负r正 *\
     /*  r右移：r正l负 *\
     /*  r左移：r负l正 *\
     /***************/
    static int t[maxn];
    static int pref[maxn];
    for (int i=1;i<=n;++i)
    {
        for (auto x:buc) ++t[a[i]^x];
        pref[i]=t[a[i+1]];
    }
    memset(t,0,sizeof(t));
    // 预处理前缀贡献
    for (int i=1,L=1,R=0;i<=m;++i)
    {
        int l=Q[i].l,r=Q[i].r;
        if (L<l) v[R].emplace_back(L,l-1,-i);
        while (L<l) {Q[i].ans+=pref[L-1];++L;} 
        if (L>l) v[R].emplace_back(l,L-1,i);
        while (L>l) {Q[i].ans-=pref[L-2];--L;}
        if (R<r) v[L-1].emplace_back(R+1,r,-i);
        while (R<r) {Q[i].ans+=pref[R];++R;}
        if (R>r) v[L-1].emplace_back(r+1,R,i);
        while (R>r) {Q[i].ans-=pref[R-1];--R;}
    }
    //模拟莫队，算出来第一类贡献，对第二类贡献打上标记
    static int64_t ans[maxn];
    for (int i=1,id,l,r;i<=n;++i)
    {
        for (auto x:buc) ++t[a[i]^x];
        for (const auto& x:v[i])
        {
            std::tie(l,r,id)=x;
            // if (i>=l) fprintf(stderr,"%d %d\n",i,l);
            for (int j=l,tmp=0;j<=r;++j)
            {
                tmp=t[a[j]];
                if (j<=i && k==0) --tmp;// 这里（按我的蒟蒻写法）k==0的时候需要特判，因为x^x永远是0，但自己对自己不能产生贡献。
                if (id<0) Q[-id].ans-=tmp;
                else Q[id].ans+=tmp;
            }
        }
    }
    for (int i=1;i<=m;++i) Q[i].ans+=Q[i-1].ans;
    for (int i=1;i<=m;++i) ans[Q[i].id]=Q[i].ans;
    for (int i=1;i<=m;++i) printf("%lld\n",ans[i]);
}