HihoCoder - 1629//2017 ICPC 北京C 回滚莫队 + 回滚并查集

古城微笑少年丶 2023-10-11 13:28 44阅读 0赞

静态无修又是连续,模拟赛的时候很快就想到了莫队 + 回滚并查集

但是众所周知并查集并不支持删除操作，回滚并查集也只能按顺序删除

赛后得知有一个叫做回滚莫队的操作，即将左端点按照块排序，相同的块按照右端点从小到大排序

然后将所有左端点相同的块一起处理，因为右端点递增所以右端点很显然只有插入操作，

对于左端点来说，每次查询都回退到当前块的最右端，然后查询的时候向左插入，避开了原本的删除操作

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #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;
    int read(){
        int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
        if (c == '-') f = -1;c = getchar();}
    while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
    const double PI = acos(-1.0);
    const double eps = 1e-9;
    const int maxn = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7; 
    int N,M,Q;
    struct Edge{
        int to,next;
    }edge[maxn * 2];
    int head[maxn],tot,unit;
    void init(){
        for(int i = 0 ; i <= N; i ++) head[i] = -1;
        tot = 0;
    }
    void add(int u,int v){
        edge[tot].to = v;
        edge[tot].next = head[u];
        head[u] = tot++;
    }
    LL fac[maxn];
    struct Query{
        int l,r;
        int id;
    }query[maxn * 2];
    int belong[maxn];
    bool cmp(Query a,Query b){
        if(belong[a.l] == belong[b.l]) return a.r < b.r;
        return belong[a.l] < belong[b.l];
    }
    LL Sum,L,R;
    int fa[maxn],size[maxn],sz[maxn];
    int Stack[maxn],top;
    void Init(){
        for(int i = 1; i <= N ; i ++){
            fa[i] = -1; size[i] = 0; sz[i] = 1;
        }
        top = 0;
    }
    int find(int x){
        while(fa[x] != -1) 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] + 1;
        Sum -= fac[sz[y]]; Sum -= fac[sz[x]];
        sz[y] += sz[x]; Sum += fac[sz[y]];
        return true;
    }
    void rewind(int t){
        while(top > t){
            int x = Stack[--top];
            size[fa[x]] -= size[x] + 1;
            sz[fa[x]] -= sz[x];
            fa[x] = -1;
        }
    }
    void add(int p){
        for(int i = head[p]; ~i ; i = edge[i].next){
            int v = edge[i].to;
            if(L <= v && v <= R) Union(v,p);
        }
    }
    
    int tree[maxn],Sz[maxn];
    int Find(int x){
        if(x != tree[x]) return tree[x] = Find(tree[x]);
        return x;
    }
    LL cul(int l,int r){
        LL sum = 0;
        for(int i = l; i <= r; i ++){
            tree[i] = i; Sz[i] = 1;
        } 
        for(int i = l ; i <= r; i ++){
            for(int j = head[i]; ~j ; j = edge[j].next){
                int v = edge[j].to;
                if(l <= v && v <= r){
                    int u = Find(i);
                    v = Find(v);
                    if(u != v){
                        tree[u] = v;
                        Sz[v] += Sz[u];
                    }
                }
            }
        }
        for(int i = l; i <= r; i ++){
            int v = Find(i);
            if(i == v) sum += fac[Sz[i]];
        } 
        return sum;
    }
    LL ans[maxn];
    void solve(){
        int up = N / unit;
        int j = 1; Init();
        for(int i = 0 ; i <= up; i ++){
            Sum = 0;
            L = (i + 1) * unit,R = L - 1;
            LL la,normal = L;
            for(;j <= Q && belong[query[j].l] == i; j ++){
                if(belong[query[j].r] == i){
                    ans[query[j].id] = cul(query[j].l,query[j].r);
                    continue;
                }
                while(R < query[j].r) add(++R);
                la = Sum; int tmp = top;
                while(L > query[j].l) add(--L);
                ans[query[j].id] = Sum;
                L = normal; rewind(tmp);
                Sum = la;
            }
            rewind(0);
            //cout << top << endl;
        }
    }
    int main(){
        int T; Sca(T);
        for(LL i = 0; i < maxn; i ++) fac[i] = i * (i - 1) / 2;
        while(T--){
            Sca3(N,M,Q); init(); unit = (int)sqrt(N);
            for(int i = 1; i <= M ; i ++){
                int u,v; Sca2(u,v);
                add(u,v); add(v,u);
            }
            for(int i = 1; i <= N ; i ++) belong[i] = i / unit;
            for(int i = 1; i <= Q; i ++){
                query[i].l = read();
                query[i].r = read();
                query[i].id = i;
            }
            sort(query + 1,query + 1 + Q,cmp);
            solve();
            for(int i = 1; i <= Q; i ++) Prl(ans[i]);
        } 
        return 0;
    }

转载于:https://www.cnblogs.com/Hugh-Locke/p/11385334.html