题目传送-Luogu3273
题目传送-BZOJ2333
题意：
有(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): 输出所有节点中，权值最大的节点的权值
题解：
一片文章
有合并操作，还有在点上的权值，并查集显然不能用，考虑可并堆。
U:两个可并堆并起来
A1:这个点从左偏树里删掉，加上权值后再并起来，注意标记的处理
A2:给根打上标记
A3:记个全局变量加一下
F1:标记下传后输出
F2:输出这个堆顶值
F3:全局维护个set维护所有堆顶的值，记得更新
过程：
一堆细节真是恶心。。hzwer：嘴巴AC真是简单
代码：
const int N=300010;
int n,q,Add=0; set<int> Max; map<int,int> cnt;
#define lc ch[u][0]
#define rc ch[u][1]
int hp[N],ch[N][2],laz[N],fa[N],dep[N];
inline void Erase(int val) {if(--cnt[val]==0) Max.erase(val);}
inline void Insert(int val) {if(++cnt[val]==1) Max.insert(val);}
inline bool get_son(int u) {return u==ch[fa[u]][1];}
inline int Find(int x) {
// assert(x);
while(fa[x]) x=fa[x]; return x;
}
inline void Update(int u,int v) {
assert(u);
hp[u]+=v; laz[u]+=v;
}
inline void Push_Dn(int u) {
if(laz[u]) {
int val=laz[u]; laz[u]=0;
if(lc) Update(lc,val);
if(rc) Update(rc,val);
}
}
int que[N];
inline void Pulltag(int u) {
int tot=0;
while(u)que[++tot]=u,u=fa[u];
while(tot) Push_Dn(que[tot--]);
}
int Merge(int x,int y) {
if(!x || !y) return x+y;
// cerr<<x<<' '<<y<<endl;
if(hp[x]<hp[y]) swap(x,y);
Push_Dn(x);
ch[x][1]=Merge(ch[x][1],y);
assert(ch[x][1]);
fa[ch[x][1]]=x;
if(dep[ch[x][0]]<dep[ch[x][1]]) swap(ch[x][0],ch[x][1]);
dep[x]=dep[ch[x][1]]+1;
return x;
}
inline void Solve_A1(int u,int v) {
int anc=Find(u); Erase(hp[anc]);
Pulltag(u);
// cerr<<"Arr"<<endl;
fa[lc]=fa[rc]=0;
int top=Merge(lc,rc),f=fa[u];
ch[f][get_son(u)]=top;
lc=rc=fa[u]=0;
fa[top]=f;
hp[u]+=v;
anc=Find(top);
// printf("%d %d
",anc,top);
anc=Merge(anc,u);
// printf("%d
",anc);
Insert(hp[anc]);
}
char s[100];
inline void Assert() {
// assert(fa[0]==0); assert(ch[0][0]==0); assert(ch[0][1]==0);
for(int i=1;i<=n;i++)
for(int j=0;j<2;j++) {
if(ch[i][j]) {
// if(fa[ch[i][j]]!=i) {
// cerr<<fa[ch[i][j]]<<' '<<ch[i][j]<<' '<<i<<endl;
// }
assert(fa[ch[i][j]]==i);
assert(fa[i]!=i);
assert(i!=ch[i][j]);
}
}
}
signed main() {
// freopen("kittle4.in","r",stdin);
// freopen("my.out","w",stdout);
set<int> :: iterator it;
read(n);
for(int i=1;i<=n;i++) read(hp[i]),Insert(hp[i]);
read(q); int Cnt=0;
for(int i=1;i<=q;i++) {
//Assert();
// cerr<<"i="<<i<<endl;
scanf("%s",s+1); int x,y,v;
if(s[1]=='U') {
read(x); read(y);
int fx=Find(x),fy=Find(y);
if(fx==fy) continue;
Erase(hp[fx]); Erase(hp[fy]);
x=Merge(fx,fy);
Insert(hp[x]);
} else if(s[1]=='F') {
++Cnt; //if(Cnt==117) cerr<<s[2];
if(s[2]=='1') {
read(x); Pulltag(x);
printf("%d
",hp[x]+Add);
} else if(s[2]=='2') {
read(x);
printf("%d
",hp[Find(x)]+Add);
} else if(s[2]=='3') {
it=Max.end(); it--;
printf("%d
",*it+Add);
}
} else if(s[1]=='A') {
if(s[2]=='1') {
read(x); read(v);
Solve_A1(x,v);
} else if(s[2]=='2') {
read(x); read(v); int anc=Find(x);
Erase(hp[anc]);
Update(anc,v);
Insert(hp[anc]);
} else if(s[2]=='3') {
read(v); Add+=v;
}
}
}
return 0;
}
/*
*/
用时：1h