bzoj3237 cdq分治+可撤销并查集

时间：2021-05-09 05:11:47

https://www.lydsy.com/JudgeOnline/problem.php?id=3237

年轻的花花一直觉得cdq分治只能用来降维，不料竟然可以用来分治询问

bzoj3237 cdq分治+可撤销并查集

N<=100000 M<=200000 K<=100000

判断图联通的方法有很多，一般来说这样的题很容易想到用并查集来判断，但是我们不可能用出每一个询问都对整个图跑一边并查集这样愚蠢的方法，对于这样大量询问的题目来说，首先是想到去预处理，但是冷静分析之后发现并查集并不能预处理出什么奥妙重重指点*的东西来，所以需要反手考虑一波离线的做法，这里每一个询问虽然是相互独立的，但是我们想到如果能产生一个删边的操作出来，删去上一个询问的边再加上下一个询问的边就好了，虽然并查集并不带有删边的操作，但是想到可撤销的并查集按顺序撤销上面的加边操作，那么如果我们将除了两个集合之外所有边权都加上，按顺序加上a集合的边就可以得到b的答案，这时候撤销a的边加上b的边就可以得到a的答案，我们思来想去，会发现cdq分治恰好就是我们要找的算法。

首先对没有存在集合的边进行缩点

我们对一段区间分为几个步骤。

1 加上所有左边集合里不存在的边

2.处理左边区间.

3.回撤,删去刚刚加上的的边

4.加上所有右边集合里不存在的边.

5.处理右边区间.

6.回撤,删去刚刚加上的边.

这么一波操作下来,就满足我们上述的所有东西了,对于每一个询问,不需要暴力的操作,可以由已经进行过的操作推倒

#include <map>

#include <set>

#include <ctime>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

inline int read(){int now=;register char c=getchar();for(;!isdigit(c);c=getchar());

for(;isdigit(c);now=now*+c-'',c=getchar());return now;}

#define For(i, x, y) for(int i=x;i<=y;i++)

#define _For(i, x, y) for(int i=x;i>=y;i--)

#define Mem(f, x) memset(f,x,sizeof(f))

#define Sca(x) scanf("%d", &x)

#define Sca2(x,y) scanf("%d%d",&x,&y)

#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define Scl(x) scanf("%lld",&x);

#define Pri(x) printf("%d\n", x)

#define Prl(x) printf("%lld\n",x);

#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();

#define LL long long

#define ULL unsigned long long

#define mp make_pair

#define PII pair<int,int>

#define PIL pair<int,long long>

#define PLL pair<long long,long long>

#define pb push_back

#define fi first

#define se second

typedef vector<int> VI;

const double eps = 1e-;

const int maxn = 1e5 + ;

const int maxm = 2e5 + ;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + ;

int N,M,K;

struct Edge{

    int u,v;

}edge[maxm];

int Stack[maxn],size[maxn];

int fa[maxn],top;

bool vis[maxm];

VI S[maxn];

int ans[maxn],now;

void init(){

    Mem(fa,-);

    Mem(size,);

    top = ;

}

int find(int x){

    while(fa[x] != -) x = fa[x];

    return x;

}

bool Union(int x,int y){

    x = find(x); y = find(y);

    if(x == y) return false;

    if(size[x] > size[y]) swap(x,y);

    Stack[top++] = x;

    fa[x] = y;

    size[y] += size[x] + ;

    now--;

    return true;

}

void rewind(int t){

    while(top > t){

        int x = Stack[--top];

        size[fa[x]] -= size[x] + ;

        fa[x] = -;

        now++;

    }

}

void cdq(int l,int r){

    if(l == r){

        ans[l] = (now == );

        return;

    }

    int t = top;

    int m = (l + r) >> ;

    For(i,l,m){

        For(j,,S[i].size() - ){

            vis[S[i][j]] = ;

        }

    }

    For(i,m + ,r){

        For(j,,S[i].size() - ){

            if(!vis[S[i][j]]) Union(edge[S[i][j]].u,edge[S[i][j]].v);

        }

    }

    For(i,l,m){

        For(j,,S[i].size() - ){

            vis[S[i][j]] = ;

        }

    }

    cdq(l,m);

    rewind(t);

    For(i,m + ,r){

        For(j,,S[i].size() - ){

            vis[S[i][j]] = ;

        }

    }

    For(i,l,m){

        For(j,,S[i].size() - ){

            if(!vis[S[i][j]]) Union(edge[S[i][j]].u,edge[S[i][j]].v);

        }

    }

    For(i,m + ,r){

        For(j,,S[i].size() - ){

            vis[S[i][j]] = ;

        }

    }

    cdq(m + ,r);

    rewind(t);

}

int main()

{

    Sca2(N,M); init();

    For(i,,M){

        edge[i].u = read(); edge[i].v = read();

    }

    now = N;

    Sca(K);

    For(i,,K){

        int t = read();

        while(t--){

            int x = read();

            S[i].pb(x); vis[x] = ;

        }

    }

    For(i,,M){

        if(!vis[i]) Union(edge[i].u,edge[i].v);

        vis[i] = ;

    }

    top = ;

    cdq(,K);

    For(i,,K){

        if(ans[i]) puts("Connected");

        else puts("Disconnected");

    }

    #ifdef VSCode

    system("pause");

    #endif

    return ;

}

相关文章