laekov

看上去挺水水水水水水水水的一道平衡树维护序列的数据结构题啊。

先用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));

}

}

}