莫队二次离线

· · 题解

前言

众所周知，莫队是一种可爱的离线算法，它的时间复杂度为 O(n\sqrt m\,f(x))，f(x) 为挪指针时更新答案复杂度，当 f(x)=O(1) 时，我们可以接受，但 f(x)=O(\log n) 甚至更大时，我们可能就无法接受了，而莫队二次离线可以让复杂度降到我们能接受的范围内——O(n\sqrt m+n\,f(x))。

适用范围：

实现

考虑在挪指针时对答案产生了哪些贡献，下文的 f(x,l,r) 表示 a_x 对 [l,r] 的贡献，F(x,l)=f(x,1,l)。

在右指针移动到 x 时，会产生的答案变动为 f(x,l,x-1)=F(x,x-1)-F(x,l-1) ；

在左指针移动到 x 时，会产生的答案变动为 f(x,x+1,r)=F(x,r)-F(x,x)。

我们注意到，F(x,x-1)，-F(x,x) 是可以预处理的，莫队时直接 O(1) 修改答案即可，而且一般情况下 F(x,x-1)=F(x,x)，毕竟一个数一般不会对自己有贡献，可以偷个懒。

莫队的指针移动是连续的，也就是说，在上面式子中的 -F(x,l-1) 和 F(x,r) 部分单独计算实际上是形如 -F(a,l-1)-F(a+1,l-1)-F(a+2,l-1)-\cdots-F(k,l-1) 和 F(a,r)+F(a-1,r)+F(a-2,r)+\cdots+F(k,r) 的，那么我们可以使用五元组 (a,k,l-1,-1,i) 和 (a,k,r,1,i) 将这些移动产生的贡献存下来，i 表示该移动在哪个询问期间发生，在莫队结束后使用扫描线处理，不懂没关系，看下代码（养成好习惯，两个指针的移动顺序不要写错）：

for(int i=1,l=1,r=0;i<=m;i++){
    if(l>q[i].l) v[r].emplace_back(q[i].l,l-1,i,1);
    while(l>q[i].l) --l,q[i].ans-=p[l];
    if(r<q[i].r) v[l-1].emplace_back(r+1,q[i].r,i,-1);
    while(r<q[i].r) ++r,q[i].ans+=p[r];
    if(l<q[i].l) v[r].emplace_back(l,q[i].l-1,i,-1);
    while(l<q[i].l) q[i].ans+=p[l],++l;
    if(r>q[i].r) v[l-1].emplace_back(q[i].r+1,r,i,1);
    while(r>q[i].r) q[i].ans-=p[r],--r;
}

这样还有最后一个问题，我们会发现一个指针在询问 i 处的移动会对询问 [i,m] 产生贡献，也就是说，我们得到的答案其实是差分的形式，需要求前缀和才能得到真正的答案。

UPD: 这里给出一个常数优化，p 数组可以用前缀和优化

for(int i=1,l=1,r=0;i<=m;i++)
        if(l>q[i].l) v[r].emplace_back(q[i].l,l-1,q[i].id,1),ans[q[i].id]-=p[l-1]-p[q[i].l-1],l=q[i].l;
        if(r<q[i].r) v[l-1].emplace_back(r+1,q[i].r,q[i].id,-1),ans[q[i].id]+=p[q[i].r]-p[r],r=q[i].r;
        if(l<q[i].l) v[r].emplace_back(l,q[i].l-1,q[i].id,-1),ans[q[i].id]+=p[q[i].l-1]-p[l-1],l=q[i].l;
        if(r>q[i].r) v[l-1].emplace_back(q[i].r+1,r,q[i].id,1),ans[q[i].id]-=p[r]-p[q[i].r],r=q[i].r;
    }

关于本题

我们预处理出所有有 k 个 1 的数，利用异或的性质 a\oplus b=c\leftrightarrow b=a\oplus c 即可得到答案。

代码

这里给出 P4887 的代码：

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
#include<tuple>
int n,m,k,bel[100010],sz,a[100010],t[100010],p[100010];
struct query{
    int l,r,id;
    long long ans;
    bool operator <(query const &x)const{
        return bel[l]==bel[x.l]?r<x.r:l<x.l;
    }
}q[100010];
std::vector<int> b;
std::vector<std::tuple<int,int,int,int>>v[100010];
long long ans[100010];
int bitcount(unsigned x){
    int ans(0);
    while(x)x-=x&-x,++ans;
    return ans;
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    if(k>14){
        for(int i=1;i<=m;i++)puts("0");
        return 0;
    }
    sz=n/sqrt(m);//莫队的正确块长，比sqrt(n)要快很多
    for(int i=1;i<=n;i++)scanf("%d",a+i),bel[i]=(i-1)/sz+1;
    for(int i=1;i<=m;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
    for(int i=0;i<16384;i++)
        if(bitcount(i)==k)
            b.push_back(i);
    std::sort(q+1,q+m+1);
    for(int i=1;i<=n;i++){//预处理
        p[i]=t[a[i]];
        for(const auto& x:b)++t[a[i]^x];
    }
    memset(t,0,sizeof(t));
    for(int i=1,l=1,r=0;i<=m;i++){//莫队
        if(l>q[i].l) v[r].emplace_back(q[i].l,l-1,i,1);
        while(l>q[i].l) --l,q[i].ans-=p[l];
        if(r<q[i].r) v[l-1].emplace_back(r+1,q[i].r,i,-1);
        while(r<q[i].r) ++r,q[i].ans+=p[r];
        if(l<q[i].l) v[r].emplace_back(l,q[i].l-1,i,-1);
        while(l<q[i].l) q[i].ans+=p[l],++l;
        if(r>q[i].r) v[l-1].emplace_back(q[i].r+1,r,i,1);
        while(r>q[i].r) q[i].ans-=p[r],--r;
    }
    for(int i=1;i<=n;i++){//扫描线
        for(const auto& x:b)++t[a[i]^x];
        for(const auto& x:v[i]){
            for(int j=std::get<0>(x);j<=std::get<1>(x);j++){
                if(j<=i&&k==0) q[std::get<2>(x)].ans+=std::get<3>(x)*(t[a[j]]-1);
                else q[std::get<2>(x)].ans+=std::get<3>(x)*t[a[j]];
            }
        }
    }
    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]);
    return 0;
}

习题

P4887

P5047

P5501