自动搬运

查看原文

来自洛谷，原作者为

	_WA自动机 这个家伙什么也不是

搬运于2025-08-24 22:04:56，当前版本为作者最后更新于2019-06-20 12:13:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

二次离线莫队

适用范围：

• 可以莫队
• 更新答案的时间不是O(1)（一个数对答案的贡献与区间中别的数有关，例如比一个数小的数有多少）

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

求

我们可以进行差分：

这样转化为了一个数对一个前缀的贡献。保存下来所有这样的询问，从左到右扫描数组计算就可以了。
但是这样做，空间是$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]);
}