题目链接:点击打开链接
题意比較明显,不赘述。
删除时能够把i-1转到根,把i+1转到根下
则i点就在 根右子树 的左子树,且仅仅有i这一个 点
#include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> using namespace std; #define N 300500 #define inf 10000000 #define L(x) tree[x].ch[0] #define R(x) tree[x].ch[1] #define Father(x) tree[x].fa #define Size(x) tree[x].size #define Val(x) tree[x].val #define Left(x) tree[x].left #define Right(x) tree[x].right #define Sum(x) tree[x].sum #define Ans(x) tree[x].ans struct node{ int ch[2],fa,size; int val, left, right, sum, ans; }tree[N]; int tot, root; int a[N]; void Newnode(int& id, int val, int fa){ node E={0,0,fa,1,val,val,val,val,val}; id = tot++; tree[id] = E; } void push_up(int id){ Size(id) = Size(L(id))+Size(R(id))+1; Sum(id) = Sum(L(id)) + Sum(R(id)) + Val(id); Left(id) = max(Left(L(id)), Sum(L(id))+Val(id)+max(Left(R(id)), 0)); Right(id) = max(Right(R(id)), Sum(R(id))+Val(id)+max(Right(L(id)), 0)); Ans(id) = max(Ans(L(id)), Ans(R(id))); Ans(id) = max(Ans(id), Val(id)+max(Right(L(id)),0)+max(Left(R(id)),0)); } void push_down(int id){} void Rotate(int id, int kind){ int y = Father(id); push_down(id); push_down(y); tree[y].ch[kind^1] = tree[id].ch[kind]; Father(tree[id].ch[kind]) = y; if(Father(y)) tree[Father(y)].ch[R(Father(y))==y] = id; Father(id) = Father(y); Father(y) = id; tree[id].ch[kind] = y; push_up(y); } void Splay(int id, int goal){ push_down(id); while(Father(id)!=goal){ int y = Father(id); if(Father(y)==goal) Rotate(id,L(y)==id); else { int kind = L(Father(y))==y; if(tree[y].ch[kind]==id) { Rotate(id, kind^1); Rotate(id, kind); } else { Rotate(y, kind); Rotate(id, kind); } } push_down(id); } if(goal==0)root = id; push_up(id); } int Get_kth(int k){ int id = root; push_down(id); while(Size(L(id))!=k){ if(Size(L(id))>k) id = L(id); else { k -= (Size(L(id)) +1); id = R(id); } push_down(id); } return id; } int Getmax(int id){ push_down(id); while(R(id)){ id = R(id); push_down(id); } return id; } void Delete(int id){ int a = Get_kth(id-1); int b = Get_kth(id+1); Splay(a, 0); Splay(b, root); L(b) = 0; push_up(b); push_up(a); } int build(int l, int r, int& id, int fa){ if(l>r)return 0; int mid = (l+r)>>1; Newnode(id, a[mid], fa); build(l, mid-1, L(id), id); build(mid+1, r, R(id), id); push_up(id); } int n, que; char s[2]; void init(){ Father(0) = L(0) = R(0) = Size(0) = 0; Sum(0) = 0; Val(0) = Left(0) = Right(0) = Ans(0) = -inf; root = tot = 1; Newnode(root, -inf, 0); Newnode(R(root), -inf, root); build(1, n, L(R(root)), R(root)); push_up(R(root)); push_up(root); } int main(){ int i, j; while(~scanf("%d",&n)){ for(i = 1; i <= n; i++)scanf("%d",&a[i]); init(); scanf("%d",&que); while(que--){ scanf("%s",s); if(s[0]==‘I‘) { scanf("%d %d",&i,&j); Splay(Get_kth(i), 0); Splay(Getmax(L(root)), root); Newnode(R(L(root)), j, L(root)); push_up(L(root)); push_up(root); } else if(s[0]==‘Q‘) { scanf("%d %d",&i,&j); Splay(Get_kth(i-1), 0); Splay(Get_kth(j+1), root); printf("%d\n", Ans(L(R(root)))); } else if(s[0]==‘D‘) { scanf("%d",&i); Delete(i); } else if(s[0]==‘R‘) { scanf("%d %d",&i,&j); Splay(Get_kth(i), 0); Val(root) = j; push_up(root); } } } return 0; } /* 5 3 -4 3 -1 6 99 I 6 2 Q 3 5 R 5 -4 Q 3 5 D 2 Q 1 5 I 2 -10 Q 1 6 R 2 -1 Q 1 6 Q 1 6 */
SPOJ 4487. Can you answer these queries VI splay,布布扣,bubuko.com
SPOJ 4487. Can you answer these queries VI splay
原文:http://www.cnblogs.com/mengfanrong/p/3760533.html