2333: [SCOI2011]棘手的操作
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1090 Solved: 419
[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
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维护全局最大。。具体操作什么的看代码。。（其实我也是看别人的代码的）。。附一个神犇的blog——>
http://dream-for-me.blog.163.com/blog/static/245077059201531172421284/（关于可并堆的）
#include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 300010;
int l[N],r[N],mark[N],key[N],f[N],n,m,x,val,Allover,y;
char opt[10];
multiset<int> bst;
int read(){
int x = 0,f = 1,c = getchar();
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;
}
void Pushdown(int x){
int Lx = l[x],Rx = r[x],val = mark[x];
if (Lx) mark[Lx]+=val,key[Lx]+=val;
if (Rx) mark[Rx]+=val,key[Rx]+=val;
mark[x] = 0;
}
int merge(int a,int b){
if (!a || !b) return a+b;
if (key[a]<key[b]) swap(a,b);
Pushdown(a);
int res = r[a] = merge(r[a],b);
f[res] = a;swap(r[a],l[a]);
return a;
}
int get(int x){while (f[x]) x = f[x];return x;}
void Add_tag(int x){if (f[x]) Add_tag(f[x]);Pushdown(x);}
void U(){
x = read(),y = read();
int fx = get(x),fy = get(y);
if (fx!=fy){
int top = merge(fx,fy);
if (top==fx) bst.erase(bst.find(key[fy]));
else bst.erase(bst.find(key[fx]));
}
}
void A1(){
x = read();val = read();
Add_tag(x);
bst.erase(bst.find(key[get(x)]));
key[x]+=val;
int Fx = f[x],Lx = l[x],Rx = r[x],tmp = merge(Lx,Rx);
f[x] = l[x] = r[x] = 0;
if (l[Fx]==x) l[Fx] = tmp;
else r[Fx] = tmp;
f[tmp] = Fx;
bst.insert(key[merge(get(tmp),x)]);
}
void A2(){
x = read();val = read();
int top = get(x);
bst.erase(bst.find(key[top]));
mark[top]+=val;key[top]+=val;
bst.insert(key[top]);
}
void A3(){val = read();Allover+=val;}
void F1(){
x = read();
Add_tag(x);
printf("%d\n",key[x]+Allover);
}
void F2(){
x = read();
printf("%d\n",key[get(x)]+Allover);
}
void F3(){printf("%d\n",*--bst.find(1e9)+Allover);}
int main(){
n = read();
for (int i=1;i<=n;i++){key[i] = read();bst.insert(key[i]);}
m = read();
for (int i=1;i<=m;i++){
scanf("%s",opt);
if (opt[0]=='U') U();
if (opt[0]=='A'){
if (opt[1]=='1') A1();
if (opt[1]=='2') A2();
if (opt[1]=='3') A3();
}
if (opt[0]=='F'){
if (opt[1]=='1') F1();
if (opt[1]=='2') F2();
if (opt[1]=='3') F3();
}
}
}
评论 (0)
