Description:

$I$ $p$ $x$ 在 $p$ 处插入插入一个元素 $x$

$D$ $p$ 删除 $p$ 处的一个元素

$R$ $p$ $x$ 修改 $p$ 处元素的值为 $x$

$Q$ $l$ $r$ 查询一个区间 $[l,r]$ 的最大子段和

Solution:

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define INF 0x3f3f3f3f

inline char getc()

{

	char c = getchar();

	while(c < 'A' || c > 'Z')c = getchar();

	return c;

}

inline int read()

{

	char c = getchar();

	int res = 0,f;

	while((c < '0' || c > '9') && c != '-')c = getchar();

	if(c == '-'){c = getchar();f = -1;}

	else f = 1;

	while('0' <= c && c <= '9')

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

#define MAXN 100010

int n,m;

struct node

{

	int siz,fa,c[2],ls,rs,ms,s,v;

	node(){ls = rs = s = 0;ms = -INF;} 

}t[MAXN << 1];

int ptr = 0;

inline int newnode(){return ++ptr;}

int root;

int a[MAXN];

inline void maintain(int rt)

{

	int lc = t[rt].c[0],rc = t[rt].c[1];

	t[rt].siz = t[lc].siz + t[rc].siz + 1;

	t[rt].s = t[lc].s + t[rc].s + t[rt].v;

	t[rt].ls = max(t[lc].ls,t[lc].s + t[rt].v + t[rc].ls);

	t[rt].rs = max(t[rc].rs,t[rc].s + t[rt].v + t[lc].rs);

	t[rt].ms = max(max(t[lc].ms,t[rc].ms),t[lc].rs + t[rt].v + t[rc].ls);

	return;

}

void build(int &rt,int l,int r,int f)

{

	if(l > r)return;

	rt = newnode();

	t[rt].fa = f;

	int mid = ((l + r) >> 1);

	t[rt].v = a[mid];

	build(t[rt].c[0],l,mid - 1,rt);

	build(t[rt].c[1],mid + 1,r,rt);

	maintain(rt);

	return;

}

inline int id(int x){return (t[t[x].fa].c[0] == x ? 0 : 1);}

inline void connect(int x,int f,int p){t[x].fa = f;t[f].c[p] = x;return;}

inline void rotate(int x)

{

	int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	connect(t[x].c[fx^1],y,fx);

	connect(y,x,fx^1);

	connect(x,z,fy);

	maintain(y);maintain(x);

	return;

}

inline void splay(int x,int &k)

{

	int to = t[k].fa;

	while(t[x].fa != to)

	{

		int y = t[x].fa;

		if(t[y].fa == to){rotate(x);break;}

		if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

	k = x;

	return;

}

inline int find(int x)

{

	register int cur = root;

	int ls;

	while(true)

	{

		if(t[cur].c[0] != 0)ls = t[t[cur].c[0]].siz;

		else ls = 0;

		if(x <= ls)cur = t[cur].c[0];

		else if(x > ls + 1){cur = t[cur].c[1];x -= ls + 1;}

		else

		{

			return cur;

		}

	}

}

inline void insert(int p,int v)

{

	if(p == 1)

	{

		int k = newnode();

		t[k].v = v;

		connect(root,k,1);

		maintain(k);

		root = k;

		return;

	}

	p = find(p - 1);

	splay(p,root);

	int k = newnode();

	connect(t[root].c[1],k,1);

	connect(k,root,1);

	t[k].v = v;

	maintain(k);

	maintain(root);

	return;

}

inline void remove(int p)

{

	if(p == 1)

	{

		splay(find(1),root);

		t[t[root].c[1]].fa = 0;

		root = t[root].c[1];

		return;

	}

	splay(find(p - 1),root);

	splay(find(p),t[root].c[1]);

	connect(t[t[root].c[1]].c[1],root,1);

	maintain(root);

	return;

}

inline void change(int p,int k)

{

	splay(find(p),root);

	t[root].v = k;

	maintain(root);

	return;

}

inline int query(int a,int b)

{

	if(a == 1 && b == n)

	{

		return t[root].ms;

	}

	if(a == 1 && b != n)

	{

		splay(find(b + 1),root);

		return t[t[root].c[0]].ms;

	}

	if(a != 1 && b == n)

	{

		splay(find(a - 1),root);

		return t[t[root].c[1]].ms;

	}

	splay(find(a - 1),root);

	splay(find(b + 1),t[root].c[1]);

	return t[t[t[root].c[1]].c[0]].ms;

}

int main()

{

	scanf("%d",&n);

	for(register int i = 1;i <= n;++i)

	{

		a[i] = read();

	}

	build(root,1,n,0);

	scanf("%d",&m);

	char opt;

	int x,y;

	for(register int i = 1;i <= m;++i)

	{

		opt = getc();

		if(opt == 'I')

		{

			x = read();y = read();

			++n;

			insert(x,y);

		}

		if(opt == 'D')

		{

			x = read();

			--n;

			remove(x);

		}

		if(opt == 'R')

		{

			x = read();y = read();

			change(x,y);

		}

		if(opt == 'Q')

		{

			x = read();y = read();

			printf("%d\n",query(x,y));

		}

	}

	return 0;

}