蒟蒻求大佬帮助

-20
0
10

维护一个全局标记和每个节点的标记，合并时下传。
A1操作删除节点然后重新插入。
A2操作在根节点打标记，通过并查集实现。
A3操作更新全局标记。
然后更新的时候顺便记录最大值。

#include<bits/stdc++.h>

using namespace std;

namespace StandardIO {

	template<typename T>inline void read (T &x) {
		x=0;T f=1;char c=getchar();
		for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
		for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
		x*=f;
	}

	template<typename T>inline void write (T x) {
		if (x<0) putchar('-'),x*=-1;
		if (x>=10) write(x/10);
		putchar(x%10+'0');
	}

}

using namespace StandardIO;

namespace Solve {
	
	const int N=300300;
	
	int n,q;
	int a[N],root[N];
	int tot,tot_tag,tot_max;
	struct node {
		int ls,rs,fa;
		int val,tag;
		int dis;
	} heap[N];
	
	void pushdown (int x) {
		if (heap[x].tag) {
			heap[heap[x].ls].tag+=heap[x].tag;
			heap[heap[x].rs].tag+=heap[x].tag;
			heap[heap[x].ls].val+=heap[x].tag;
			heap[heap[x].rs].val+=heap[x].tag;
			heap[x].tag=0;
		}
	}
	int merge (int x,int y) {
		if (!x||!y) return x+y;
		if (heap[x].val<heap[y].val) swap(x,y);
		pushdown(x);
		heap[x].rs=merge(heap[x].rs,y);
		if (heap[heap[x].ls].dis<heap[heap[x].rs].dis) swap(heap[x].ls,heap[x].rs);
		heap[heap[x].ls].fa=x,heap[heap[x].rs].fa=x;
		heap[x].dis=heap[heap[x].rs].dis+1;
		tot_max=max(tot_max,heap[x].val);
		return x;
	}
	int pop (int x) {
		x=merge(heap[x].ls,heap[x].rs);
		return x;
	}
	int newNode (int v) {
		heap[++tot].val=v,heap[tot].fa=tot;
		heap[tot].ls=heap[tot].rs=heap[tot].dis=heap[tot].tag=0;
		tot_max=max(tot_max,heap[tot].val);
		return tot;
	}
	int add (int x,int v) {
		int tmp=heap[x].val;
		int rest=pop(x);
		x=newNode(tmp+v);
		x=merge(x,rest);
		tot_max=max(tot_max,heap[x].val);
		return x;
	}
	int find (int x) {
		while (heap[x].fa!=x) x=heap[x].fa;
		return x;
	}
	void block_add (int x,int v) {
		int top=find(x);
		heap[top].tag+=v;
	}
	void all_add (int v) {
		tot_tag+=v;
	}
	int value (int x) {
		return heap[x].val;
	}
	int block_max (int x) {
		int top=find(x);
		return heap[top].val;
	}
	int all_max () {
		return tot_max+tot_tag;
	}

	inline void solve () {
		read(n);
		for (register int i=1; i<=n; ++i) {
			read(a[i]);
			root[i]=newNode(a[i]);
		}
		read(q);
		while (q--) {
			string op;int x,y;
			cin>>op;
			if (op=="U") {
				read(x),read(y);
				root[x]=merge(root[x],root[y]);
			} else if (op=="A1") {
				read(x),read(y);
				root[x]=add(root[x],y);
			} else if (op=="A2") {
				read(x),read(y);
				block_add(root[x],y);
			} else if (op=="A3") {
				read(x);
				all_add(x);
			} else if (op=="F1") {
				read(x);
				write(value(root[x])+tot_tag),putchar('\n');
			} else if (op=="F2") {
				read(x);
				write(block_max(root[x])+tot_tag),putchar('\n');
			} else {
				write(all_max()),putchar('\n');
			}
		}
	}
}

using namespace Solve;

int main () {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	solve();
}