根号算法

zzy0618 · 2024-12-08 19:59:21 · 算法·理论

一、分块

我们发现，如果一片区域被完全覆盖，我们可以对这个整块打上标记，而如果没有完全覆盖，我们只能挨个加。设我们将序列平均分成了 B 块，对完全覆盖的整块我们最多做 O(B) 次打标记。对没有完全覆盖的部分，发现只有两端要暴力做，所以是 O(\frac{N}{B}) 级别的，最终复杂度为 O(B+\frac{N}{B}) 可以发现，当 B=\sqrt N 时最小，于是我们可以在 O(\sqrt N) 的复杂度完成区间修改，区间查询。

虽然这没有线段树快，但其能维护更复杂的信息，并且单点修改是 O(1) 级别，这将与后文的莫队很好地结合。

二、根号分治

CF797E Array Queries

给出数组 a ，对此询问 k,p，求至少经过多少次 p\gets p+a_p+k 才能使得 p>n。

可以发现，如果暴力跳是 O(n) 的，等等，不要这么粗略的分析复杂度，实际是 O(\frac{n}{k}) 级别，如果我们对于 k\ge B 的暴力跳，复杂度是 O(\frac n B)。如果存储答案呢？设我们存储了 k\le B 的答案，我们的复杂度为 O(nB) 级别。模仿分块的思想，取 B=\sqrt n，分别进行两种操作，便可得到 O(n\sqrt n) 的解法。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,sqn,a[N];
int dp[N][320];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;sqn=sqrt(n);
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=n;i>=1;--i){
        for(int j=1;j<=sqn;++j){
            if(i+a[i]+j>n)dp[i][j]=1;
            else dp[i][j]=dp[i+a[i]+j][j]+1;
        }
    }cin>>m;
    while(m--){
        int p,k,ans=0;cin>>p>>k;
        if(k<=sqn){
            cout<<dp[p][k]<<'\n';
        }
        else{
            while(p<=n)p+=a[p]+k,++ans;
            cout<<ans<<'\n';
        }
    }
    return 0;
}

CF1580C Train Maintenance

比较明显的根号分治。如果 x_i+y_i>\sqrt n，直接暴力差分添加。对于 x_i+y_i\le \sqrt n，开一个桶 f_{a,b} 表示 x_i+y_i=a，在这个长度为 a 的周期中，第 b 天有多少车在维修。那么第 i 天，f_{a,i\bmod a} 是有贡献的。值得注意的是，维护差分数组的删除时，由于有点差分数组已经经过前缀和了。对于以前的一个位置 j 的贡献如果要删除，应该算到 i 上。

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,sqn,x[N],y[N];
int las[N],b[N],st[500][500];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;sqn=sqrt(n);
    for(int i=1;i<=n;++i)
        cin>>x[i]>>y[i];
    for(int i=1,op,p,ans;i<=m;++i){
        ans=0;cin>>op>>p;
        int z=x[p]+y[p];
        if(op==1){
            las[p]=i;
            if(z<=sqn)
                for(int j=0;j<z;++j)st[z][(i+j)%z]+=(j>=x[p]);
            else
                for(int j=i+x[p];j<=m;j+=z)++b[j],--b[min(m+1,j+y[p])];
        }
        else{
            if(z<=sqn)
                for(int j=0;j<z;++j)st[z][(las[p]+j)%z]-=(j>=x[p]);
            else
                for(int j=las[p]+x[p];j<=m;j+=z)--b[max(i,j)],++b[max(i,min(m+1,j+y[p]))];
        }
        for(int j=2;j<=sqn;++j)
            ans+=st[j][i%j];
        b[i]+=b[i-1];
        cout<<ans+b[i]<<'\n';
    }
    return 0;
}

P6189 [NOI Online #1 入门组] 跑步

正整数拆分问题。

有一个很明显的 DP，f_{i,j} 表示拆分成若干不大于 i 的数，总和为 j 的方案数，有 f_{0,0}=1,f_{i,j}=f_{i-1,j}+f_{i,j-i}。复杂度为 O(n^2)。

令 m=\lfloor\sqrt n\rfloor 上面的 DP，我们可以只求到 f_{m-1,n}，下面更换 DP 方式。

设 g_{i,j} 表示用 i 个大于等于 m 的数，和为 j 的方案数，有 g_{0,0}=1，g_{i,j}=g_{i-1,j-m}+g_{i,j-i}。转移的意思为，我们可以新添加一个数 m，或者将已经选的 i 个数全部加一，分别对应 g_{i-1,j-m} 与 g_{i,j-i}。这一部分的 g 也只用求到 g_{m,n}，因为更多的数无意义。

最终答案为 \sum_{i=1}^n(f_{m-1,i}\times\sum_{j=0}^mg_{j,n-i})，相当于把 < m 的和 \ge m 的拼起来。

这样总复杂度为 O(n\sqrt n)。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,Q=320;
int n,m,p,f[Q][N],g[Q][N];
int ans=0;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>p;const int P=p;
    int m=sqrt(n);f[0][0]=g[0][0]=1;
    for(int i=1;i<m;++i){
        for(int j=0;j<=n;++j){
            f[i][j]=f[i-1][j];
            if(j>=i)(f[i][j]+=f[i][j-i])%=P;
        }
    }
    for(int i=1;i<m;++i){
        for(int j=0;j<=n;++j){
            if(j>=m)(g[i][j]+=g[i-1][j-m])%=P;
            if(j>=i)(g[i][j]+=g[i][j-i])%=P;
        }
    }
    for(int i=0;i<=n;++i){
        int s=0;for(int j=0;j<m;++j)(s+=g[j][n-i])%=P;
        ans=(ans+1ll*f[m-1][i]*s)%P;
    }cout<<ans<<'\n';
    return 0;
}

三、莫队

普通莫队——P3901 数列找不同

多次判断某个区间的数是否互不相同。

只讲莫队的方法。题目相当于判断区间内不同数字的个数是否等于区间长度。我们发现，如果我们记录了区间 [l,r] 的数字的桶，我们可以 O(1) 更新到 [l+1,r],[l,r-1],[l-1,r],[l,r+1]。一种暴力的想法是将询问存下来，先按 l 排序，再按 r 排序，每次从上一个的答案区间暴力移动过来。

但是我们可以轻松卡掉这种做法，原因是我们的 l 从小到大，只有 O(n) 级别的变化量，而 r 可能因为左右大幅度横跳达到 O(n^2) 级别。

考虑根号平衡，将长度为 n 的区间分成 \sqrt n 块，将 l 所在的块作为第一关键字从小到大，将 r 作为第二关键字从小到大。这样暴力移动区间复杂度是对的。因为相邻两个 l 变化量是 O(\sqrt n) 级别的，而对于 l 再同一个块内的 r 是递增的，共有 \sqrt n 个块，所以 r 的变化量的和是 O(n\sqrt n) 级别，于是总复杂度为 O(n\sqrt n)。

不理解可以先记着排序的方式，会用就行。

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
struct question{int l,r,id;}q[N];
int tong[N],a[N],p1=0,p2=0;
int cnt=0,ans[N],s;
inline bool cmp(question x,question y){
    return (x.l/s==y.l/s)?x.r<y.r:x.l<y.l;
}inline void add(int x){
    if((++tong[a[x]])==1)cnt++;
}inline void era(int x){
    if((--tong[a[x]])==0)cnt--;
}signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    register int n,m,i,j;
    cin>>n>>m;
    s=sqrt(n);
    for(i=1;i<=n;i++)
        cin>>a[i];
    for(i=1;i<=m;i++)
        cin>>q[i].l>>q[i].r,q[i].id=i;
    sort(q+1,q+m+1,cmp);
    for(i=1;i<=m;i++){
        int L=q[i].l;
        int R=q[i].r;
        while(p1>L)p1--,add(p1);
        while(p1<L)era(p1),p1++;
        while(p2>R)era(p2),p2--;
        while(p2<R)p2++,add(p2);
        if(cnt==R-L+1)
            ans[q[i].id]=1;
    }
    for(int i=1;i<=m;i++)
        if(ans[i]==1)cout<<"Yes\n";
        else cout<<"No\n";
    return 0;
}

作者若干年前的丑代码。

P1494 [国家集训队] 小 Z 的袜子

维护区间内有多少对相同的数字。

在上一题的基础上，记录一个总答案，设加入数 x 前有 st_x 个数 x，对总答案的贡献就是 st_x，并且 st_x\gets st_x+1。

#include<bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
const int N=50005,Q=223;
int n,m,a[N],st[N];
ll ans[N],gty[N],res;
struct ques{int l,r,id;}q[N];
void add(int x){res+=st[x];++st[x];}
void era(int x){--st[x];res-=st[x];}
bool cmp(ques x,ques y){
    return x.l/Q==y.l/Q?x.r<y.r:x.l<y.l;
}signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=1,j;i<=m;++i)
        cin>>q[i].l>>q[i].r,j=q[i].r-q[i].l+1,
        gty[q[i].id=i]=1ll*j*(j-1)/2;
    sort(q+1,q+m+1,cmp);
    for(int i=1,l=1,r=0;i<=m;++i){
        int L=q[i].l,R=q[i].r;
        while(l>L)add(a[--l]);while(r<R)add(a[++r]);
        while(l<L)era(a[l++]);while(r>R)era(a[r--]);
        ans[q[i].id]=res;
    }for(int i=1;i<=m;++i){
        if(!ans[i])cout<<"0/1\n";
        else{
            int d=__gcd(ans[i],gty[i]);
            cout<<ans[i]/d<<'/'<<gty[i]/d<<'\n';
        }
    }
    return 0;
}

P3730 曼哈顿交易

多次询问区间相同数字出现次数的第 k 小。

如果只是区间第 k 小，那么可以用主席树解决。但是我们要维护区间每个数的出现次数，如果用莫队加线段树维护一个桶，复杂度为 O(n \sqrt n \log n) 的，原因是线段树单点修改是 O(\log n) 的。

我们不需要线段树的 O(\log n) 的查询，分块的 \sqrt n 也很好，并且分块的单点修改是 O(1) 的，刚好配上莫队，于是使用值域分块加莫队就可以 O(n\sqrt n) 解决。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,SN=320;
int n,m,sqn,nqs;
int a[N],lsh[N];
struct ques{int l,r,k,id;}q[N];
inline bool cmp(ques a,ques b){return(a.l/sqn==b.l/sqn?a.r<b.r:a.l<b.l);}
int block[N],le[SN],ri[SN];
int st1[N],st2[N],st3[SN];
int ans[N];
inline void add(int x){
    --st2[st1[x]];
    --st3[block[st1[x]]];
    ++st1[x];
    ++st2[st1[x]];
    ++st3[block[st1[x]]];
}
inline void del(int x){
    --st2[st1[x]];
    --st3[block[st1[x]]];
    --st1[x];
    ++st2[st1[x]];
    ++st3[block[st1[x]]];
}
inline int solve(int k){
    int i;
    for(i=1;i<=sqn;++i)
        if(k<=st3[i])break;
        else k-=st3[i];
    if(i==sqn+1)return -1;
    for(int j=le[i];j<=ri[i];++j)
        if(k<=st2[j])return j;
        else k-=st2[j];
    return -1;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    sqn=sqrt(n);
    for(int i=1;i<=n;++i)
        cin>>a[i],lsh[i]=a[i];
    sort(lsh+1,lsh+n+1);
    int cnt=unique(lsh+1,lsh+n+1)-lsh-1;
    for(int i=1;i<=n;++i)
        a[i]=lower_bound(lsh+1,lsh+cnt+1,a[i])-lsh;
    for(int i=1,num=-1;i<=n;++i){
        block[i]=(i-1)/sqn+1;
        if(num^block[i])
            le[++nqs]=i,num=nqs;
        ri[nqs]=i;
    }
    for(int i=1;i<=m;++i)
        cin>>q[i].l>>q[i].r>>q[i].k,q[i].id=i;
    sort(q+1,q+m+1,cmp);
    int l=1,r=0;
    for(int i=1;i<=m;++i){
        while(l>q[i].l)add(a[--l]);
        while(r<q[i].r)add(a[++r]);
        while(l<q[i].l)del(a[l++]);
        while(r>q[i].r)del(a[r--]);
        ans[q[i].id]=solve(q[i].k);
    }

    for(int i=1;i<=n;++i)
        cout<<ans[i]<<'\n';
    return 0;
}

带修莫队——P1903 [国家集训队] 数颜色 / 维护队列

除了区间的变化，我们多了一维时间线。

我们能否从状态 (l,r,t)，即第 t 个时刻区间 [l,r] 的信息 O(1) 更新到 (l\pm 1,r\pm 1,t\pm 1) 呢？答案是可以的，区间变化是平常的时间的变化要考虑第 t\pm1 个时刻干了什么。如果修改位置在 [l,r] 中，相当于一次删除，一次添加。如果不在则暂时没有影响，我们可以把可能会被修改成的数加到序列末尾，这样一次时间的变化相当与做序列的交换，这样就解决了还原的问题（不然当你撤回时间上的变化时不知道原来时什么）。

那么怎么排序呢？取 B=n^{\frac2 3}，如果 \lfloor \frac {l_1}B \rfloor\not=\lfloor \frac {l_2}B \rfloor 按照 l 排，如果等则按照 \lfloor \frac {r}B \rfloor 排，如果 \lfloor \frac {r_1}B \rfloor=\lfloor \frac {r_2}B \rfloor 再按 t 排，这样复杂度为 O(n^{\frac 5 3})，不会证也不想证。

#include<bits/stdc++.h>
using namespace std;
const int N=133338,M=1e6+5,Q=2600;
int n,m,k,a[N],p[N],c[N],ans[N];
struct ques{int l,r,t,id;}q[N];
bool cmp(ques x,ques y){
    return x.l/Q==y.l/Q?x.r/Q==y.r/Q?x.t<y.t:x.r<y.r:x.l<y.l;
}int st[M],cnt=0;
void add(int x){cnt+=!st[x]++;}
void del(int x){cnt-=!--st[x];}
void upd(int x,int y){
    if(q[x].l<=p[y]&&p[y]<=q[x].r)
        del(a[p[y]]),add(c[y]);
    swap(a[p[y]],c[y]);
}signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=1,j=0;i<=m;++i){
        char op;cin>>op;
        if(op=='R')++j,cin>>p[j]>>c[j];
        else ++k,cin>>q[k].l>>q[k].r,q[k].t=j,q[k].id=k;
    }sort(q+1,q+k+1,cmp);
    for(int i=1,l=1,r=0,t=0;i<=k;++i){
        int L=q[i].l,R=q[i].r,T=q[i].t;
        while(l>L)add(a[--l]);while(r<R)add(a[++r]);
        while(l<L)del(a[l++]);while(r>R)del(a[r--]);
        while(t<T)upd(i,++t);while(t>T)upd(i,t--);
        ans[q[i].id]=cnt;
    }for(int i=1;i<=k;++i)
        cout<<ans[i]<<'\n';
    return 0;
}

回滚莫队——P5906 【模板】回滚莫队

有些时候，我们会发现添加容易，但是删除很困难。

在讨论莫队复杂度时，我们发现 l 的总是在一个块里来回移动，r 总是从小到大的。对于 l 所属的块变化时，我们直接 O(n) 暴力计算，因为总共 O(\sqrt n) 次。而 l 在同一个块时，r 是递增的不用担心，而 l 我们可以直接从块的有边界重新跑一边。具体的，设 x 为 l 所在块的右端点，我们有区间 [x,r] 的答案，每次从 [x,r] 更新到 [l,r]，总结答案，再恢复成 [x,r]，也就是“回滚”的操作。

对于这一题，我们维护每个数最左和最右的位置，这种信息添加是容易的。如果 l,r 在同一个块内则暴力计算，如果 l_i 与 l_{i-1} 不在同一个块也暴力计算。保存一个 [x,r] 的答案数组，暴力移动后再改回去，复杂度是 O(n\sqrt n) 的。

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,sqn,a[N];
int lsh[N],len;
int block[N];
struct ques{int l,r,id;}q[N];
inline bool cmp(ques x,ques y){
    return (block[x.l]==block[y.l]?x.r<y.r:x.l<y.l);
}int ans[N];
int t[N],pre[N];
int mx1[N],mn1[N];
int mx2[N],mn2[N];
int mx3[N],mn3[N];
int res1,res2;
inline void add1(int x){
    mx2[a[x]]=mx1[a[x]]=max(mx1[a[x]],x);
    mn2[a[x]]=mn1[a[x]]=min(mn1[a[x]],x);
    res2=res1=max(res1,mx1[a[x]]-mn1[a[x]]);
}
inline void add2(int x){
    mx2[a[x]]=max(mx2[a[x]],x);
    mn2[a[x]]=min(mn2[a[x]],x);
    res2=max(res2,mx2[a[x]]-mn2[a[x]]);
}
inline void era(int x){
    mx2[a[x]]=mx1[a[x]];
    mn2[a[x]]=mn1[a[x]];
    res2=res1;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;sqn=sqrt(n);
    for(int i=1;i<=n;++i)
        cin>>a[i],lsh[i]=a[i];
    sort(lsh+1,lsh+n+1);
    len=unique(lsh+1,lsh+n+1)-lsh-1;
    for(int i=1;i<=n;++i)
        a[i]=lower_bound(lsh+1,lsh+len+1,a[i])-lsh;
    for(int i=1;i<=n;++i)
        block[i]=(i-1)/sqn+1;
    cin>>m;
    for(int i=1;i<=m;++i)
        cin>>q[i].l>>q[i].r,q[i].id=i;
    sort(q+1,q+m+1,cmp);
    memset(mn1,0x3f,sizeof(mn1));
    memset(mn2,0x3f,sizeof(mn2));
    memset(mn3,0x3f,sizeof(mn3));
    for(int i=1,l=1,r=0,bl=0,br=0;i<=m;++i){
        int L=q[i].l,R=q[i].r;
        if(block[R]-block[L]<=1){
            int res=0;
            for(int j=L;j<=R;++j){
                mx3[a[j]]=max(mx3[a[j]],j);
                mn3[a[j]]=min(mn3[a[j]],j);
                res=max(res,mx3[a[j]]-mn3[a[j]]);
            }
            ans[q[i].id]=res;
            for(int j=L;j<=R;++j)
                mx3[a[j]]=0,mn3[a[j]]=0x3f3f3f3f;
        }
        else{
            if(block[L]!=bl){
                for(int j=1;j<=len;++j)
                    mx1[j]=mx2[j]=0,mn1[j]=mn2[j]=0x3f3f3f3f;
                res1=res2=0;
                bl=block[L];
                r=br=min(bl*sqn,n);
                l=r+1;
            }
            while(r<R)add1(++r);
            while(l>L)add2(--l);
            ans[q[i].id]=res2;
            while(l<=br)era(l++);
            res2=res1;
        }
    }
    for(int i=1;i<=m;++i)
        cout<<ans[i]<<'\n';
    return 0;
}

P3709 大爷的字符串题

求区间众数出现的次数。

这个转化比较特别，我们可以将这个区间重排成尽可能少的严格递增序列，这样是最优的，而答案就是区间众数出现次数。

我们添加是好添加的，然而删除我们不知道次大的是什么，如果用 set 则又要多个 \log，所以使用回滚莫队。

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,sqn,a[N];
int lsh[N],len;
int block[N];
struct ques{int l,r,id;}q[N];
inline bool cmp(ques x,ques y){
    return (block[x.l]==block[y.l]?x.r<y.r:x.l<y.l);
}int ans[N];
int t[N],pre[N];
int st1[N],st2[N],st3[N];
int res1,res2;
inline void add1(int x){
    st2[x]=st1[x]=++st1[x];
    res2=res1=max(res1,st1[x]);
}
inline void add2(int x){
    st2[x]=++st2[x];
    res2=max(res2,st2[x]);
}
inline void era(int x){
    st2[x]=st1[x];
    res2=res1;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;sqn=sqrt(n);
    for(int i=1;i<=n;++i)
        cin>>a[i],lsh[i]=a[i];
    sort(lsh+1,lsh+n+1);
    len=unique(lsh+1,lsh+n+1)-lsh-1;
    for(int i=1;i<=n;++i)
        a[i]=lower_bound(lsh+1,lsh+len+1,a[i])-lsh;
    for(int i=1;i<=n;++i)
        block[i]=(i-1)/sqn+1;
    for(int i=1;i<=m;++i)
        cin>>q[i].l>>q[i].r,q[i].id=i;
    sort(q+1,q+m+1,cmp);
    for(int i=1,l=1,r=0,bl=0,br=0;i<=m;++i){
        int L=q[i].l,R=q[i].r;
        if(block[R]-block[L]<=1){
            int res=0;
            for(int j=L;j<=R;++j){
                ++st3[a[j]];
                res=max(res,st3[a[j]]);
            }
            ans[q[i].id]=res;
            for(int j=L;j<=R;++j)
                st3[a[j]]=0;
        }
        else{
            if(block[L]!=bl){
                for(int j=1;j<=len;++j)
                    st1[j]=st2[j]=0;
                res1=res2=0;
                bl=block[L];
                r=br=min(bl*sqn,n);
                l=r+1;
            }
            while(r<R)add1(a[++r]);
            while(l>L)add2(a[--l]);
            ans[q[i].id]=res2;
            while(l<=br)era(a[l++]);
            res2=res1;
        }
    }
    for(int i=1;i<=m;++i)
        cout<<-ans[i]<<'\n';
    return 0;
}

莫队二离——P4887 【模板】莫队二次离线

有时，我们从 [l,r] 到 [l\pm1,r\pm1] 不能做到 O(1)。莫队的复杂度为 O(n\sqrt nk)，k 为移动一次端点的复杂度，我们可以将其优化成 O(n\sqrt n+nk)。

以这题为例，我们要查询若干个 f(x,l,r)，表示 a_x 加入 [l,r] 这个区间的贡献。先考虑这个怎么计算，有 f(x,l,r)=f(x,1,r)-f(x,1,l-1)，转化为一个前缀的计算。打标或组合计算得，二进制下有 k 个 1 的数最多只有约 3000 个，于是 O(3000n) 处理前缀和（挺极限的），于是我们可以计算出 (x,1),(x,2)...(x,y) 合法二元组的数目。

for(int i=0;i<16384;++i)
    if(__builtin_popcount(i)==k)
        base.push_back(i);
for(int i=1;i<=n;++i){
    for(auto x:base)
        ++t[a[i]^x];
    pre[i]=t[a[i+1]];
}

这里 pre_x 为 f(x+1,1,x) 的答案。

我们对答案差分，这样我们只用处理相邻两个答案的变化量。我们共有 n\sqrt n 个的形如 f(x,l,r) 的查询，如果直接存将是 O(n\sqrt n) 的空间，不能通过。我们发现我们的查询为四种形式，不难发现 k\not=0 时 f(x,x,x)=0。

其中部分是直接能用 pre 算的。不能算的，我们以 f(r+1,1,l-1) 为例。将 (r,R,id) 挂到 l-1 上，其中 l,r 为现在的区间端点，R 为目标位置，记录其是加还是减，当前缀和做到 l-1 时，暴力从 r 到 R 算，因为莫队的特性，这些移动长度和不超过 O(n\sqrt n)。

特判 k=0，最后再作一边前缀和。代码小清新。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,k,a[N];
int sqn,ans[N];
struct ques{int l,r,id;}q[N];
inline bool cmp(ques x,ques y){
    return (x.l/sqn==y.l/sqn?x.r<y.r:x.l<y.l);
}
vector<int> base;
vector<tuple<int,int,int> >v[N];
int t[N],pre[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    if(k>14){
        for(int i=1;i<=m;++i)
            cout<<"0\n";
        return 0;
    }sqn=sqrt(n);
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=1;i<=m;++i)
        cin>>q[i].l>>q[i].r,q[i].id=i;
    sort(q+1,q+m+1,cmp);
    for(int i=0;i<16384;++i)
        if(__builtin_popcount(i)==k)
            base.push_back(i);
    for(int i=1;i<=n;++i){
        for(auto x:base)
            ++t[a[i]^x];
        pre[i]=t[a[i+1]];
    }memset(t,0,sizeof(t));
    for(int i=1,l=1,r=0;i<=n;++i){
        int L=q[i].l,R=q[i].r;
        if(l<L)v[r].emplace_back(l,L-1,-i);
        while(l<L)ans[q[i].id]+=pre[l-1],++l;
        if(l>L)v[r].emplace_back(L,l-1,i);
        while(l>L)ans[q[i].id]-=pre[l-2],--l;
        if(r<R)v[l-1].emplace_back(r+1,R,-i);
        while(r<R)ans[q[i].id]+=pre[r],++r;
        if(r>R)v[L-1].emplace_back(R+1,r,i);
        while(r>R)ans[q[i].id]-=pre[r-1],--r;
    }
    for(int i=1,id,l,r;i<=n;++i){
        for(auto x:base)++t[a[i]^x];
        for(const auto& x:v[i]){
            tie(l,r,id)=x;
            for(int j=l,tmp=0;j<=r;++j){
                tmp=t[a[j]];
                if(j<=i&&k==0)--tmp;
                if(id<0)ans[q[-id].id]-=tmp;
                else ans[q[id].id]+=tmp;
            }
        }
    }
    for(int i=1;i<=m;++i)
        ans[q[i].id]+=ans[q[i-1].id];
    for(int i=1;i<=m;++i)
        cout<<ans[i]<<'\n';
    return 0;
}

P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II

我们需要在莫队的基础上求出区间 < x,>x 数的个数，如果硬做在莫队的基础上要多个 \log，于是莫队二离启动。这题与上一题十分相似，甚至处理起来更直白。逆序对用树状数组还是分块随意。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5,sqn=320;
ll c[N];
void add(int x){while(x<N)++c[x],x+=x&-x;}
ll ask(int x){int k=0;while(x)k+=c[x],x-=x&-x;return k;}
int n,m;
int a[N],lsh[N],cnt;
ll pre[N],suf[N],ans[N];
struct ques{int l,r,id;}q[N];
inline bool cmp(ques x,ques y){
    return x.l/sqn==y.l/sqn?x.r<y.r:x.l<y.l;
}
struct node{int id,l,r,v;};
vector<node>v1[N],v2[N];
inline void init(){
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>a[i],lsh[i]=a[i];
    sort(lsh+1,lsh+n+1);
    cnt=unique(lsh+1,lsh+n+1)-lsh-1;
    for(int i=1;i<=n;++i)
        a[i]=lower_bound(lsh+1,lsh+cnt+1,a[i])-lsh;
    for(int i=1;i<=n;++i)
        pre[i]=pre[i-1]+i-1-ask(a[i]),add(a[i]);
    memset(c,0,sizeof(c));
    for(int i=n;i>=1;--i)
        suf[i]=suf[i+1]+ask(a[i]-1),add(a[i]);
    for(int i=1;i<=m;++i)
        cin>>q[i].l>>q[i].r,q[i].id=i;
    sort(q+1,q+m+1,cmp);
}
int id[N],le[N],ri[N];
int tag[N],w[N];
inline void solve1(){
    for(int i=1,l=1,r=0;i<=m;++i){
        int L=q[i].l,R=q[i].r,id=q[i].id;
        if(r<R)ans[q[i].id]+=(pre[R]-pre[r]),
            v1[l].push_back((node){id,r+1,R,-1}),r=R;
        if(r>R)ans[q[i].id]-=(pre[r]-pre[R]),
            v1[l].push_back((node){id,R+1,r,1}),r=R;
        if(l<L)ans[q[i].id]-=(suf[l]-suf[L]),
            v2[r].push_back((node){id,l,L-1,1}),l=L;
        if(l>L)ans[q[i].id]+=(suf[L]-suf[l]),
            v2[r].push_back((node){id,L,l-1,-1}),l=L;
    }
}
inline void solve2(){
    int num=sqrt(cnt),cur=1;le[1]=1;
    if(num*num<cnt)++num;
    for(int i=1;i<=cnt;++i){
        id[i]=cur;
        if(i%num==0)ri[cur]=i,le[++cur]=i+1;
    }ri[cur]=cnt;
    for(int i=1;i<=n;++i){
        for(int j=0;j<v1[i].size();++j){
            int L=v1[i][j].l,R=v1[i][j].r,v=v1[i][j].v;
            for(int k=L;k<=R;++k)
                ans[v1[i][j].id]+=1ll*v*(tag[id[a[k]+1]]+w[a[k]+1]);
        }
        int x=a[i];
        for(int i=le[id[x]];i<=x;++i)++w[i];
        for(int i=1;i<id[x];++i)++tag[i];
    }
    memset(tag,0,sizeof(tag));
    memset(w,0,sizeof(w));
    for(int i=n;i>=1;--i){
        for(int j=0;j<v2[i].size();++j){
            int L=v2[i][j].l,R=v2[i][j].r,v=v2[i][j].v;
            for(int k=L;k<=R;++k)
                ans[v2[i][j].id]+=1ll*v*(tag[id[a[k]-1]]+w[a[k]-1]);
        }
        int x=a[i];
        for(int i=x;i<=ri[id[x]];++i)++w[i];
        for(int i=id[x]+1;i<=num;++i)++tag[i];
    }
}
inline void out(){
    for(int i=1;i<=m;++i)ans[q[i].id]+=ans[q[i-1].id];
    for(int i=1;i<=m;++i)cout<<ans[i]<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    init();solve1();solve2();out();
    return 0;
}

四、简单习题。

P3396 哈希冲突：根号分治

P5501 [LnOI2019] 来者不拒，去者不追：莫队二离

P4396 [AHOI2013] 作业：莫队

P7708 「Wdsr-2.7」八云蓝自动机 Ⅰ：莫队维护操作序列