首页 > 代码库 > [bzoj2333][SCOI2011][棘手的操作]
[bzoj2333][SCOI2011][棘手的操作]
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
30 0 08A1 3 -20A1 2 20U 1 3A2 1 10F1 3F2 3A3 -10F3
Sample Output
-101010
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
Solution
用可并堆
把块内堆和全局堆分开来做，开两组堆
#include <stdio.h>#define RG register#define MAXN 300003inline void Rin(RG int &x){ RG int c=getchar(),f=1; for(;c<48||c>57;c=getchar())if(c==45)f=-1; for(x=0;c>47&&c<58;x=(x<<1)+(x<<3)+c-48,c=getchar());x*=f;}inline void swap(RG int &x,RG int &y){x^=y;y^=x;x^=y;}int n,m,root,all,va[MAXN],fa[MAXN],_fa[MAXN],ls[MAXN],_ls[MAXN],rs[MAXN],_rs[MAXN],tg[MAXN];inline int sum(RG int x){ int ret=0; while(fa[x])x=fa[x],ret+=tg[x]; return ret;}inline int find(RG int x){ while(fa[x])x=fa[x]; return x;}inline int down(RG int x){ if(tg[x]){ va[ls[x]]+=tg[x]; va[rs[x]]+=tg[x]; tg[ls[x]]+=tg[x]; tg[rs[x]]+=tg[x]; tg[x]=0; }}int merge(RG int x,RG int y){ if(!(x&&y))return x|y; if(va[x]<va[y])swap(x,y); down(x); rs[x]=merge(rs[x],y); fa[rs[x]]=x; swap(ls[x],rs[x]); return x;}int _merge(RG int x,RG int y){ if(!(x&&y))return x|y; if(va[x]<va[y])swap(x,y); _rs[x]=_merge(_rs[x],y); _fa[_rs[x]]=x; swap(_ls[x],_rs[x]); return x;}inline int del(RG int x){ down(x); RG int t=merge(ls[x],rs[x]); fa[t]=fa[x]; if(ls[fa[x]]==x)ls[fa[x]]=t; else rs[fa[x]]=t; ls[x]=rs[x]=fa[x]=0; return find(t);}inline void _del(RG int x){ RG int t=_merge(_ls[x],_rs[x]); _fa[t]=_fa[x]; if(root==x)root=t; else _ls[_fa[x]]==x?_ls[_fa[x]]=t:_rs[_fa[x]]=t; _ls[x]=_rs[x]=_fa[x]=0;}int main(){ Rin(n); for(RG int i=1;i<=n;i++) Rin(va[i]),root=_merge(root,i); Rin(m); RG char s[10];RG int x,y; while(m--){ scanf("%s",s); if(s[0]==‘U‘){ Rin(x),Rin(y); x=find(x),y=find(y); if(x!=y){if(merge(x,y)==x)_del(y);else _del(x);} } else if(s[0]==‘A‘){ if(s[1]==‘1‘){ Rin(x),Rin(y); int k=find(x);_del(k); va[x]+=y+sum(x); k=merge(x,del(x)); root=_merge(root,k); } if(s[1]==‘2‘){ Rin(x),Rin(y); int k=find(x);_del(k); tg[k]+=y,va[k]+=y; root=_merge(root,k); } if(s[1]==‘3‘)Rin(x),all+=x; } else if(s[0]==‘F‘){ if(s[1]==‘1‘)Rin(x),printf("%d\n",sum(x)+va[x]+all); if(s[1]==‘2‘)Rin(x),printf("%d\n",va[find(x)]+all); if(s[1]==‘3‘)printf("%d\n",va[root]+all); } } return 0;}
[bzoj2333][SCOI2011][棘手的操作]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。