2733: [HNOI2012]永無鄉

題意：加邊，詢問一個連通塊中k小值

---

終于寫了一下splay啟發式合并
本題直接splay上一個節點對應圖上一個點就可以了
并查集維護連通性
合并的時候，把size小的樹的所有節點插入到size大的中，每個點最多插入log次，復雜度\(O(nlogn*insert\ time)\)
然后主席說如果按照順序插入，插入的復雜度均攤\(O(1)\)，總的復雜度\(O(nlogn)\)，隨便中序遍歷一下就有序了.貌似并沒有更快

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; #define lc t[x].ch[0] #define rc t[x].ch[1] #define pa t[x].fa const int N=1e5+5; inline int read(){char c=getchar();int x=0,f=1;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; }int n, m, val[N], x, y, Q; char s[5]; int fa[N]; inline int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);} struct SplayTree{struct meow{int ch[2], fa, size, v;}t[N];int sz, root;inline void ini() {for(int i=1; i<=n; i++) t[i].v=val[i], t[i].size=1;}inline int wh(int x) {return t[pa].ch[1] == x;}inline void update(int x) {t[x].size = t[lc].size + t[rc].size + 1;}inline void rotate(int x) {int f=t[x].fa, g=t[f].fa, c=wh(x);if(g) t[g].ch[wh(f)]=x; t[x].fa=g;t[f].ch[c] = t[x].ch[c^1]; t[t[f].ch[c]].fa=f;t[x].ch[c^1]=f; t[f].fa=x;update(f); update(x);}inline void splay(int x, int tar) {for(; pa!=tar; rotate(x))if(t[pa].fa != tar) rotate(wh(x)==wh(pa) ? pa : x);if(tar==0) root=x;}inline void insert(int p) { int x=root, f=0, v=t[p].v; while(x) f=x, x= v<t[x].v ? lc : rc;x=p; t[f].ch[v>t[f].v]=x; t[x].fa=f; splay(x, 0);}int q[N], p;void order(int x) {int l=lc, r=rc;lc=rc=pa=0; t[x].size=1;if(l) order(l);insert(x);if(r) order(r);}void Merge(int x, int y) {if(x==y) return;splay(x, 0); splay(y, 0);if(t[x].size > t[y].size) swap(x, y); fa[x]=y; root=y;order(x);}int kth(int x, int k) { splay(x, 0); int lsize=0; while(x) {int _=lsize+t[lc].size; if(k<=_) x=lc;else if(k==_+1) return x;else lsize=_+1,x=rc;}return -1;} }S;int main() {freopen("in","r",stdin);n=read(); m=read();for(int i=1; i<=n; i++) val[i]=read(), fa[i]=i;S.ini();for(int i=1; i<=m; i++) x=find(read()), y=find(read()), S.Merge(x, y);Q=read();for(int i=1; i<=Q; i++) {scanf("%s",s); x=find(read()); y=read();if(s[0]=='B') y=find(y), S.Merge(x, y);else printf("%d\n", S.kth(x, y));} }

總結

以上是生活随笔為你收集整理的BZOJ 2733: [HNOI2012]永无乡 [splay启发式合并]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。