首页 > 代码库 > BZOJ2333: [SCOI2011]棘手的操作
BZOJ2333: [SCOI2011]棘手的操作
2333: [SCOI2011]棘手的操作
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 696 Solved: 272
[Submit][Status]
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
题解：
此题比较神！看不懂云神的题解。。。然后翻题解发现了这样的神做法：
初看题目很容易想到用并查集来维护森林中各个节点之间的关系，但是在合并的时候就会出现很多问题了。如果用并查集的话需要暴力地修改标记，维护最大值，然后需要堆来维护各个连通块的最优值，这样显得非常繁琐。
于是我们可以考虑设计离线算法，先将所有询问读入，把连通块之间的关系用并查集维护，并且保证大的节点接在小的节点后面，维护完之后我们就可以将每个连通块映射成为一个区间，这样题目中不管是询问还是更新都是在区间上操作。而在区间上操作的数据结构我们马上就可以想到使用线段树，这样我们可以以O(m)的预处理和O(mlogn)的时间来解决本题。
orz！一些注释写在代码里。
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 350000+5 14 #define maxm 500+100 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 #define for0(i,n) for(int i=0;i<=(n);i++) 19 #define for1(i,n) for(int i=1;i<=(n);i++) 20 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 21 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 22 #define mod 1000000007 23 using namespace std; 24 inline int read() 25 { 26 int x=0,f=1;char ch=getchar(); 27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 28 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 29 return x*f; 30 } 31 struct seg{int l,r,tag,mx;}t[4*maxn]; 32 struct rec{int ch,x,y;}a[maxn]; 33 int n,m,tot,fa[maxn],w[maxn],b[maxn],pos[maxn],last[maxn],next[maxn]; 34 inline void pushup(int k) 35 { 36 t[k].mx=max(t[k<<1].mx,t[k<<1|1].mx); 37 } 38 inline void build(int k,int l,int r) 39 { 40 t[k].l=l;t[k].r=r;int mid=(l+r)>>1; 41 if(l==r){t[k].mx=b[l];return;} 42 build(k<<1,l,mid);build(k<<1|1,mid+1,r); 43 pushup(k); 44 } 45 inline void update(int k,int z) 46 { 47 t[k].tag+=z;t[k].mx+=z; 48 } 49 inline void pushdown(int k) 50 { 51 if(!t[k].tag)return; 52 update(k<<1,t[k].tag); 53 update(k<<1|1,t[k].tag); 54 t[k].tag=0; 55 } 56 inline void add(int k,int x,int y,int z) 57 { 58 int l=t[k].l,r=t[k].r,mid=(l+r)>>1; 59 if(l==x&&r==y){update(k,z);return;} 60 pushdown(k); 61 if(y<=mid)add(k<<1,x,y,z); 62 else if(x>mid)add(k<<1|1,x,y,z); 63 else add(k<<1,x,mid,z),add(k<<1|1,mid+1,y,z); 64 pushup(k); 65 } 66 inline int query(int k,int x,int y) 67 { 68 int l=t[k].l,r=t[k].r,mid=(l+r)>>1; 69 if(l==x&&r==y)return t[k].mx; 70 pushdown(k); 71 if(y<=mid)return query(k<<1,x,y); 72 else if(x>mid)return query(k<<1|1,x,y); 73 else return max(query(k<<1,x,mid),query(k<<1|1,mid+1,y)); 74 } 75 inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} 76 int main() 77 { 78 freopen("input.txt","r",stdin); 79 freopen("output.txt","w",stdout); 80 n=read(); 81 for1(i,n)w[i]=read(),fa[i]=i,last[i]=i;//last表示i集合中最后一个节点，不一定编号最大 82 m=read(); 83 for1(i,m) 84 { 85 char ch[4];scanf("%s",ch); 86 if(ch[0]==‘U‘) 87 { 88 a[i].ch=0; 89 int x=a[i].x=read(),y=a[i].y=read(); 90 x=find(x);y=find(y); 91 if(x==y)continue;//注意如果合并两个本身就在同一集合的点！ 92 if(x>y)swap(x,y);//小的在前，大的在后 93 fa[y]=x; 94 next[last[x]]=y;//记录后继，这里相当于把两个集合连起来了 95 last[x]=last[y];//last改变 96 } 97 else if(ch[0]==‘A‘) 98 { 99 a[i].ch=ch[1]-‘0‘;100 if(a[i].ch==3)a[i].x=read();else a[i].x=read(),a[i].y=read();101 }102 else 103 {104 a[i].ch=ch[1]-‘0‘+3;105 if(a[i].ch!=6)a[i].x=read();106 }107 }108 for1(i,n)if(fa[i]==i){for(int j=i;j;j=next[j])pos[j]=++tot;}//在同一集合的按刚才的顺序重新编成连续的号 109 for1(i,n)last[i]=pos[i];//此时last表示i集合的最后 ，然后下面的修改和查询就顺理成章了 110 for1(i,n)b[pos[i]]=w[i];111 for1(i,n)fa[i]=i;112 build(1,1,n);113 int tmp=0;114 for1(i,m)115 {116 if(!a[i].ch)117 {118 int x=find(a[i].x),y=find(a[i].y);119 if(x>y)swap(x,y);120 fa[y]=x;121 last[x]=last[y];122 }123 else if(a[i].ch==1)add(1,pos[a[i].x],pos[a[i].x],a[i].y);124 else if(a[i].ch==2)125 {126 int x=find(a[i].x);127 add(1,pos[x],last[x],a[i].y);128 }129 else if(a[i].ch==3)tmp+=a[i].x;130 else if(a[i].ch==4)printf("%d\n",query(1,pos[a[i].x],pos[a[i].x])+tmp);131 else if(a[i].ch==5)132 {133 int x=find(a[i].x);134 printf("%d\n",query(1,pos[x],last[x])+tmp);135 }136 else printf("%d\n",t[1].mx+tmp);137 } 138 return 0;139 }
BZOJ2333: [SCOI2011]棘手的操作
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。