首页 > 其他分享 >P8026 [ONTAK2015] Bajtocja & 杭电多校2 L.图计算

P8026 [ONTAK2015] Bajtocja & 杭电多校2 L.图计算

时间:2024-08-09 10:50:00浏览次数:17  
标签:联通 pt int Bajtocja ONTAK2015 P8026 ncol siz tcol

题目传送门1

题目传送门2

题意

洛谷那题比较简明,就是多张图(\(d \leq 200\)),每次给某张图加一条边,询问加完后有多少点对在所有图都联通。

题解

翻了很多题解都是用的hash做法,具体而言就是如果两个点在某张图联通,那么他们在该图并查集有相同根节点。将每个点在所有图的根节点构成一个字符串,只有字符串相同时,两个点才能在所有图都联通, 用hash解决。 其实很聪明,但我在没看过原题的情况下确想不出,赛时写了一个离线反着删边的做法,现在在洛谷是最优解,不过理论复杂度应该一样?

所以来一个非哈希的题解吧:我们考虑先把所有边建好,再反着删除边,这样做的好处是,如果你正着加边,需要所有图中都联通才能联通。而反着删除边,只要一个图被割裂就割裂了。

这是一个出发点,但实际情况比较复杂,我们如何删除一条边呢?考虑加边时,如果一条边连接的两个点已经联通,那么这条边加入是无意义的,因为反删除时这条边反而会提前删除。所以在按秩合并下,所有有意义的加边构成一颗树,图边和并查集树边一一对应,问题在于当你断开一条树边时,原来的树被分成两颗子树,但这两颗子树中的某些点对可能之前就在其他并查集树上被隔离了,所以你不好直接去统计答案。

这时候你容易发现,由于启发式合并的复杂度,你可以允许在删除一条边将树一分为二时,遍历小的那一颗子树。(读自证)但我们还不知道能用这个复杂度做些什么。

我们考虑加完所有边之后,暴力的跑一遍答案,这时候我们就得到了所有图的共有联通块集合,每一个联通块在所有图都是联通的,并且每一个点都属于一个共有联通块(再不济它自己也能构成一个连通块)。

我们考虑删边的同时维护这个连通块集合,每次删边时,一颗并查集树一分为二棵子树,对于连通块集合中的任意一个联通块,要么不在这颗树上没影响,要么连通块的点都在其中一颗子树上,仍然联通没影响。最后就是有影响的情况,这个联通块的点分布在两颗子树上,删边会将其一分为二(这里其实就是反着做,一个联通块只要在一个图被分开就被分开了的优点)。

这样我们遍历小的那颗子树,对于其中每一个点所在的连通块,如果都在这颗子树上则不管,否则还有大子树的部分,但由于我们维护了每个联通块的总大小,知道小子树的部分也就知道了大子树部分,直接一分为二就可以,并且统计答案,还是只用枚举小子树就行。

复杂度我不太会算,一个上界应该是\(nd \ log (nd)\),足以通过, 但实际由于总操作次数是m级别的,我也不太会算。

btw,虽然赛时代码很烂,但洛谷上是最优解(

实现

赛时代码完全看不了,因为很多细节是边写边考虑的,变量名完全不知道叫什么乱取。。。。。

所以稍微讲一下实现把,代码之所以这么烂,主要是最后建完边之后求并查集的交集那里搞得太复杂了,因为启发式和并你不能很好的清空数组,每次你只能遍历一遍清空,再遍历一遍计算,然后这交集也不算好求把,就写太烂了,读者可以教博主怎么更好的去求这个东西。 我这里是对于并查集的每一个联通块, 考虑它在另一个并查集的中的分布,对于分布相同的就连接起来。

#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <tuple>
#define ll long long
#define edge tuple<int, int, int> 
using namespace std;

int read(){
    int num=0, flag=1; char c=getchar();
    while(!isdigit(c) && c!='-') c=getchar();
    if(c == '-') flag=-1, c=getchar();
    while(isdigit(c)) num=num*10+c-'0', c=getchar();
    return num*flag;
}

const int N = 5e4+20;
const int M = 110;

int T;
int n, m, d, q;


struct Tree{
    int fa[N], dep[N];
    vector<int> son[N];
    void clear(){
        for(int i=1; i<=n; i++) fa[i]=i, dep[i]=1;
        for(int i=1; i<=n; i++) son[i].clear();
    }
    int find(int x){
        while(fa[x] != x) x = fa[x];
        return x;
    }
    void merge(int u, int v){
        u=find(u), v=find(v);
        if(u == v) return ;
        if(dep[u] > dep[v]) swap(u, v);
        fa[u] = v;
        son[v].push_back(u);
        dep[v] = max(dep[v], dep[u]+1);
    }
}t[M];
int root = M-3;
int lroot = (root ^ 1);
vector<edge > Q; 
int vis[N];

int col[N], siz[N];
int cnt = 0;
int ctc[N];
ll res[110000];
int qid[110000];

vector<int> tp[N];
vector<int> pt[N];
vector<int> pp;

void dfs(int x, int w){
    pp.push_back(x);
    for(int nex : t[w].son[x]){
        if(t[w].fa[nex] == x)
            dfs(nex, w);
    }
}

void solve(){
    ll ans = 0;
    
    n=read(), m=read(), d=read()+1, q=read();
    {
        Q.clear();
        t[root].clear();
        for(int i=1; i<=n; i++) siz[i] = 0;
        for(int i=1; i<=d; i++) t[i].clear();
        
        for(int i=1; i<=q; i++) res[i]=-1;
    }

    for(int i=1; i<=m; i++){
        int u=read(), v=read();
        for(int j=1; j<=d; j++){
            if(t[j].find(u) != t[j].find(v)){
                t[j].merge(u, v);
            }
        }
    }

    for(int i=1; i<=q; i++){
        int u=read(), v=read(), w=read();
        u=t[w].find(u), v=t[w].find(v);
        if(u == v) continue;

        Q.push_back((edge){u, v, w}); 
		qid[Q.size()-1] = i;
        t[w].merge(u, v);
    }

    for(int i=1; i<n; i++) t[root].merge(i, i+1); 

    
    for(int id=1; id<=d; id++){
        lroot = (root ^ 1);
        t[lroot].clear();

        for(int i=1; i<=n; i++) pt[i].clear();
        for(int i=1; i<=n; i++) pt[t[id].find(i)].push_back(i);
        
        for(int i=1; i<=n; i++){
            for(int x : pt[i]){
                int fa = t[root].find(x);
                vis[fa] = 0;
                tp[fa].clear();
            }

            for(int x : pt[i]){
                int fa = t[root].find(x);
                tp[fa].push_back(x);
            }

            for(int x : pt[i]){
                int fa = t[root].find(x);
                if(vis[fa]++) continue;
                
                for(int j=0; j+1<tp[fa].size(); j++){
                    t[lroot].merge(tp[fa][j], tp[fa][j+1]);
                }
            }
        }
    
        swap(root, lroot);
    }

    // for(int i=1; i<=n; i++) pt[i].clear();
    cnt = 0;
    for(int i=1; i<=n; i++) ctc[i] = 0;

    for(int i=1; i<=n; i++){
        col[i] = t[root].find(i);
        if(ctc[col[i]] == 0) ctc[col[i]] = ++cnt;

        col[i] = ctc[col[i]];
        siz[col[i]]++;        
    }

    for(int i=1; i<=n; i++) ans += 1ll*siz[i]*siz[i];
	
	res[q+1] = ans;

    for(int id=((int)Q.size())-1; id>=0; id--){
        int u=get<0>(Q[id]), v=get<1>(Q[id]), w=get<2>(Q[id]);

        if(t[w].fa[u] != v) swap(u, v);
        t[w].fa[u]  = 0;
        pp.clear();
        dfs(u, w);

        for(int x : pp){
            vis[x] = 0;
            pt[col[x]].clear();
        }
        for(int x : pp){
            pt[col[x]].push_back(x);
        }
        for(int x : pp){
            if(vis[x]) continue;
            int tcol = col[x];
            for(int y : pt[tcol]) vis[y] = 1;  

            if(pt[tcol].size() ==  siz[tcol]) continue;

            int ncol = ++cnt;
            siz[ncol] = 0;
            for(int y : pt[tcol]){
                col[y] = ncol;
                siz[ncol]++;
            }

            ans -= 1ll*siz[tcol]*siz[tcol];
            siz[tcol] -= siz[ncol];
            ans += 1ll*siz[ncol]*siz[ncol] + 1ll*siz[tcol]*siz[tcol];
        }
        
//        printf("%lld\n", (ans-n)/2);
		res[qid[id]] = ans;

    }

    for(int i=q; i>=1; i--) {
    	if(res[i] == -1) res[i] = res[i+1];
	} 
	for(int i=1; i<=q; i++) printf("%lld\n", (res[i+1]-n)/2);
}

int main(){
    T = read();
    while(T--){
        solve();

    }
    return 0;   
}

标签:联通,pt,int,Bajtocja,ONTAK2015,P8026,ncol,siz,tcol
From: https://www.cnblogs.com/ltdjcoder/p/18348544

相关文章

  • P8026 [ONTAK2015] Bajtocja
    P8026[ONTAK2015]Bajtocja题目描述给定d张无向图,每张图都有n个点。一开始,在任何一张图中都没有任何边。接下来有m次操作,每次操作会给出a,b,k,意为在第k张图中的点a和点b之间添加一条无向边。你需要在每次操作之后输出有序数对(a,b)的个数,使得1≤a,b≤n,且a点......
  • P8026 [ONTAK2015] Bajtocja 做题笔记
    题目链接一道好题,本来是做几道启发式合并玩玩,没想到是个哈希。这一道题需要维护连通性,显然想到使用并查集。如果两个点在某个图内的父亲相同,显然这两个点就连通了。但是如果每链接一对点我们就遍历所有点对然后判断父亲,显然爆炸。于是考虑借鉴一下CSP2022T3的思路,对于每......
  • P8026 『JROI-7』hibernal 做题笔记
    题目链接观察数据,要求询问次数不超过$\lceil2\logn\rceil-1$,相当困难。我刚开始也在想二分,但这个东西并不具有单调性,但这个题具有的特点就是你不仅仅可以询问一个前缀,你还可以询问任意的集合。首先发现如果能将$n$个苹果分成$S_1$$S_2$两个长度接近的集合,且$S_1$和$S......