題目
有N個節點，標號從1到N，這N個節點一開始相互不連通。第i個節點的初始權值為a[i]，接下來有如下一些操作：
U x y: 加一條邊，連接第x個節點和第y個節點
A1 x v: 將第x個節點的權值增加v
A2 x v: 將第x個節點所在的連通塊的所有節點的權值都增加v
A3 v: 將所有節點的權值都增加v
F1 x: 輸出第x個節點當前的權值
F2 x: 輸出第x個節點所在的連通塊中，權值最大的節點的權值
F3: 輸出所有節點中，權值最大的節點的權值
輸入格式
輸入的第一行是一個整數N，代表節點個數。
接下來一行輸入N個整數，a[1], a[2], …, a[N]，代表N個節點的初始權值。
再下一行輸入一個整數Q，代表接下來的操作數。
最后輸入Q行，每行的格式如題目描述所示。
輸出格式
對于操作F1, F2, F3，輸出對應的結果，每個結果占一行。
輸入樣例
3
0 0 0
8
A1 3 -20
A1 2 20
U 1 3
A2 1 10
F1 3
F2 3
A3 -10
F3
輸出樣例
-10
10
10
提示
對于30%的數據，保證 N<=100，Q<=10000
對于80%的數據，保證 N<=100000，Q<=100000
對于100%的數據，保證 N<=300000，Q<=300000
對于所有的數據，保證輸入合法，并且 -1000<=v, a[1], a[2], …, a[N]<=1000
題解
據說此題很多人堆套堆，怎么這么難寫我那么弱當然是用線段樹啦
我覺得線段樹的確好寫到不知哪里去
對于所有操作，似乎在線段樹上都很好實現，唯一的難點就在于點的編號
那么問題就轉化成了，給定一種編號方法，使任意時刻同一個聯通塊內的所有點編號連續
只需要分兩種情況想就很容易實現了：
我們想象，一開始所有點相互獨立，沒什么關系
①當兩個獨立的點相連時，它們的編號一定是連續的，否則此時就不滿足所需性質
那我們就先用鏈表將它們連起來，表示編號連續
②當兩個聯通塊相連時，由我們維護的性質得：兩個聯通塊內部的點編號一定是連續的，現在我們需要兩個聯通塊編號連續，我們只需要將它們的編號銜接起來就好了，那么我們把其中一個聯通塊所對應的鏈 接到另一個聯通塊對應的鏈末尾就好了
可以發現，這樣子操作之后，我們就會得出若干個鏈，表示鏈上的點編號必須按鏈上的順序
所以我們按鏈的順序標號，就能保證所有時刻聯通塊內部點的編號連續
取鏈頭鏈尾用并查集實現
我們在詢問的時候，也要用上并查集，并且鏈接順序與標號的時候相同，保證每個聯通塊目前的代表元一定是標號時編號最小的點，所以我們再維護并查集的大小就可以輕松求出每次操作的區間啦~
數據結構部分就只用實現一個簡單的線段樹比堆套堆不知道要好寫到哪里去
丑丑的代碼
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
#define ls (u << 1)
#define rs (u << 1 | 1)
using namespace std;
const int maxn = 300005,maxm = 100005,INF = 1000000000;
inline int read(){int out = 0,flag = 1; char c = getchar();while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57) {out = (out << 3) + (out << 1) + c - '0'; c = getchar();}return out * flag;
}
struct Query{int opt,a,b,c;}q[maxn];
int n,m,pre[maxn],post[maxn],id[maxn],Hash[maxn],val[maxn],cnt;
int nxt[maxn],siz[maxn];
int mx[4 * maxn],tag[4 * maxn];
char opt[10];
int findu(int u){return u == pre[u] ? u : pre[u] = findu(pre[u]);}
int findd(int u){return u == post[u] ? u : post[u] = findd(post[u]);}
void build(int u,int l,int r){if (l == r) {mx[u] = val[Hash[l]]; return;}int mid = l + r >> 1;build(ls,l,mid);build(rs,mid + 1,r);mx[u] = max(mx[ls],mx[rs]);
}
void pd(int u){if (tag[u]){mx[ls] += tag[u]; tag[ls] += tag[u];mx[rs] += tag[u]; tag[rs] += tag[u];tag[u] = 0;}
}
void modify(int u,int l,int r,int L,int R,int v){if (l >= L && r <= R){mx[u] += v; tag[u] += v; return;}pd(u);int mid = l + r >> 1;if (mid >= L) modify(ls,l,mid,L,R,v);if (mid < R) modify(rs,mid + 1,r,L,R,v);mx[u] = max(mx[ls],mx[rs]);
}
int query(int u,int l,int r,int L,int R){if (l >= L && r <= R) return mx[u];pd(u);int mid = l + r >> 1;if (mid >= R) return query(ls,l,mid,L,R);else if (mid < L) return query(rs,mid + 1,r,L,R);else return max(query(ls,l,mid,L,R),query(rs,mid + 1,r,L,R));
}
int main(){n = read();for (int i = 1; i <= n; i++) val[i] = read(),pre[i] = post[i] = i;m = read();int fa,fb,sa,sb;for (int i = 1; i <= m; i++){scanf("%s",opt);if (opt[0] == 'U'){q[i].opt = 0,q[i].a = read(),q[i].b = read();fa = findu(q[i].a); fb = findu(q[i].b);if (fa == fb) continue;sa = findd(q[i].a); sb = findd(q[i].b);nxt[sa] = fb;pre[fb] = fa;post[sa] = sb;}else if (opt[0] == 'A'){q[i].a = read();if (opt[1] == '1') q[i].opt = 1,q[i].b = read();else if (opt[1] == '2') q[i].opt = 2,q[i].b = read();else q[i].opt = 3;}else {if (opt[1] == '1') q[i].opt = 4,q[i].a = read();else if (opt[1] == '2') q[i].opt = 5,q[i].a = read();else q[i].opt = 6;}}for (int i = 1; i <= n; i++){if (id[i]) continue;int u = findu(i);while (u) id[u] = ++cnt,Hash[cnt] = u,u = nxt[u];}build(1,1,n);for (int i = 1; i <= n; i++) pre[i] = i,siz[i] = 1;for (int i = 1; i <= m; i++){switch(q[i].opt){case 0:fa = findu(q[i].a); fb = findu(q[i].b);if (fa != fb){siz[fa] += siz[fb];pre[fb] = fa;}break;case 1:modify(1,1,n,id[q[i].a],id[q[i].a],q[i].b);break;case 2:fa = findu(q[i].a);modify(1,1,n,id[fa],id[fa] + siz[fa] - 1,q[i].b);break;case 3:modify(1,1,n,1,n,q[i].a);break;case 4:printf("%d\n",query(1,1,n,id[q[i].a],id[q[i].a]));break;case 5:fa = findu(q[i].a);printf("%d\n",query(1,1,n,id[fa],id[fa] + siz[fa] - 1));break;case 6:printf("%d\n",mx[1]);break;}}return 0;
}
--工具選型篇)
