SPOJ_4487
其实这个题目和GSS1是差不多的，只不过由于有增加和删除的操作，这样用线段树就搞不定了，因此可以维护一个splay来实现这些操作。
但是一开始我写出的程序总是TLE，而和网上一些AC的程序对照之后发现无非有两点很不同的地方，一个是他们都用了结构体，另一个是他们都用了指针。在百思不得其解之际，我把以前的若干个数组仿照一个AC的程序写成了结构体，就像下面这样：
struct Splay{ int left, right, pre, size, sum, mc, key, lc, rc; #define left(x) sp[x].left #define right(x) sp[x].right #define pre(x) sp[x].pre #define size(x) sp[x].size #define sum(x) sp[x].sum #define mc(x) sp[x].mc #define key(x) sp[x].key #define lc(x) sp[x].lc #define rc(x) sp[x].rc}sp[MAXD]; 尼玛……居然AC了……
不知道这是不是也算底层优化……各位TLE了的同仁不妨试试写成结构体……
#include#include #include #define MAXD 200010#define INF 0x3f3f3f3fint N, T, a[MAXD], node;struct Splay{ int left, right, pre, size, sum, mc, key, lc, rc; #define left(x) sp[x].left #define right(x) sp[x].right #define pre(x) sp[x].pre #define size(x) sp[x].size #define sum(x) sp[x].sum #define mc(x) sp[x].mc #define key(x) sp[x].key #define lc(x) sp[x].lc #define rc(x) sp[x].rc}sp[MAXD];int Max(int x, int y){ return x > y ? x : y;}void newnode(int &cur, int v){ cur = ++ node; size(cur) = 1; key(cur) = sum(cur) = mc(cur) = lc(cur) = rc(cur) = v; left(cur) = right(cur) = 0;}void update(int cur){ int ls = left(cur), rs = right(cur); size(cur) = size(ls) + size(rs) + 1; sum(cur) = sum(ls) + sum(rs) + key(cur); mc(cur) = Max(rc(ls), 0) + key(cur) + Max(lc(rs), 0); mc(cur) = Max(mc(cur), Max(mc(ls), mc(rs))); lc(cur) = Max(lc(ls), sum(ls) + key(cur) + Max(lc(rs), 0)); rc(cur) = Max(rc(rs), sum(rs) + key(cur) + Max(rc(ls), 0));}void leftrotate(int cur){ int k = right(cur), fa = pre(cur); right(cur) = left(k); pre(right(cur)) = cur; left(k) = cur; pre(cur) = k; pre(k) = fa; right(fa) == cur ? right(fa) = k : left(fa) = k; update(cur);}void rightrotate(int cur){ int k = left(cur), fa = pre(cur); left(cur) = right(k); pre(left(cur)) = cur; right(k) = cur; pre(cur) = k; pre(k) = fa; right(fa) == cur ? right(fa) = k : left(fa) = k; update(cur);}void build(int &cur, int x, int y, int fa){ int mid = (x + y) >> 1; newnode(cur, a[mid]); pre(cur) = fa; if(x == y) return ; if(x < mid) build(left(cur), x, mid - 1, cur); if(mid < y) build(right(cur), mid + 1, y, cur); update(cur);}void splay(int x, int goal){ int y, z; for(;;) { if((y = pre(x)) == goal) break; if((z = pre(y)) == goal) right(y) == x ? leftrotate(y) : rightrotate(y); else { if(right(z) == y) right(y) == x ? (leftrotate(z), leftrotate(y)) : (rightrotate(y), leftrotate(z)); else left(y) == x ? (rightrotate(z), rightrotate(y)) : (leftrotate(y), rightrotate(z)); } } if(goal == 0) T = x; update(x);}void rotateto(int k, int goal){ int cur = T, n; for(;;) { n = size(left(cur)) + 1; if(n == k) break; if(k < n) cur = left(cur); else k -= n, cur = right(cur); } splay(cur, goal);}void init(){ int i; for(i = 1; i <= N; i ++) scanf("%d", &a[i]); node = size(0) = sum(0) = 0; mc(0) = lc(0) = rc(0) = -INF; newnode(T, 0), newnode(right(T), 0); pre(right(T)) = T; key(T) = key(right(T)) = 0; if(N) build(left(right(T)), 1, N, right(T)); update(right(T)), update(T);}void Delete(int x){ rotateto(x, 0), rotateto(x + 2, T); left(right(T)) = 0; update(right(T)), update(T);}void Insert(int x, int y){ rotateto(x, 0), rotateto(x + 1, T); newnode(left(right(T)), y); pre(node) = right(T); update(right(T)), update(T);}void Replace(int x, int y){ rotateto(x + 1, 0); key(T) = y; update(T);}void Query(int x, int y){ rotateto(x, 0), rotateto(y + 2, T); printf("%d\n", mc(left(right(T))));}void solve(){ int i, q, x, y; char op[5]; scanf("%d", &q); for(i = 0; i < q; i ++) { scanf("%s", op); if(op[0] == 'D') { scanf("%d", &x); Delete(x); } else { scanf("%d%d", &x, &y); if(op[0] == 'I') Insert(x, y); else if(op[0] == 'R') Replace(x, y); else Query(x, y); } }}int main(){ while(scanf("%d", &N) == 1) { init(); solve(); } return 0;}