看上去挺水水水水水水水水的一道平衡树维护序列的数据结构题啊。
先用split-merge tree写，tle。
然后改用splay，tle。
最后据说把splay的裸数组改到struct node里就能过。于是再写了一个程序来改代码。
不 带 这 么 坑 的 ！
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <memory.h>
#include <algorithm>
using namespace std;
/*#define readInt(_s_) {\
int _d_;\
bool _nag_ = 0;\
_s_ = 0;\
while (!isdigit(_d_ = getchar()))\
if (_d_ == '-')\
_nag_ = 1;\
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\
if (_nag_)\
_s_ = - _s_;\
}*/
#define readInt(_s_) scanf("%d",&_s_);
#define readOpt(_s_) {\
do\
_s_ = getchar();\
while (_s_ != 'I' && _s_ != 'D' && _s_ != 'R' && _s_ != 'Q');\
}
const int maxn = 200009;
struct node {
int vl, ls, rs, pt, sz, sl, sr, sm, s;
};
int v0[maxn];
int n, m, rt, tn, cr;
node tree[maxn];
inline void initDat(const int& p, const int& v0) {
tree[p]. sl = v0;
tree[p]. sr = v0;
tree[p]. sm = v0;
tree[p]. s = v0;
}
inline void mergeDat(const int& p, const int& a, const int& b) {
int nl = max(tree[a]. sl, tree[a]. sm + tree[b]. sl);
int nr = max(tree[b]. sr, tree[b]. sm + tree[a]. sr);
int nm = tree[a]. sm + tree[b]. sm;
int nx = max(max(tree[a]. s, tree[b]. s), tree[a]. sr + tree[b]. sl);
tree[p]. sl = nl;
tree[p]. sr = nr;
tree[p]. sm = nm;
tree[p]. s = nx;
}
int newNode(int v0) {
++ tn;
tree[tn]. vl = v0;
tree[tn]. ls = 0;
tree[tn]. rs = 0;
tree[tn]. sz = 1;
initDat(tn, v0);
return tn;
}
#define update(_p_) {\
tree[_p_]. sz = tree[tree[_p_]. ls]. sz + tree[tree[_p_]. rs]. sz + 1;\
initDat(_p_, tree[_p_]. vl);\
if (tree[_p_]. ls)\
mergeDat(_p_, tree[_p_]. ls, _p_);\
if (tree[_p_]. rs)\
mergeDat(_p_, _p_, tree[_p_]. rs);\
}
inline void lRot(int q) {
int p = tree[q]. pt, a = tree[p]. pt;
if (tree[q]. rs)
tree[tree[q]. rs]. pt = p;
tree[p]. ls = tree[q]. rs;
tree[q]. rs = p;
tree[q]. pt = a;
tree[p]. pt = q;
if (a) {
if (p == tree[a]. ls)
tree[a]. ls = q;
else
tree[a]. rs = q;
}
update(p);
update(q);
}
inline void rRot(int q) {
int p = tree[q]. pt, a = tree[p]. pt;
if (tree[q]. ls)
tree[tree[q]. ls]. pt = p;
tree[p]. rs = tree[q]. ls;
tree[q]. ls = p;
tree[q]. pt = a;
tree[p]. pt = q;
if (a) {
if (p == tree[a]. ls)
tree[a]. ls = q;
else
tree[a]. rs = q;
}
update(p);
update(q);
}
void splay(int q) {
while (tree[q]. pt) {
int p = tree[q]. pt, a = tree[p]. pt;
if (!a || !tree[a]. pt) {
if (q == tree[p]. ls)
lRot(q);
else
rRot(q);
}
else {
if (p == tree[a]. ls) {
if (q == tree[p]. ls) {
lRot(p);
lRot(q);
}
else {
rRot(q);
lRot(q);
}
}
else {
if (q == tree[p]. rs) {
rRot(p);
rRot(q);
}
else {
lRot(q);
rRot(q);
}
}
}
}
}
int makeTree(int l, int r) {
if (l > r)
return 0;
int x = (l + r) >> 1;
int p = newNode(v0[x]);
tree[p]. ls = makeTree(l, x - 1);
tree[tree[p]. ls]. pt = p;
tree[p]. rs = makeTree(x + 1, r);
tree[tree[p]. rs]. pt = p;
update(p);
return p;
}
int kth(int p, int k) {
while (p)
if (tree[tree[p]. ls]. sz + 1 == k)
break;
else if (tree[tree[p]. ls]. sz >= k)
p = tree[p]. ls;
else
k -= tree[tree[p]. ls]. sz + 1, p = tree[p]. rs;
return p;
}
int query(int rt, int l, int r) {
int p = kth(rt, l), q = kth(rt, r + 2);
splay(p);
splay(q);
cr = q;
return tree[tree[p]. rs]. s;
}
void dispTree(int p, bool ed = 1) {
if (!p)
return;
dispTree(tree[p]. ls, 0);
printf("%d ", tree[p]. vl);
dispTree(tree[p]. rs, 0);
if (ed)
putchar(10);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
readInt(n);
rt = 0;
tn = 0;
for (int i = 1; i <= n; ++ i)
readInt(v0[i]);
v0[0] = 0;
v0[n + 1] = 0;
cr = makeTree(0, n + 1);
readInt(m);
while (m --) {
char opt;
int p, v, l, r, rt = cr;
readOpt(opt);
//dispTree(cr);
if (opt == 'I') {
readInt(p);
readInt(v);
int q = kth(rt, p), u = newNode(v);
splay(q);
cr = q;
if (tree[q]. rs)
tree[tree[q]. rs]. pt = u;
tree[u]. rs = tree[q]. rs;
update(u);
tree[q]. rs = u;
tree[u]. pt = q;
update(q);
if (tree[u]. rs) {
cr = tree[u]. rs;
splay(cr);
}
++ n;
}
else if (opt == 'D') {
readInt(p);
int q = kth(rt, p + 1);
splay(q);
cr = q;
if (!tree[q]. rs)
tree[tree[q]. ls]. pt = 0;
else {
int x = kth(tree[q]. rs, 1);
tree[tree[q]. rs]. pt = 0;
splay(x);
cr = x;
tree[x]. ls = tree[q]. ls;
if (tree[q]. ls)
tree[tree[q]. ls]. pt = x;
update(x);
cr = kth(x, tree[x]. sz >> 1);
splay(cr);
}
-- n;
}
else if (opt == 'R') {
readInt(p);
readInt(v);
int q = kth(rt, p + 1);
splay(q);
cr = q;
tree[q]. vl = v;
update(q);
}
else if (opt == 'Q') {
readInt(l);
readInt(r);
printf("%d\n", query(rt, l, r));
}
}
}