做此题的原因题号美题目大意
给出一个序列，支持一堆操作（具体看下面）。让你维护它。
思路
U x y：我们需要可并堆来将两个堆合并。 A1 x v：将这个点从堆中拽出来，改了之后再合并回去。 A2 x v：在堆顶打标记。 A3：记录一个全局变量记录。 F1 x：将这个点到堆顶的链上的所有标记下传，，之后返回自己的大小。 F2 x：返回堆顶。 F3：用一个堆（set也行）维护所有堆顶的元素。需要仔细讨论一下。
CODE;multiset<int> G;struct Heap{int val,plus;Heap *son[2],*father;Heap(int _):val(_) {son[0] = son[1] = father = NULL;plus = 0;}Heap() {}void Plus(int _) {val += _;plus += _;}void PushDown() {if(plus) {if(son[0] != NULL) son[0]->Plus(plus);if(son[1] != NULL) son[1]->Plus(plus);plus = 0;}}}heap[MAX];Heap *Find(Heap *x){while(x->father != NULL)x = x->father;return x;}inline Heap *Merge(Heap *x,Heap *y){if(x == NULL) return y;if(y == NULL) return x;if(x->val < y->val) swap(x,y);x->PushDown();bool k = rand()&1;x->son[k] = Merge(x->son[k],y);x->son[k]->father = x;return x;}inline void Union(Heap *x,Heap *y){G.erase(G.find(min(x->val,y->val)));Merge(x,y);}inline void ClearTag(Heap *x){static Heap *stack[MAX];int top = 0;while(x != NULL)stack[++top] = x,x = x->father;for(int i = top; i; –i)stack[i]->PushDown();}inline void PlusPoint(Heap *x,int c){if(x->father == NULL) {G.erase(G.find(x->val));x->PushDown();Heap *temp = Merge(x->son[0],x->son[1]);if(temp != NULL)temp->father = NULL;x->val += c;x->son[0] = x->son[1] = NULL;G.insert(Merge(x,temp)->val);return ;}Heap *fx = Find(x);G.erase(G.find(fx->val));ClearTag(x);Heap *temp = Merge(x->son[0],x->son[1]);bool k = x->father->son[1] == x;x->father->son[k] = temp;if(temp != NULL)temp->father = x->father;x->father = NULL;x->val += c;x->son[0] = x->son[1] = NULL;G.insert(Merge(fx,x)->val);}inline void PlusBlock(Heap *x,int c){Heap *fx = Find(x);G.erase(G.find(fx->val));fx->Plus(c);G.insert(fx->val);}int g_add;inline void PlusAll(int c){g_add += c;}inline int AskPoint(Heap *x){ClearTag(x);return x->val + g_add;}inline int AskBlock(Heap *x){Heap *fx = Find(x);return fx->val + g_add;}inline int AskAll(){multiset<int>::iterator it = G.end();return *(–it) + g_add;}int points,asks;char s[10];int main(){>> points;for(int x,i = 1; i <= points; ++i) {scanf(“%d”,&x);heap[i] = Heap(x);G.insert(x);}cin >> asks;for(int x,y,i = 1; i <= asks; ++i) {scanf(“%s”,s);if(s[0] == ‘U’) {scanf(“%d%d”,&x,&y);Heap *fx = Find(&heap[x]),*fy = Find(&heap[y]);if(fx == fy) continue;Union(fx,fy);}if(s[0] == ‘A’) {if(s[1] == ‘1’) {scanf(“%d%d”,&x,&y);PlusPoint(&heap[x],y);}if(s[1] == ‘2’) {scanf(“%d%d”,&x,&y);PlusBlock(&heap[x],y);}if(s[1] == ‘3’) {scanf(“%d”,&x);PlusAll(x);}}if(s[0] == ‘F’) {if(s[1] == ‘1’) {scanf(“%d”,&x);printf(“%d\n”,AskPoint(&heap[x]));}if(s[1] == ‘2’) {scanf(“%d”,&x);printf(“%d\n”,AskBlock(&heap[x]));}if(s[1] == ‘3’)printf(“%d\n”,AskAll());}}return 0;}
一只小狗在沙漠中旅行，找到了电线杆，结果还是憋死了，
