各种莫队算法

[bzoj2648]小 $Z$ 的袜子——普通莫队

题目大意

给出一个有 $n$ 个数的数列 $A : a_{1}, a_{2}, a_{3} \dots a_{n}$ ，询问 $m$ 次

每次询问给出一个区间 $[l, r]$ ，询问区间 $[l, r]$ 内抽到一对数值相等的数的概率大小

数据范围

$n, m ⩽ 50000$ ， $1 ⩽ l < r ⩽ n$ ， $a_{i} ⩽ n$

题解

不妨设区间 $[l, r]$ 里元素个数为 $l e n$ ，显然，抽一对数的情况总数为 $C_{l e n}^{2}$

同时区间里只有 $k$ 种数值，每种数值对应的元素有 $s_{1}, s_{2} \dots s_{k}$ 个，抽一对数值相等的数的情况总数为 $C_{s_{1}}^{2} + C_{s_{2}}^{2} + \dots C_{s_{k}}^{2}$

则答案为 $\frac{C_{s_{1}}^{2} + C_{s_{2}}^{2} + \dots C_{s_{k}}^{2}}{C_{l e n}^{2}} = \frac{s_{1} (s_{1} - 1) + s_{2} (s_{2} - 1) + \dots s_{k} (s_{k} - 1)}{l e n (l e n - 1)} = \frac{s_{1}^{2} + s_{2}^{2} + \dots s_{k}^{2} - l e n}{l e n (l e n - 1)}$

那么现在问题简化为，如何即时地统计所有的 $s_{1}, s_{2} \dots s_{k}$

这个时候引入一个东西，莫队算法，是莫涛前几年提出的算法，适用于解决离线区间查询问题

Question Ⅰ：这个算法怎么用啊？

假设已经得到了区间 $[l, r]$ 需要统计的信息，可以在常数级别的时间内转移到区间 $[l - 1, r]$ 、区间 $[l + 1, r]$ 、区间 $[l, r - 1]$ 、区间 $[l, r + 1]$

那么可以在 $O (n \sqrt{n})$ 的时间复杂度求得所有答案

Question Ⅱ：这个时间复杂度？

我们可以调整一下处理每个查询的顺序，保证最优的顺序之下转移区间

将 $n$ 个数分成 $\sqrt{n}$ 块

按区间排序，以左端点所在块内为第一关键字，右端点为第二关键字，进行排序

然后按这个排序直接暴力，复杂度分析是这样的：

$i$ 与 $i + 1$ 在同一块内， $r$ 单调递增，所以 $r$ 是 $O (n)$ 的，由于有 $\sqrt{n}$ 块，所以这一部分时间复杂度是 $n \sqrt{n}$

$i$ 与 $i + 1$ 跨越一块， $r$ 最多变化 $n$ ，由于有 $\sqrt{n}$ 块，所以这一部分时间复杂度是 $n \sqrt{n}$

$i$ 与 $i + 1$ 在同一块内， $l$ 变化不超过 $\sqrt{n}$ ，跨越一块也不会超过 $\sqrt{n} \times 2$

由于有 $m$ 次询问（和 $n$ 同级），所以时间复杂度是 $n \sqrt{n}$

代码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cctype>
#include<algorithm>
#define ll long long
#define For(i,l,r) for(int i=l;i<=r;++i)
#define Ford(i,r,l) for(int i=r;i>=l;--i)
inline int read(){
    int x=0;char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
    return x;
}
using namespace std;

int n,m,size;
struct data{int l,r,id;long long up,down;}q[50050];
int a[50050],belong[50050]; 
ll ans,s[50050];
inline bool cmp1(data x,data y) {return belong[x.l]==belong[y.l]?x.r<y.r:x.l<y.l;}
inline bool cmp2(data x,data y) {return x.id<y.id;}
inline ll gcd(ll x,ll y){return y==0?x:gcd(y,x%y);}

inline void update(int x,int c){
    ans-=s[x]*s[x];
    s[x]+=(ll)c;
    ans+=s[x]*s[x];
}

int main(){
    n=read(),m=read();
    For(i,1,n) a[i]=read();
    For(i,1,m) q[i]=(data){read(),read(),i};

    size=(int)sqrt(n);
    For(i,1,n) belong[i]=(i-1)/size+1;
    sort(q+1,q+m+1,cmp1);

    int l=1,r=0;
    For(i,1,m){
        for(;r<q[i].r;r++) update(a[r+1],1);
        for(;r>q[i].r;r--) update(a[r],-1);
        for(;l<q[i].l;l++) update(a[l],-1);
        for(;l>q[i].l;l--) update(a[l-1],1);
        if (q[i].l==q[i].r){
            q[i].up=0;q[i].down=1;
            continue;
        }
        ll len=q[i].r-q[i].l+1;
        q[i].up=ans-len,q[i].down=(len-1)*len;
        ll g=gcd(q[i].up,q[i].down);
        q[i].up/=g,q[i].down/=g;
    }
    sort(q+1,q+m+1,cmp2);
    For(i,1,m) printf("%lld/%lld\n",q[i].up,q[i].down);
    return 0;
}

[bzoj2120]数颜色——带修改莫队

题目大意

有 $n$ 支彩色画笔（颜色可能相同）排成一排，有 $m$ 次操作

询问在 $[l, r]$ 中共有几种颜色不同的画笔
把其中一只画笔替换为别的颜色的画笔

数据范围

$n ⩽ 10000, m ⩽ 10000$

所有画笔的颜色表示为 $1 ⩽ c [i] ⩽ 10^{6}$

题解

以前做这道题的时候想过用分块去做，具体戳分块题解

其实这道题除了分块，也可以想想莫队的思路

思考熊

Question Ⅲ：查询操作的区间还是要调整成最优区间，那么修改操作的顺序就会被打乱，怎么解决？

对于每一个查询操作，我们记录在它之前最近的修改操作的编号，维护两个时间段之间的修改操作

就是对于现在的这个查询，在它之后执行过的修改操作改回去，在它之前没执行的修改就执行

Question Ⅳ：这个时间复杂度？

排序方法：设定块的长度为 $S_{1}$ 和 $S_{2}$ ，按照 $(⌊ \frac{l}{S_{1}} ⌋, ⌊ \frac{r}{S_{2}} ⌋, t)$ 的三元组小到大排序，其中 $t$ 表示这个询问的时刻之前经历过了几次修改操作

复杂度分析：考虑询问序列中的每个小块，小块内每个询问的一二关键字相同

在这个小块内，显然 $t$ 最多变化 $m$ ，对于每个询问， $l, r$ 最多变化 $S_{1}$ 和 $S_{2}$ ，一共有 $\frac{n^{2}}{S_{1} S_{2}}$ 个这样的块，相邻块之间转移的复杂度为 $O (n)$ ，总复杂度就是 $O (m S_{1} + m S_{2} + \frac{n^{2} m}{S_{1} S_{2}} + \frac{n^{2} m}{S_{1} S_{2}})$

不妨设 $n, m$ 同阶，取 $S_{1} = S_{2} = n^{\frac{2}{3}}$ 时可达到最优复杂度 $O (n^{\frac{5}{3}})$

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cctype>
#include<algorithm>
#define ll long long
#define For(i,l,r) for(int i=l;i<=r;++i)
#define Ford(i,r,l) for(int i=r;i>=l;--i)
inline int read(){
    int x=0;char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
    return x;
}
using namespace std;

int n,m,cnt_r,cnt_q;
struct revise{int pos,col,pre;}c[1050];
struct query{int l,r,id,time;}q[10050];
int belong[10050],last[10050];
int colour[1000500],num[1000500],vis[10050];
int ans[10050],sum;
inline bool cmp(query a,query b){return belong[a.l]==belong[b.l]?a.r<b.r:belong[a.l]<belong[b.l];}

inline void cal(int x){
    if (vis[x]){
        num[colour[x]]--;
        if (num[colour[x]]==0) sum--;
    }
    else{
        if (num[colour[x]]==0) sum++;
        num[colour[x]]++;
    }
    vis[x]^=1;
}
inline void change(int x,int c){
    if (vis[x]){
        cal(x);
        colour[x]=c;
        cal(x);
    }
    else colour[x]=c;
}

int main(){
    n=read(),m=read();
    For(i,1,n) colour[i]=last[i]=read();
    For(i,1,m){
        char ch[5];scanf("%s",ch);
        int x=read(),y=read();
        if (ch[0]=='R') c[++cnt_r]=(revise){x,y,last[x]},last[x]=y;
        else q[++cnt_q]=(query){x,y,cnt_q,cnt_r};
    }

    int size=ceil(pow(cnt_q,2.0/3));
    For(i,1,cnt_q) belong[i]=(i-1)/size+1;
    sort(q+1,q+cnt_q+1,cmp);
    int l=1,r=0;
    For(i,1,cnt_q){
        for (int j=q[i-1].time+1;j<=q[i].time;j++) change(c[j].pos,c[j].col);
        for (int j=q[i-1].time;j>=q[i].time+1;j--) change(c[j].pos,c[j].pre);
        for (;r<q[i].r;r++) cal(r+1);
        for (;r>q[i].r;r--) cal(r);
        for (;l<q[i].l;l++) cal(l);
        for (;l>q[i].l;l--) cal(l-1);
        ans[q[i].id]=sum;
    }

    For(i,1,cnt_q) printf("%d\n",ans[i]);
}

[bzoj3757]苹果树——树上无修改莫队

题目大意

有一棵有 $n$ 个节点的树，执行 $m$ 次询问，每个点有一种颜色

每次询问 $u$ 到 $v$ 路径上把颜色 $a$ 和颜色 $b$ 当作同一种颜色后路径上不同颜色的数目

数据范围

$n ⩽ 5 \times 10^{4}, m ⩽ 10^{5}$

题解

参考：https://blog.sengxian.com/algorithms/mo-s-algorithm

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cctype>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
#define N 50500
using namespace std;
inline int read(){
    int x=0;char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
    return x;
}

int n,m,block,root,et,cnt,tot,top,ans;
struct edge{int to,next;}e[2*N];
struct data{int u,v,a,b,id;}q[2*N];
int last[N],bin[25];
int dfn[N],deep[N],belong[N],st[N],fa[N][25];
int c[N],sum[N],vis[N],result[2*N];

inline bool cmp(data x,data y){
    return belong[x.u]==belong[y.u]?dfn[x.v]<dfn[y.v]:belong[x.u]<belong[y.u];
}
inline void addedge(int u,int v){
    e[++et]=(edge){v,last[u]};last[u]=et;
    e[++et]=(edge){u,last[v]};last[v]=et;
}
inline int lca(int u,int v){
    if (deep[u]<deep[v]) swap(u,v);
    int t=deep[u]-deep[v];
    for(int i=0;bin[i]<=t;i++)
        if (t&bin[i]) u=fa[u][i];
    for(int i=16;i>=0;i--)
        if (fa[u][i]!=fa[v][i])
            u=fa[u][i],v=fa[v][i];
    if (u==v) return u;
    return fa[u][0];
}

int dfs(int x){
    int size=0;
    dfn[x]=++cnt;
    For(i,1,16){
        if (deep[x]>=bin[i]) 
            fa[x][i]=fa[fa[x][i-1]][i-1];
        else break;
    }
    goedge(i,x){
        if (e[i].to==fa[x][0]) continue;
        deep[e[i].to]=deep[x]+1;
        fa[e[i].to][0]=x;
        size+=dfs(e[i].to);
        if (size>block){
            tot++;
            For(i,1,size) belong[st[top--]]=tot;
            size=0;
        }
    }
    st[++top]=x;
    return size+1;
}

inline void reverse(int x){
    if (!vis[x]) {vis[x]=1;sum[c[x]]++;if (sum[c[x]]==1) ans++;}
    else {vis[x]=0;sum[c[x]]--;if (sum[c[x]]==0) ans--;}
}

inline void solve(int u,int v){
    while (u!=v){
        if (deep[u]>deep[v]) reverse(u),u=fa[u][0];
        else reverse(v),v=fa[v][0];
    }
}

int main(){
    bin[0]=1;For(i,1,20) bin[i]=bin[i-1]<<1;
    n=read(),m=read();
    For(i,1,n) c[i]=read();
    For(i,1,n){
        int u=read(),v=read();
        if (!u) root=v;
        else if (!v) root=u;
        else addedge(u,v);
    }

    block=sqrt(n);
    dfs(root);
    tot++;
    while (top) belong[st[top--]]=tot;

    For(i,1,m){
        q[i]=(data){read(),read(),read(),read(),i};
        if (dfn[q[i].u]>dfn[q[i].v]) swap(q[i].u,q[i].v);
    }
    sort(q+1,q+m+1,cmp);

    int h=lca(q[1].u,q[1].v);
    solve(q[1].u,q[1].v);
    reverse(h);
    result[q[1].id]=ans;
    if (sum[q[1].a] && sum[q[1].b] && q[1].a!=q[1].b) 
        result[q[1].id]--;
    reverse(h);

    For(i,2,m){
        solve(q[i-1].u,q[i].u);
        solve(q[i-1].v,q[i].v);
        int h=lca(q[i].u,q[i].v);
        reverse(h);
        result[q[i].id]=ans;
        if (sum[q[i].a] && sum[q[i].b] && q[i].a!=q[i].b)
            result[q[i].id]--;
        reverse(h);
    }

    For(i,1,m) printf("%d\n",result[i]);
    return 0;
}

zgjkt的博客

博客

[bzoj2648]小 $Z$ 的袜子——普通莫队

题目大意

数据范围

题解

代码

[bzoj2120]数颜色——带修改莫队

题目大意

数据范围

题解

程序

[bzoj3757]苹果树——树上无修改莫队

题目大意

数据范围

题解

程序

评论

发表评论

zgjkt的博客

博客