2333: [SCOI2011]棘手的操作
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 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
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+5,INF=1e9; 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,Q,x,y,v; char s[20]; 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=0; } } int st[N]; inline void PD(int x){ while(x) st[++st[0]]=x,x=t[x].fa; while(st[0]) pushDown(st[st[0]--]); } inline int Top(int x){ return t[find(x)].v; } int Merge(int x,int y){ if(x==0||y==0) 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=0; 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 ",t[x].v+ADD); } int main(){ //freopen("in.txt","r",stdin); n=read(); for(int i=1;i<=n;i++){ t[i].v=read(); S.insert(t[i].v); } Q=read(); while(Q--){ scanf("%s",s); if(s[0]=='U') x=read(),y=read(),U(x,y); if(s[0]=='A'){ x=read(); if(s[1]=='1') v=read(),A1(x,v); if(s[1]=='2') v=read(),A2(x,v); if(s[1]=='3') ADD+=x; } if(s[0]=='F'){ if(s[1]=='1') x=read(),F1(x); if(s[1]=='2') x=read(),printf("%d ",t[find(x)].v+ADD); if(s[1]=='3') printf("%d ",*--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+5,INF=1e9; 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,Q,x,y,v; char s[20]; 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 ",x,y); if(x==0||y==0) return x+y; if(t[x].v<t[y].v) swap(x,y); rc=Merge(rc,y); // update(x);printf("MS %d %d ",x,t[x].size); t[rc].fa=x; if(t[lc].d<t[rc].d) swap(lc,rc); t[x].d=t[rc].d+1; 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=0; x=f; while(x){ if(t[lc].d<t[rc].d) swap(lc,rc); if(t[rc].d+1==t[x].d) break; t[x].d=t[rc].d+1; 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 ",x,y); if(x==0||y==0) 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+1; 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=0; x=f; while(x){ if(t[lc].d<t[rc].d) swap(lc,rc); if(t[rc].d+1==t[x].d) break; t[x].d=t[rc].d+1; x=t[x].fa; }//printf("DElre %d ",re); return re; } int q[N],head,tail; inline void lop(int &x){if(x==N) x=1;} void Heapify(){ head=tail=1; for(int i=1;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 ",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 ",x,y,z,t[x].v,t[y].v,t[z].v); add[z]=add[y];//printf("hiz %d %d %d %d ",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 ",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 ",x,y); int z=fa[x]=fa[y]=Merge(x,y); //printf("A1 %d %d %d AS %d %d %d ",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 ",t[x].v+add[fx]+ADD); } inline void F2(int x){ int fx=find(x); printf("%d ",t[fx].v+add[fx]+ADD); } inline void F3(){printf("%d ",S::t[S::root].v+ADD);} int main(){ //freopen("in.txt","r",stdin); n=read(); for(int i=1;i<=n;i++){ t[i].v=S::t[i].v=read(); t[i].size=1; fa[i]=i; } t[0].d=S::t[0].d=-1; S::Heapify(); Q=read();//printf("BEGIN "); while(Q--){ //printf("QQQQQQQQQ %d ",Q); scanf("%s",s); if(s[0]=='U') x=read(),y=read(),U(x,y); if(s[0]=='A'){ x=read(); if(s[1]=='1') v=read(),A1(x,v); if(s[1]=='2') v=read(),A2(x,v); if(s[1]=='3') A3(x); } if(s[0]=='F'){ if(s[1]=='1') x=read(),F1(x); if(s[1]=='2') x=read(),F2(x); if(s[1]=='3') 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+5,INF=1e9; 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,Q,x,y,v; char s[20]; 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=0; } } 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==0||y==0) 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+1; 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=0; x=f; while(x){ if(t[lc].d<t[rc].d) swap(lc,rc); if(t[rc].d+1==t[x].d) break; t[x].d=t[rc].d+1; 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 ",t[x].v+ADD); } int main(){ //freopen("in.txt","r",stdin); n=read(); for(int i=1;i<=n;i++){ t[i].v=read(); S.insert(t[i].v); } t[0].d=-1; Q=read(); while(Q--){ scanf("%s",s); if(s[0]=='U') x=read(),y=read(),U(x,y); if(s[0]=='A'){ x=read(); if(s[1]=='1') v=read(),A1(x,v); if(s[1]=='2') v=read(),A2(x,v); if(s[1]=='3') ADD+=x; } if(s[0]=='F'){ if(s[1]=='1') x=read(),F1(x); if(s[1]=='2') x=read(),printf("%d ",t[find(x)].v+ADD); if(s[1]=='3') printf("%d ",*--S.end()+ADD); } } }