首页 > 代码库 > 2333: [SCOI2011]棘手的操作[写不出来]
2333: [SCOI2011]棘手的操作[写不出来]
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
Day2
可恶
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;#define lc t[x].l#define rc t[x].rtypedef 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\n",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\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+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\n",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\n",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\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=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\n"); while(Q--){ //printf("QQQQQQQQQ %d\n",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].rtypedef 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\n",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\n",t[find(x)].v+ADD); if(s[1]==‘3‘) printf("%d\n",*--S.end()+ADD); } }}
2333: [SCOI2011]棘手的操作[写不出来]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。