SPOJ/GSS6.cc

   1 #include <cstdio>
   2 #include <cctype>
   3 #include <algorithm>
   4
   5 using namespace std;
   6
   7 const int maxn = 2e5 + 10, inf = 1 << 25;
   8
   9 struct node {
  10   node *p, *ch[2];
  11   int size;
  12   int lx, rx, mx, sum, val;
  13   inline bool dir() { return this == p->ch[1]; }
  14   inline void setc(node*, int);
  15   inline void update();
  16 };
  17
  18 node pool[maxn];
  19 node *nil = pool, *tot = nil + 1, *root;
  20
  21 inline void node::setc(node *c, int d) {
  22   ch[d] = c;
  23   c->p = this;
  24 }
  25
  26 inline void node::update() {
  27   size = ch[0]->size + 1 + ch[1]->size;
  28   sum = ch[0]->sum + val + ch[1]->sum;
  29   lx = max(ch[0]->lx, ch[0]->sum + val + max(ch[1]->lx, 0));
  30   rx = max(max(ch[0]->rx, 0) + val + ch[1]->sum, ch[1]->rx);
  31   mx = max(max(ch[0]->mx, ch[1]->mx), max(ch[0]->rx, 0) + val + max(ch[1]->lx, 0));
  32 }
  33
  34 inline node* makenode(int x) {
  35   tot->ch[0] = tot->ch[1] = tot->p = nil;
  36   tot->size = 1;
  37   tot->lx = tot->rx = tot->mx = tot->sum = tot->val = x;
  38   return tot++;
  39 }
  40
  41 inline void rotate(node *u) {
  42   node *v = u->p;
  43   int d = u->dir();
  44   v->p->setc(u, v->dir());
  45   v->setc(u->ch[d^1], d);
  46   u->setc(v, d^1);
  47   v->update();
  48   u->update();
  49   if (v == root) root = u;
  50 }
  51
  52 inline void splay(node *u, node *target = nil) {
  53   while (u->p != target) {
  54     if (u->p->p == target)
  55       rotate(u);
  56     else
  57       (u->dir() == u->p->dir()) ? (rotate(u->p), rotate(u)) : (rotate(u), rotate(u));
  58   }
  59   u->update();
  60 }
  61
  62 inline node* select(int pos) {
  63   node *u = root;
  64   for (;;) {
  65     int k = u->ch[0]->size;
  66     if (k == pos) break;
  67     if (k < pos) {
  68       pos -= (k + 1);
  69       u = u->ch[1];
  70     } else {
  71       u = u->ch[0];
  72     }
  73   }
  74   splay(u);
  75   return u;
  76 }
  77
  78 int n;
  79
  80 inline void init() {
  81   nil->ch[0] = nil->ch[1] = nil->p = nil;
  82   nil->mx = nil->lx = nil->rx = nil->val = -inf;
  83   root = makenode(-inf);
  84   node *u = root, *v;
  85   for (int i = 1, x; i <= n; ++i) {
  86     scanf("%d", &x);
  87     v = makenode(x);
  88     u->setc(v, 1);
  89     u = v;
  90   }
  91   v = makenode(-inf);
  92   u->setc(v, 1);
  93   splay(v);
  94 }
  95
  96 inline void ins(int pos, int val) {
  97   node *u = select(pos - 1), *v = makenode(val);
  98   splay(u);
  99   v->setc(u->ch[1], 1);
 100   u->setc(v, 1);
 101   splay(v);
 102 }
 103
 104 inline void del(int pos) {
 105   node *u = select(pos - 1), *v = select(pos + 1);
 106   splay(u);
 107   splay(v, u);
 108   v->setc(nil, 0);
 109   splay(v);
 110 }
 111
 112 inline void replace(int pos, int val) {
 113   node *u = select(pos);
 114   splay(u);
 115   u->val = val;
 116   u->update();
 117 }
 118
 119 inline int query(int l, int r) {
 120   node *u = select(l - 1), *v = select(r + 1);
 121   splay(u);
 122   splay(v, u);
 123   return v->ch[0]->mx;
 124 }
 125
 126 int main() {
 127   scanf("%d", &n);
 128   init();
 129   int tcase;
 130   scanf("%d", &tcase);
 131   char op;
 132   int a, b;
 133   while (tcase--) {
 134     scanf(" %c%d", &op, &a);
 135     switch (op) {
 136       case 'D':
 137         del(a);
 138         break;
 139       default:
 140         scanf("%d", &b);
 141         switch(op) {
 142           case 'I':
 143             ins(a, b);
 144             break;
 145           case 'Q':
 146             printf("%d\n", query(a, b));
 147             break;
 148           case 'R':
 149             replace(a, b);
 150             break;
 151         }
 152         break;
 153     }
 154   }
 155   return 0;
 156 }