Skip to content

莫队

~~众所周知，莫队等于分块+暴力~~

用途

离线处理区间询问问题，尤其是一些"不满足区间可加性或可乘性"的问题

原理

1.离线算法，将所有区间读下来

2.给所有区间分块，分成\(\sqrt{n}\)块

3.将所有区间的l按照块的顺序排序

4.再将同一块的所有区间按照r的顺序排序

5.维护左右两个指针，每得到一个区间的左右边界，就暴力跳转，修改答案即可

复杂度分析

总：\(\Theta(n\sqrt{n})\)

1.l:因为区间按照块将l排了序，所以l每次最多移动\(\sqrt{n}\)次，一共n个询问，总的不超过\(n \sqrt{n}\)次

2.r:对于每个块中的区间，r已经排好了序，最坏时一个块要移动到序列最右端，即一共n次，一共\(\sqrt{n}\)个块，所以不超过\(n \sqrt{n}\)次

3.块之间的跳转：一共\(\sqrt n\)个块，l最多从块尾到块头，\(\sqrt n\)次；r最多从序列尾到序列头，n次，所以不超过\(n\sqrt n\)次。

模板

P2709 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define int long long 
using namespace std;
const int N=1e5+10;
int n,m,k,c;
int vis[N],ans[N],a[N];
struct node{
    int l,r,k,id;
}q[N];
bool cmp(node a,node b){
    if(a.k!=b.k)return a.k<b.k;
    else return a.r<b.r;
}
int read1(){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9' ||ch<'0'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch<='9' && ch>='0'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void write1(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write1(x/10);
    putchar(x%10+'0');
    return;
}
signed main(){
    //freopen("P2709_1.in","r",stdin);
    //freopen("1.out","w",stdout);
    n=read1(),m=read1(),k=read1();
    for(int i=1;i<=n;++i){
        a[i]=read1();
    }
    int len=sqrt(n);
    for(int i=1;i<=m;++i){
        q[i].l=read1(),q[i].r=read1();
        q[i].k=(q[i].l-1)/len+1;q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);
    int l=1,r=0; 
    memset(vis,0,sizeof vis);
    for(int i=1;i<=m;++i){
        int x=q[i].l,y=q[i].r;
        while(l>x)--l,c+=2*vis[a[l]]+1,vis[a[l]]++;
        while(r<y)++r,c+=2*vis[a[r]]+1,vis[a[r]]++;
        while(l<x)c-=2*vis[a[l]]-1,vis[a[l]]--,++l;
        while(r>y)c-=2*vis[a[r]]-1,vis[a[r]]--,--r;
        ans[q[i].id]=c;
    }
    for(int i=1;i<=m;++i){
        write1(ans[i]);
        putchar('\n');
    }
    return 0;
}
~~写的时候注意：分块是根据l的值域(数量)分的，而不是区间的数量。不然就错了~~

happy TLE

一般处理不超过\(1* 10^5\) 的数据

带修改莫队

原理

就是将原来的询问(l,r)加了一维时间轴(l,r,t)，将l,r都分块

3d

如图，将l轴分成n块，每块长\(\frac{N}{n}\);将r轴分成k块，每块长\(\frac{N}{k}\)

复杂度

1.读入：\(\Theta(n+m)\)

2.排序：\(\Theta(nlogn)\)

3.l:每次最多移动\(\frac{N}{n}\)，一共m个询问，所以共\(\Theta(\frac{N}{n}* m)\)

块与块之间的移动共n次，一次\(\frac{2* N}{n}\)，共\(\Theta(N)\)

4.r:每次最多移动\(\frac{N}{k}\)，一共m个询问，所以共\(\Theta(\frac{N}{k}* m)\)

块与块之间的移动共k次，一次\(\frac{2* N}{k}\)，共\(\Theta(N)\)

5.t:一共n * k个块，每个块最坏去情况为推到序列最后一位，所以复杂度\(\Theta(N* n* k)\)

块与块之间一共n* k次，一次最多N，复杂度\(\Theta(N* n* k)\)

所以复杂度最小时n=k，为\(max(\Theta(N^{2-k}),\Theta(N^{1+2k}))\)

此时2-k=1+2k,即k=\(\frac13\)

所以总复杂度为\(\Theta(N^{\frac53})\)

P1903 模板

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#define int long long 
using namespace std;
const double F=0.666666666667;
const int N=2e6+10;
int a[N],vis[N],res[N];
int n,m;
char ch;
struct qe1{int l,r,id,k1,k2,t;}q1[N];
struct qe2{int x,y,id;}q2[N];
bool cmp(qe1 a,qe1 b){
    if(a.k1!=b.k1)return a.k1<b.k1;
    else if(a.k2!=b.k2)return a.k2<b.k2;
    else return a.t<b.t;
}
int read1()
void write1(int x) 
signed main(){
    n=read1(),m=read1();
    for(int i=1;i<=n;++i)a[i]=read1();
    int len=pow(n,F),c1=0,c2=0;
    for(int i=1;i<=m;++i){
        cin>>ch;
        if(ch=='Q')++c1,q1[c1].l=read1(),q1[c1].r=read1(),q1[c1].id=i,q1[c1].k1=(q1[c1].l-1)/len+1,q1[c1].k2=(q1[c1].r-1)/len+1,q1[c1].t=c2;
        else ++c2,q2[c2].x=read1(),q2[c2].y=read1(),q2[c2].id=i;
    }
    sort(q1+1,q1+c1+1,cmp);
    int l=1,r=0,t=0,ans=0;
    for(int i=1;i<=c1;++i){
        int x=q1[i].l,y=q1[i].r,z=q1[i].t;
        while(t<z){
            ++t;
            if(q2[t].x<=r && q2[t].x>=l)ans-=vis[a[q2[t].x]]==1?1:0,vis[a[q2[t].x]]--,ans+=vis[q2[t].y]==0?1:0,vis[q2[t].y]++;
            swap(a[q2[t].x],q2[t].y);
        }
        while(t>z){
            if(q2[t].x<=r && q2[t].x>=l)ans-=vis[a[q2[t].x]]==1?1:0,vis[a[q2[t].x]]--,ans+=vis[q2[t].y]==0?1:0,vis[q2[t].y]++;
            swap(a[q2[t].x],q2[t].y);
            t--;
        }
        while(l>x)--l,ans+=vis[a[l]]==0?1:0,vis[a[l]]++;
        while(r<y)++r,ans+=vis[a[r]]==0?1:0,vis[a[r]]++;
        while(l<x)ans-=vis[a[l]]==1?1:0,vis[a[l]]--,++l;
        while(r>y)ans-=vis[a[r]]==1?1:0,vis[a[r]]--,--r;
        res[q1[i].id]=ans;
    }
    for(int i=1;i<=m;++i)if(res[i])write1(res[i]),putchar('\n');
    return 0;
}

P5906

这道题是很好的分块与莫队的结合。

对于每个数(已离散化),他在区间中的最大值就是右端点到左端点大的距离，所以考虑用莫队维护左右端点。因为最左端点被删除后还需要知道次左端点，所以提前预处理出每个数的前驱后继，即用链表连接一下，方便跳转。

而最大值比较难维护，因为一共会有\(m\sqrt n\)次修改，\(m\)次查询,所以线段树等维护区间的工具会被卡成\(m \sqrt n \log n\),而观察到查询次数较小，所以可以用值域分块来维护最大值。因为分块的修改\(O(1)\),查询\(O(\sqrt n)\)，所以可以均摊到\(m\sqrt n\).

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define int long long 
using namespace std;
const int N=2e5+10;
int n,m,len,MAX,num;
int a[N],b[N],vis[N],K[N],L[N],R[N],pre[N],nxt[N],ans[N],s[N],S[N];
struct query{
    int l,r,k,id;
}q[N];
struct block{
    int l,r;    
}k[N];
bool cmp(query a,query b){
    if(a.k==b.k)return a.r<b.r;
    else return a.k<b.k;    
}
bool cmp1(int a,int b){
    return a<b;
}
void init(){
    len=sqrt(n);
    sort(b+1,b+n+1,cmp1);
    int tot=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i){
        a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
    }
    for(int i=1;i<=n;++i){
        if(vis[a[i]])pre[i]=vis[a[i]],nxt[vis[a[i]]]=i;
        vis[a[i]]=i;
    }
    for(int i=1;i<=n;++i){
        K[i]=(i-1)/len+1;
    }
    num=K[n];
    for(int i=1;i<=num;++i){
        k[i].l=(i-1)*len+1;
        k[i].r=i*len;
    }
}
void change(int x,int k){
    S[K[x]]+=k;
    s[x]+=k; 
}
int query(){
    for(int i=num;i>=1;--i){
        if(S[i]>0){
            for(int j=k[i].r;j>=k[i].l;--j){
                if(s[j]>0)return j;
            }
        }
    }
    return 0;
} 
void addl(int i){
    if(!R[a[i]]){
        R[a[i]]=L[a[i]]=i;
        return; 
    }
    change(R[a[i]]-L[a[i]],-1);
    L[a[i]]=i;
    change(R[a[i]]-L[a[i]],1);
}
void addr(int i){
    if(!L[a[i]]){
        R[a[i]]=L[a[i]]=i;
        return; 
    }
    change(R[a[i]]-L[a[i]],-1);
    R[a[i]]=i;
    change(R[a[i]]-L[a[i]],1);
}
void dell(int i){
    if(R[a[i]]==L[a[i]]){
        R[a[i]]=L[a[i]]=0;
        return; 
    }
    change(R[a[i]]-L[a[i]],-1);
    L[a[i]]=nxt[i];
    change(R[a[i]]-L[a[i]],1);
}
void delr(int i){
    if(R[a[i]]==L[a[i]]){
        R[a[i]]=L[a[i]]=0;
        return; 
    }
    change(R[a[i]]-L[a[i]],-1);
    R[a[i]]=pre[i];
    change(R[a[i]]-L[a[i]],1);
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]),b[i]=a[i];
    init();
    scanf("%lld",&m);
    for(int i=1;i<=m;++i){
        scanf("%lld%lld",&q[i].l,&q[i].r);  
        q[i].k=(q[i].l-1)/len+1;
        q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);
    int l=1,r=0;
    memset(L,0,sizeof L);
    memset(R,0,sizeof R);
    for(int i=1;i<=m;++i){
        int x=q[i].l,y=q[i].r;
        while(l>x)addl(--l);
        while(r<y)addr(++r);
        while(l<x)dell(l++);
        while(r>y)delr(r--);
        ans[q[i].id]=query();
    }
    for(int i=1;i<=m;++i)printf("%lld\n",ans[i]);
    return 0;
}

什么，你说不够"优雅",不够快? 没事，这题还是个回滚莫队的模板题...

回滚莫队

对于添加方便而删除不方便的操作，如维护最大值，删除后要找到次大值，较为麻烦。这时我们可以用回滚莫队尽可能的减少删除操作。

我们可以将左右指针放在一个块的最右端。

对于每个询问，如果它左右端点都在一个块内，虽然不能避免删除，但是暴力时间是\(\sqrt n\),可以接受。

接下来，每遇到一个新的块，此时块内的询问满足左端点都在块内，右端点都不在块内，这时我们可以将右端点不断向右移动，更新答案，左端点不断移动过去再~~退~~滚回来，将沿路产生的贡献全部删除，并且只计入变量\(\_tmp\)中，不计入原有答案。这样就可以实现"回滚"的过程，全程没有删除操作。

最后只需要比较\(\_tmp\)与\(tmp\)的最大值即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define int long long 
using namespace std;
const int N=3e5+10;
int n,m,len,tot,num;
int a[N],b[N],L[N],R[N],blk[N],st[N],ed[N],ed1[N],ans[N];
struct query{
    int l,r,k,id;
}q[N];
bool Cmp(query a,query b){
    if(a.k==b.k)return a.r<b.r;
    else return a.k<b.k;
}
bool cmp(int a,int b){
    return a<b;
}
void Discrete(){
    sort(b+1,b+n+1,cmp);
    tot=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
}

signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]),b[i]=a[i];
    Discrete();
    scanf("%lld",&m);
    len=sqrt(n);
    for(int i=1;i<=m;++i){
        scanf("%lld%lld",&q[i].l,&q[i].r);
        q[i].k=(q[i].l-1)/len+1;    
        q[i].id=i;
    }
    sort(q+1,q+m+1,Cmp);

    for(int i=1;i<=n;++i){
        blk[i]=(i-1)/len+1;
    }
    num=blk[n];
    for(int i=1;i<=num;++i){
        L[i]=(i-1)*len+1;
        R[i]=(i==num)?n:i*len;//容易写错
    }

    int block=0,tmp=0,l=1,r=0;
    for(int i=1;i<=m;++i){
        int x=q[i].l,y=q[i].r,now=blk[x];
        if(blk[x]==blk[y]){//暴力
            tmp=0;
            for(int j=x;j<=y;++j)st[a[j]]=0;
            for(int j=x;j<=y;++j){
                if(!st[a[j]])st[a[j]]=j;
                tmp=max(tmp,j-st[a[j]]);
            }
            for(int j=x;j<=y;++j)st[a[j]]=0;
            ans[q[i].id]=tmp;
            continue;
        }
        if(now!=block){
            tmp=0;
            for(int j=l;j<=r;++j)st[a[j]]=ed[a[j]]=0;
            l=R[now];
            r=l-1;//注意，莫队套路，r=l-1
            block=now;//换块时将所有值初始化为0，左右端点挪到块右端点。
        }
        while(r<y){
            ++r;
            if(!st[a[r]])st[a[r]]=r;
            ed[a[r]]=r;//不断更新ed，保证更新左端点时可以用上。
            tmp=max(tmp,r-st[a[r]]);
        }
        int p=l,tmp1=0;
        while(p>x){//add
            --p; 
            if(!ed1[a[p]])ed1[a[p]]=p;
            tmp1=max(tmp1,max(ed1[a[p]],ed[a[p]])-p);//在ed1和ed中取最大值。
        }
        while(p<l){//del
            ed1[a[p]]=0;
            p++;
        }
        ans[q[i].id]=max(tmp,tmp1);
    }
    for(int i=1;i<=m;++i){
        printf("%lld\n",ans[i]);
    }

    return 0;
} 
/*
8
1 6 2 2 3 3 1 6
6
1 3
1 4
2 5
2 8
5 6
1 7
*/

AT1219

解法一：因为每个数出现的次数会影响值域分块，所以对于出现\(t\)次的数\(x\)，将\(x,2x,3x,...tx\)全部记录到离散化数组里，再堆离散化数组值域分块即可。

因为\(\sum t_i=n\),所以复杂度正确，为\(m\sqrt n\)

同时还可以回滚莫队做。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define int long long 
using namespace std;
const int N=1e5+10;
int n,m,len,num;
int a[N],b[N],blk[N],L[N],R[N],cnt[N],tot[N],ans[N];
struct query{
    int l,r,k,id;
}q[N];
bool cmp(int a,int b){
    return a<b;
}
bool Cmp(query a,query b){
    if(a.k==b.k)return a.r<b.r;
    else return a.k<b.k;
}
void Discrete(){
    sort(b+1,b+n+1,cmp);
    int tott=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+tott+1,a[i])-b;
}
void init(){
    for(int i=1;i<=n;++i){
        blk[i]=(i-1)/len+1;
    }
    num=blk[n];
    for(int i=1;i<=num;++i){
        L[i]=(i-1)*len+1;
        R[i]=(i==num)?n:i*len;
    }
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]),b[i]=a[i];
    Discrete();
    len=sqrt(n);
    for(int i=1;i<=m;++i){
        scanf("%lld%lld",&q[i].l,&q[i].r);
        q[i].k=(q[i].l-1)/len+1;
        q[i].id=i;
    }
    sort(q+1,q+m+1,Cmp);
    init();
    int l=1,r=0,tmp=0,block=0;
    for(int i=1;i<=m;++i){
        int x=q[i].l,y=q[i].r,now=blk[x];
        if(blk[x]==blk[y]){
            tmp=0;
            for(int j=x;j<=y;++j)cnt[a[j]]=0;
            for(int j=x;j<=y;++j){
                cnt[a[j]]++;
                tmp=max(tmp,cnt[a[j]]*b[a[j]]);
            }
            for(int j=x;j<=y;++j)cnt[a[j]]=0;
            ans[q[i].id]=tmp;
            continue;
        }
        if(block!=now){
            tmp=0;
            for(int j=l;j<=r;++j)cnt[a[j]]=0;
            l=R[now];
            r=l-1;
            block=now;
        }
        while(r<y){
            ++r;
            cnt[a[r]]++;
            tmp=max(tmp,cnt[a[r]]*b[a[r]]);
        }
        int p=l,_tmp=0;
        while(p>x){
            --p;
            tot[a[p]]++;
            _tmp=max(_tmp,(tot[a[p]]+cnt[a[p]])*b[a[p]]);
        }
        while(p<l){
            tot[a[p]]=0;
            p++;
        }
        ans[q[i].id]=max(tmp,_tmp);
    }
    for(int i=1;i<=m;++i){
        printf("%lld\n",ans[i]);
    }
    return 0;
}

P8078

~~考场上只拿了35pts差五分就有铜牌的蒟蒻~~

对于所有数从小到大的顺序排序后，可以用链表把他们连接起来，链表边上记录一下权值。发现链表删除+恢复远比添加简单得多，所以可以用不添加莫队。

与不删除莫队类似，都是处理完左端点回滚。只是这个初始是\(l=1,r=n\),从两端向中间更改\(l,r\).

~~最后输给了巨大的常数拿了95pts~~

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rg register
using namespace std;
typedef long long ll;
const int N=5e5+10,INF=0x3f3f3f3f;
inline int read1(){
    int x=0;char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch<='9' && ch>='0') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x;
}
inline void write1(ll x){
    if(x>9) write1(x/10);
    putchar(x%10+'0');
}
struct node{
    int l,r,k,id;
}q[N];

struct link{
    int v,p;
}pre[N],nxt[N];
int n,m,K,L;
ll tmp,_tmp;
int a[N],blk[N],lb[N],rb[N],s[N];
ll ans[N];
bool cmp(node a,node b){
    if(a.k==b.k) return a.r>b.r;
    return a.k<b.k;
}
void init(){
    _tmp=0;
    for(rg int i=2;i<=n;++i){
        int x=s[i]-s[i-1];
        _tmp+=(ll)abs(x);
        nxt[i-1].v=i,nxt[i-1].p=x;  
        pre[i].v=i-1,pre[i].p=-x;   
    }
    pre[1].v=pre[1].p=-INF;
    nxt[n].v=nxt[n].p=-INF;

}
inline void del(int i){
    int _x=pre[a[i]].v,_y=nxt[a[i]].v,l1=pre[a[i]].p,l2=nxt[a[i]].p,l3=-l1+l2;

    if(_x==-INF && _y!=-INF){//pre
        pre[_y].v=pre[_y].p=-INF;
        _tmp-=(ll)abs(l2);
    }
    if(_x!=-INF && _y==-INF){//nxt
        nxt[_x].v=nxt[_x].p=-INF;
        _tmp-=(ll)abs(l1);  
    }
    if(_x!=-INF && _y!=-INF){//pre nxt
        nxt[_x].v=_y;nxt[_x].p=l3;
        pre[_y].v=_x;pre[_y].p=-l3;
        _tmp=_tmp-(ll)(abs(l1)+abs(l2)-abs(l3));
    } 

}
inline void cov(int i){
    int _x=pre[a[i]].v,_y=nxt[a[i]].v,l1=pre[a[i]].p,l2=nxt[a[i]].p,l3=-l1+l2;
    if(_x==-INF && _y!=-INF){//pre
        pre[_y].v=a[i],pre[_y].p=-l2;
        _tmp+=(ll)abs(l2);
    }
    if(_x!=-INF && _y==-INF){//nxt
        nxt[_x].v=a[i];nxt[_x].p=-l1;
        _tmp+=(ll)abs(l1);  
    }
    if(_x!=-INF && _y!=-INF){//pre nxt
        nxt[_x].v=a[i];nxt[_x].p=-l1;
        pre[_y].v=a[i];pre[_y].p=-l2;
        _tmp=_tmp+(ll)(abs(l1)+abs(l2)-abs(l3));
    } 
}
int main(){
    n=read1(),m=read1();L=sqrt(n);
    for(rg int i=1;i<=n;++i) a[i]=read1(),s[a[i]]=i,blk[i]=(i-1)/L+1;
    for(rg int i=1;i<=m;++i) q[i].l=read1(),q[i].r=read1(),q[i].k=(q[i].l-1)/L+1,q[i].id=i;
    K=blk[n];
    for(rg int i=1;i<=K;++i) lb[i]=(i-1)*L+1,rb[i]=min(i*L,n); 
    sort(q+1,q+m+1,cmp);
    int l=1,r=n,now=0;
    init();
    for(rg int i=1;i<=m;++i){
        int x=q[i].l,y=q[i].r;
        if(blk[x]!=now){
            now=blk[x];
            while(r<n) cov(++r);
            while(l<lb[now]) del(l++);
        }
        while(r>y) del(r--);
        int p=l;
        while(p<x) del(p++);
        ans[q[i].id]=_tmp;
        while(p>l) cov(--p);
    }
    for(rg int i=1;i<=m;++i) write1(ans[i]),putchar('\n');
    return 0;
}