題意：
給定一個數列，要求支持以下操作：
I x y 在第x個數所在位置插入數y并將后面的全部右移動一位
D x 刪除第x個位置上的數
R x y 將第x個位置上的數替換為y
Q x y 求[x,y]之間的最大子段和
做法：
如果不需要D和I操作那么線段樹可以完美支持
加入D和I操作后就只能用平衡樹維護了。
用splay搞搞就行..
1
#include <cstdio>
2#define max(a,b) ((a)>(b)?(a):(b))
3struct Tsplay
4
{
5
#define Lch(x) T[x].l
6 #define Rch(x) T[x].r
7 #define Par(x) T[x].p
8 #define Val(x) T[x].val
9 #define Sum(x) T[x].sum
10 #define Lms(x) T[x].lms
11 #define Rms(x) T[x].rms
12 #define Ms(x) T[x].ms
13 #define Size(x) T[x].size
14 int l,r,p,size;
15 int sum,ms,lms,rms,val;
16
} T[200005];
17
18int N,Que,root,tot,cnt,x,y;
19char cmd[105];
20
21inline void Tupdate(int x)
22{
23 Size(x)=Size(Lch(x))+1+Size(Rch(x));
24 Sum(x)=Sum(Lch(x))+Val(x)+Sum(Rch(x));
25 Lms(x)=max(Lms(Lch(x)),Sum(Lch(x))+Val(x)+Lms(Rch(x)));
26 Rms(x)=max(Rms(Rch(x)),Rms(Lch(x))+Val(x)+Sum(Rch(x)));
27 Ms(x)=Rms(Lch(x))+Val(x)+Lms(Rch(x));
28 if (Lch(x)) Ms(x)=max(Ms(x),Ms(Lch(x)));
29 if (Rch(x)) Ms(x)=max(Ms(x),Ms(Rch(x)));
30}
31inline void zig(int x)
32{
33 int y=Par(x),z=Par(y);
34 Lch(y)=Rch(x),Par(Lch(y))=Rch(x)=y;
35 if (Lch(z)==y) Lch(z)=x;
36 else Rch(z)=x;
37 Par(x)=z,Par(y)=x;
38 Tupdate(y);
39}
40inline void zag(int x)
41{
42 int y=Par(x),z=Par(y);
43 Rch(y)=Lch(x),Par(Rch(y))=Lch(x)=y;
44 if (Lch(z)==y) Lch(z)=x;
45 else Rch(z)=x;
46 Par(x)=z,Par(y)=x;
47 Tupdate(y);
48}
49inline void splay(int &root,int x)
50{
51 for (int y,z;Par(x);)
52
{
53 y=Par(x),z=Par(y);
54 if (!z)
55 if (Lch(y)==x) zig(x);
56 else zag(x);
57 else
58 if (Lch(z)==y)
59 if (Lch(y)==x) zig(y),zig(x);
60 else zag(x),zig(x);
61 else
62 if (Rch(y)==x) zag(y),zag(x);
63 else zig(x),zag(x);
64
}
65 Tupdate(root=x);
66}
67inline int Findkth(int root,int k)
68{
69 for (int p=root;;)
70 if (k<=Size(Lch(p))) p=Lch(p);
71 else
72 if (k<=Size(Lch(p))+1) return p;
73 else k-=Size(Lch(p))+1,p=Rch(p);
74}
75inline int Tjoin(int u,int v)
76{
77 if (!u) return v;
78 if (!v) return u;
79 int p=u;
80 for (;Rch(p);p=Rch(p));
81 splay(u,p);
82 return Rch(p)=v,Par(v)=p,p;
83}
84inline void D(int x)
85{
86 splay(root,x);
87 Par(Lch(x))=Par(Rch(x))=0;
88 root=Tjoin(Lch(x),Rch(x));
89 Tupdate(root);
90}
91inline void I(int x,int y)
92{
93 splay(root,x);
94 int v=Lch(x);
95 for (;Rch(v);v=Rch(v));
96 Rch(v)=++tot,Par(tot)=v,Size(tot)=1;
97 Sum(tot)=Ms(tot)=Lms(tot)=Rms(tot)=Val(tot)=y;
98 splay(root,tot);
99}
100inline void R(int x,int y)
101{
102 Val(x)=y;
103 splay(root,x);
104}
105inline void Q(int x,int y)
106{
107 splay(root,y);
108 Par(Lch(y))=0;
109 splay(Lch(y),x);
110 Par(x)=y;
111 printf("%d\n",Ms(Rch(x)));
112}
113int main()
114{
115 scanf("%d",&N);
116 for (int i=1;i<=N;++i)
117 {
118 scanf("%d",&Val(i));
119 Sum(i)=Ms(i)=Lms(i)=Rms(i)=Val(i);
120 Par(i)=i-1,Rch(i-1)=i,Size(i)=N-i+1;
121 splay(root,i);
122 }
123 splay(root,1),Par(N+1)=1,Lch(1)=N+1,Size(N+1)=1,splay(root,N+1);
124 splay(root,N),Par(N+2)=N,Rch(N)=N+2,Size(N+2)=1,splay(root,N+2);
125 tot=N+2;
126 for (scanf("%d",&Que);Que--;)
127 {
128 scanf("%s%d",cmd,&x);
129 if (cmd[0]=='D') D(Findkth(root,x+1));
130 else
131 {
132 scanf("%d",&y);
133 if (cmd[0]=='Q') Q(Findkth(root,x),Findkth(root,y+2));
134 else
135 if (cmd[0]=='I') I(Findkth(root,x+1),y);
136 else R(Findkth(root,x+1),y);
137 }
138 }
139 return 0;
140}
141