【Codeforces 763E】Timofey and our friends animals | Mrsrz's blog

回滚莫队，可撤销并查集。

题目大意：

给定 $n$ 个点，每个点只可能和其左右距离不超过 $k$ 的点有边相连。

有多组询问，每次给定 $l,r$，问只保留 $l\sim r$ 的点以及边的情况下，有多少连通块。

题解：

$10^5$ 还给了 $7$ 秒，那我应该想都不想直接莽回滚莫队才对啊……

好像有个非常短的做法能过但貌似是假的？

既然回滚莫队能跑那就写啊。

大概就是对序列分块，将左端点在一个块里的询问放到一起处理。

处理一个块的询问的时候，按照右端点排序，然后处理每个询问的时候，先移动右端点，并更新并查集。然后移动左端点到目标位置。

处理完一个询问后，立即将左端点的位置还原。使用可撤销并查集实现按顺序撤销的操作。

时间复杂度 $O(n\sqrt n\log n)$。

实际上好像最慢的点也才 $1\texttt s$。

Code：

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define bel(x)((x-1)/siz+1)
const int N=1e5+5,siz=400;
int fa[N],sz[N],ans[N],k,n,m,t;
bool Lf[N][5],Rg[N][5];
inline int Find(int x){while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;}
inline int find(int x){while(x!=fa[x])x=fa[x];return x;}
struct que{
    int l,r,id;
    inline bool operator<(const que&rhs)const{return r<rhs.r;}
};
vector<que>vec[500];
int sta[N*10],top; 
void work(int l,int r,int id){
    int s=r-l+1;
    for(int i=l;i<=r;++i)
    for(int j=0;j<k&&i+j<r;++j)if(Rg[i][j]){
        int x=Find(i),y=Find(i+j+1);
        if(x!=y){
            --s;
            if(sz[x]<sz[y])fa[x]=y,sz[y]+=sz[x];else fa[y]=x,sz[x]+=sz[y];
        }
    }
    ans[id]=s;
    for(int i=l;i<=r;++i)fa[i]=i,sz[i]=1;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)fa[i]=i,sz[i]=1;
    scanf("%d",&t);
    while(t--){
        int u,v;
        scanf("%d%d",&u,&v);
        if(u>v)u^=v^=u^=v;
        Rg[u][v-u-1]=Lf[v][v-u-1]=1;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;++i){
        int l,r;
        scanf("%d%d",&l,&r);
        if(r-l+1<=1000)work(l,r,i);else
        vec[bel(l)].push_back((que){l,r,i});
    }
    for(int V=1;V<400;++V)if(!vec[V].empty()){
        for(int i=1;i<=n;++i)fa[i]=i,sz[i]=1;
        sort(vec[V].begin(),vec[V].end());
        int r=V*siz,s=0;
        for(que q:vec[V]){
            while(r<q.r){
                ++r;
                for(int j=0;j<k&&r-j-1>=V*siz;++j)
                if(Lf[r][j]){
                    int x=find(r),y=find(r-j-1);
                    if(x!=y){
                        ++s;
                        if(sz[x]<sz[y])fa[x]=y,sz[y]+=sz[x];else fa[y]=x,sz[x]+=sz[y];
                    }
                }
            }
            int nw=s;top=0;
            for(int l=V*siz-1;l>=q.l;--l)
            for(int j=0;j<k;++j)if(Rg[l][j]){
                int x=find(l),y=find(l+j+1);
                if(x!=y){
                    ++s;
                    if(sz[x]<sz[y])swap(x,y);
                    sta[++top]=y,fa[y]=x,sz[x]+=sz[y];
                }
            }
            ans[q.id]=q.r-q.l+1-s,s=nw;
            for(int i=top;i;--i){
                int x=sta[i];
                sz[fa[x]]-=sz[x],fa[x]=x;
            }
        }
    }
    for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
    return 0;
}