2333: [SCOI2011]棘手的操作
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1979 Solved: 772
[Submit][Status][Discuss]
Description
有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: 输出所有节点中，权值最大的节点的权值
Input
输入的第一行是一个整数N，代表节点个数。
接下来一行输入N个整数，a[1], a[2], …, a[N]，代表N个节点的初始权值。
再下一行输入一个整数Q，代表接下来的操作数。
最后输入Q行，每行的格式如题目描述所示。
Output
对于操作F1, F2, F3，输出对应的结果，每个结果占一行。
Sample Input
3
0 0 0
8
A1 3 -20
A1 2 20
U 1 3
A2 1 10
F1 3
F2 3
A3 -10
F3
Sample Output
-10
10
10
HINT
对于30%的数据，保证 N<=100，Q<=10000
对于80%的数据，保证 N<=100000，Q<=100000
对于100%的数据，保证 N<=300000，Q<=300000
对于所有的数据，保证输入合法，并且 -1000<=v, a[1], a[2], …, a[N]<=1000
Source
可并堆真是个玄学的东西我不玩了！！！
复杂度怎么分析怎么不对啊，怎么可以像平衡树那样打标记呢？
并且怎么写怎么不对........
最后无奈照黄学长抄了个代码，内层左偏树或者斜堆都可以，外层set必须用s.erase(s.find(v))
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
#define lc t[x].l
#define rc t[x].r
typedef long long ll;
const int N=3e5+,INF=1e9;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return x*f;
}
int n,Q,x,y,v;
char s[]; struct node{
int l,r,fa,v,add;
}t[N];
inline int find(int x){
while(t[x].fa) x=t[x].fa;
return x;
}
inline void pushDown(int x){
if(t[x].add){
if(lc) t[lc].v+=t[x].add,t[lc].add+=t[x].add;
if(rc) t[rc].v+=t[x].add,t[rc].add+=t[x].add;
t[x].add=;
}
}
int st[N];
inline void PD(int x){
while(x) st[++st[]]=x,x=t[x].fa;
while(st[]) pushDown(st[st[]--]);
}
inline int Top(int x){
return t[find(x)].v;
}
int Merge(int x,int y){
if(x==||y==) return x+y;
if(t[x].v<t[y].v) swap(x,y);
pushDown(x);
rc=Merge(rc,y);
t[rc].fa=x;
swap(lc,rc);
return x;
}
int Del(int x){
pushDown(x);//no
int f=t[x].fa,y=Merge(lc,rc);
t[y].fa=f;
if(t[f].l==x) t[f].l=y;
else t[f].r=y;
t[x].l=t[x].r=t[x].fa=;
return find(y);
}
multiset<int> S;
inline void erase(int v){
S.erase(S.find(v));
}
inline void U(int x,int y){
x=find(x);y=find(y);
if(x!=y){
if(Merge(x,y)==x) erase(t[y].v);
else erase(t[x].v);
}
}
inline void A1(int x,int v){
PD(x);
erase(t[find(x)].v);
t[x].v+=v;
S.insert(t[Merge(Del(x),x)].v);
}
inline void A2(int x,int v){
int f=find(x);
erase(t[f].v);
t[f].add+=v;t[f].v+=v;
S.insert(t[f].v);
}
int ADD;
inline void F1(int x){
PD(x);
printf("%d\n",t[x].v+ADD);
}
int main(){
//freopen("in.txt","r",stdin);
n=read();
for(int i=;i<=n;i++){
t[i].v=read();
S.insert(t[i].v);
}
Q=read();
while(Q--){
scanf("%s",s);
if(s[]=='U') x=read(),y=read(),U(x,y);
if(s[]=='A'){
x=read();
if(s[]=='') v=read(),A1(x,v);
if(s[]=='') v=read(),A2(x,v);
if(s[]=='') ADD+=x;
}
if(s[]=='F'){
if(s[]=='') x=read(),F1(x);
if(s[]=='') x=read(),printf("%d\n",t[find(x)].v+ADD);
if(s[]=='') printf("%d\n",*--S.end()+ADD);
}
}
}
下面是当时写了一个下午的WA代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define lc t[x].l
#define rc t[x].r
typedef long long ll;
const int N=3e5+,INF=1e9;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return x*f;
}
int n,Q,x,y,v;
char s[]; int fa[N];
inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
struct node{
int l,r,fa,v,d,size;
}t[N];
int add[N];
//inline void update(int x){t[x].size=t[lc].size+t[rc].size+1;}
void Add(int x,int v){
t[x].v+=v;
if(lc) Add(lc,v);
if(rc) Add(rc,v);
}
int Merge(int x,int y){//printf("Merge %d %d\n",x,y);
if(x==||y==) return x+y;
if(t[x].v<t[y].v) swap(x,y);
rc=Merge(rc,y);
// update(x);printf("MS %d %d\n",x,t[x].size);
t[rc].fa=x;
if(t[lc].d<t[rc].d) swap(lc,rc);
t[x].d=t[rc].d+;
return x;
}
int Del(int x){
int f=t[x].fa,y=Merge(lc,rc);
t[y].fa=f;
if(f&&t[f].l==x) t[f].l=y;
if(f&&t[f].r==x) t[f].r=y;
// update(f);
int re=f?find(f):y;
t[x].l=t[x].r=t[x].fa=t[x].d=;
x=f;
while(x){
if(t[lc].d<t[rc].d) swap(lc,rc);
if(t[rc].d+==t[x].d) break;
t[x].d=t[rc].d+;
x=t[x].fa;
}
return re;
} namespace S{ struct node{
int l,r,fa,v,d;
}t[N];
int root;
int Merge(int x,int y){//printf("Merge %d %d\n",x,y);
if(x==||y==) return x+y;
if(t[x].v<t[y].v) swap(x,y);
rc=Merge(rc,y);
t[rc].fa=x;
if(t[lc].d<t[rc].d) swap(lc,rc);
t[x].d=t[rc].d+;
return x;
}
int Del(int x){
int f=t[x].fa,y=Merge(lc,rc);
t[y].fa=f;
if(f&&t[f].l==x) t[f].l=y;
if(f&&t[f].r==x) t[f].r=y;
int re=f?find(f):y;
t[x].l=t[x].r=t[x].fa=t[x].d=;
x=f;
while(x){
if(t[lc].d<t[rc].d) swap(lc,rc);
if(t[rc].d+==t[x].d) break;
t[x].d=t[rc].d+;
x=t[x].fa;
}//printf("DElre %d\n",re);
return re;
} int q[N],head,tail;
inline void lop(int &x){if(x==N) x=;}
void Heapify(){
head=tail=;
for(int i=;i<=n;i++) q[tail++]=i;
int x,y,z;
while(head!=tail){
x=q[head++];lop(head);
if(head!=tail) y=q[head++],lop(head);
else break;
z=Merge(x,y);
q[tail++]=z;lop(tail);
}
root=x;
} } inline void U(int x,int y){
x=find(x);y=find(y);
if(x!=y){
S::Del(x);
S::Del(y);//printf("IWantToSeeSize %d %d\n",t[x].size,t[y].size);
if(t[x].size>t[y].size) swap(x,y);
Add(x,add[x]-add[y]);
int z=fa[x]=fa[y]=Merge(x,y);//printf("M %d %d %d %d %d %d\n",x,y,z,t[x].v,t[y].v,t[z].v);
add[z]=add[y];//printf("hiz %d %d %d %d\n",z,S::t[z].v,S::root,S::t[S::root].v);
t[z].size=t[x].size+t[y].size;
S::root=S::Merge(S::root,z);//printf("hiroot %d %d\n",S::root,S::t[S::root].v);
}
}
inline void A1(int x,int v){
int fx=find(x);
S::root=S::Del(fx); int _add=add[fx],_size=t[fx].size;
int y=Del(x);
t[x].v+=v;//printf("what %d %d\n",x,y);
int z=fa[x]=fa[y]=Merge(x,y);
//printf("A1 %d %d %d\nAS %d %d %d\n",x,y,z,t[x].size,t[y].size,t[z].size);
add[z]=_add;t[z].size=_size; S::t[z].v=t[z].v+add[z];
S::root=Merge(S::root,z);
}
inline void A2(int x,int v){
x=find(x);
S::root=S::Del(x);
add[x]+=v;
S::t[x].v=t[x].v+add[x];
S::root=Merge(S::root,x);
}
int ADD;
inline void A3(int v){ADD+=v;}
inline void F1(int x){
int fx=find(x);
printf("%d\n",t[x].v+add[fx]+ADD);
}
inline void F2(int x){
int fx=find(x);
printf("%d\n",t[fx].v+add[fx]+ADD);
}
inline void F3(){printf("%d\n",S::t[S::root].v+ADD);}
int main(){
//freopen("in.txt","r",stdin);
n=read();
for(int i=;i<=n;i++){
t[i].v=S::t[i].v=read();
t[i].size=; fa[i]=i;
}
t[].d=S::t[].d=-;
S::Heapify();
Q=read();//printf("BEGIN\n");
while(Q--){ //printf("QQQQQQQQQ %d\n",Q);
scanf("%s",s);
if(s[]=='U') x=read(),y=read(),U(x,y);
if(s[]=='A'){
x=read();
if(s[]=='') v=read(),A1(x,v);
if(s[]=='') v=read(),A2(x,v);
if(s[]=='') A3(x);
}
if(s[]=='F'){
if(s[]=='') x=read(),F1(x);
if(s[]=='') x=read(),F2(x);
if(s[]=='') F3();
}
}
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
#define lc t[x].l
#define rc t[x].r
typedef long long ll;
const int N=3e5+,INF=1e9;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return x*f;
}
int n,Q,x,y,v;
char s[]; struct node{
int l,r,fa,v,d,add;
}t[N];
inline int find(int x){
while(t[x].fa) x=t[x].fa;
return x;
}
inline void pushDown(int x){
if(t[x].add){
if(lc) t[lc].v+=t[x].add;
if(rc) t[rc].v+=t[x].add;
t[x].add=;
}
}
int st[N],top;
inline void PD(int x){
while(x) st[++top]=x,x=t[x].fa;
while(top) pushDown(st[top--]);
} int Merge(int x,int y){
if(x==||y==) return x+y;
if(t[x].v<t[y].v) swap(x,y);
pushDown(x);
rc=Merge(rc,y);
t[rc].fa=x;
if(t[lc].d<t[rc].d) swap(lc,rc);
t[x].d=t[rc].d+;
return x;
}
int Del(int x){
pushDown(x);
int f=t[x].fa,y=Merge(lc,rc);
t[y].fa=f;
if(f&&t[f].l==x) t[f].l=y;
if(f&&t[f].r==x) t[f].r=y;
t[x].l=t[x].r=t[x].fa=t[x].d=;
x=f;
while(x){
if(t[lc].d<t[rc].d) swap(lc,rc);
if(t[rc].d+==t[x].d) break;
t[x].d=t[rc].d+;
x=t[x].fa;
}
return find(y);
}
multiset<int> S;
inline void U(int x,int y){
x=find(x);y=find(y);
if(x!=y){
if(Merge(x,y)==x) S.erase(t[y].v);
else S.erase(t[x].v);
}
}
inline void A1(int x,int v){
PD(x);
S.erase(t[find(x)].v);
t[x].v+=v;
S.insert(t[Merge(Del(x),x)].v);
}
inline void A2(int x,int v){
int f=find(x);
S.erase(t[f].v);
t[f].add+=v;t[f].v+=v;
S.insert(t[f].v);
}
int ADD;
inline void F1(int x){
PD(x);
printf("%d\n",t[x].v+ADD);
}
int main(){
//freopen("in.txt","r",stdin);
n=read();
for(int i=;i<=n;i++){
t[i].v=read();
S.insert(t[i].v);
}
t[].d=-;
Q=read();
while(Q--){
scanf("%s",s);
if(s[]=='U') x=read(),y=read(),U(x,y);
if(s[]=='A'){
x=read();
if(s[]=='') v=read(),A1(x,v);
if(s[]=='') v=read(),A2(x,v);
if(s[]=='') ADD+=x;
}
if(s[]=='F'){
if(s[]=='') x=read(),F1(x);
if(s[]=='') x=read(),printf("%d\n",t[find(x)].v+ADD);
if(s[]=='') printf("%d\n",*--S.end()+ADD);
}
}
}