BZOJ2333.cpp

#include <cstdio>
#include <cstdlib>
#include <set>
#include <algorithm>

using namespace std;

struct pii{
	int x, y;
	pii(int x = 0, int y = 0):x(x), y(y){};
};

const int MaxN = 300000;

int fa[MaxN + 1], iMax[MaxN + 1], lazy[MaxN + 1], val[MaxN + 1];
set<pair<int, int> > sMax[MaxN + 1], gMax;

int add;

pair<int, int> getMax(int g){
	set<pair<int, int> >::iterator it = sMax[g].end();it--;
	return *it;
}
pair<int, int> getGMax(){
	set<pair<int, int> >::iterator it = gMax.end();it--;
	return *it;
}

pii getFather(int x){
	if (fa[x] == x)
		return pii(x, 0);
	pii v = getFather(fa[x]);
	sMax[fa[x]].erase(make_pair(val[x] + lazy[x], x));
	fa[x] = v.x;
	lazy[x] += v.y;
	sMax[v.x].insert(make_pair(val[x] + lazy[x], x));
	return pii(v.x, lazy[x]);
}

void Union(int x, int y) {
	pii fx = getFather(x), fy = getFather(y);
	if (fx.x == fy.x)
		return ;
	getFather(getMax(fx.x).second);
	fa[fx.x] = fy.x;
	gMax.erase(make_pair(getMax(fx.x).first + lazy[fx.x], getMax(fx.x).second));
	lazy[fx.x] -= lazy[fy.x];
	gMax.erase(make_pair(getMax(fy.x).first + lazy[fy.x], getMax(fy.x).second));
	getFather(getMax(fx.x).second);
	gMax.insert(make_pair(getMax(fy.x).first + lazy[fy.x], getMax(fy.x).second));
}

int main(){
	freopen("2333.in", "r", stdin);
	freopen("2333_my.out", "w", stdout);
	char opt[3];
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		fa[i] = i;scanf("%d", val + i);
		gMax.insert(make_pair(val[i], i));
		sMax[i].insert(make_pair(val[i], i));
	}
	int Q;
	scanf("%d", &Q);
	for (int i = 1; i <= Q; i++){
		scanf("%s", &opt);
		if (opt[0] == 'U'){
			int x, y;
			scanf("%d%d", &x, &y);
			Union(x, y);
		}
		if (opt[0] == 'A'){
			if (opt[1] == '1'){
				int x, v;
				scanf("%d%d", &x, &v);
				pii y = getFather(x);
				gMax.erase(make_pair(getMax(y.x).first + lazy[y.x], getMax(y.x).second));
				if (y.x == x){
					sMax[x].erase(make_pair(val[x], x));
					val[x] += v;
					sMax[x].insert(make_pair(val[x],x));
				} else {
					sMax[y.x].erase(make_pair(val[x] + lazy[x], x));
					sMax[x].erase(make_pair(val[x], x));
					val[x] += v;
					sMax[x].insert(make_pair(val[x], x));
					getFather(getMax(x).second);
					getFather(x);
				}
				//sMax[y.x].insert(make_pair(getMax(x).first + (x != fa[x])?lazy[x]:0, getMax(x).second));
				gMax.insert(make_pair(getMax(y.x).first + lazy[y.x], getMax(y.x).second));
			}
			if (opt[1] == '2'){
				int x, v;
				scanf("%d%d", &x, &v);
				pii y = getFather(x);
				gMax.erase(make_pair(getMax(y.x).first + lazy[y.x], getMax(y.x).second));
				lazy[y.x] += v;
				gMax.insert(make_pair(getMax(y.x).first + lazy[y.x], getMax(y.x).second));
			}
			if (opt[1] == '3'){
				int v;
				scanf("%d",&v);
				add += v;
			}
		}
		if (opt[0] == 'F'){
			if (opt[1] == '1'){
				int x;scanf("%d", &x);
				pii y = getFather(x);
				printf("%d\n", add + lazy[y.x] + val[x]);
			}
			if (opt[1] == '2'){
				int x;scanf("%d", &x);
				pii y = getFather(x);
				printf("%d\n", add + getMax(y.x).first + lazy[y.x]);
			}
			if (opt[1] == '3'){
				printf("%d\n", getGMax().first + add);
			}
		}
	}
}