题目链接：点击打开链接

题意比較明显，不赘述。

删除时能够把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

*/