[NOI2005]维护数列

  1 #include <bits/stdc++.h>
  2 #define ll long long
  3 #define L(x) e[x].son[0]
  4 #define R(x) e[x].son[1]
  5 #define lx(x) e[x].left
  6 #define rx(x) e[x].right
  7 #define mx(x) e[x].mx
  8 #define sum(x) e[x].sum
  9 using namespace std;
 10 const int N = 1e6 + 7;
 11 const int inf = 0x3f3f3f3f;
 12 ll read() {
 13     ll re = 0, f = 1;
 14     char ch = getchar();
 15     while (ch < '0' || ch > '9') {if (ch == '-') f = -f; ch = getchar();}
 16     while ('0' <= ch && ch <= '9') {re = re * 10 + ch - '0'; ch = getchar();}
 17     return re * f;
 18 }
 19 int n, m, root, cnt;
 20 struct node{
 21     int val, father;
 22     int son[2];
 23     int siz;
 24     int sum, mx;
 25     int left, right;
 26     bool tag, rev;
 27 }e[N];
 28 int top, a[N], id[N], rub[N];
 29 void update(int x) {
 30     int l = L(x), r = R(x);
 31     sum(x) = sum(l) + sum(r) + e[x].val;
 32     e[x].siz = e[l].siz + e[r].siz + 1;
 33     mx(x) = max(mx(l), max(mx(r), rx(l) + e[x].val + lx(r)));
 34     lx(x) = max(lx(l), sum(l) + e[x].val + lx(r));
 35     rx(x) = max(rx(r), sum(r) + e[x].val + rx(l));
 36 }
 37 void pushdown(int x) {
 38     int l = L(x), r = R(x);
 39     if (e[x].tag) {
 40         e[x].tag = e[x].rev = false;
 41         if (l) {
 42             e[l].tag = true, e[l].val = e[x].val, sum(l) = e[x].val * e[l].siz;
 43             lx(l) = rx(l) = max(sum(l), 0);
 44             mx(l) = max(sum(l), e[l].val);
 45         }
 46         if (r) {
 47             e[r].tag = true, e[r].val = e[x].val, sum(r) = e[x].val * e[r].siz;
 48             lx(r) = rx(r) = max(sum(r), 0);
 49             mx(r) = max(sum(r), e[r].val);
 50         }
 51     }
 52     if (e[x].rev) {
 53         e[x].rev = false;
 54         e[l].rev ^= 1, e[r].rev ^= 1;
 55         swap(lx(l), rx(l)), swap(lx(r), rx(r));
 56         swap(L(l), R(l)), swap(L(r), R(r));
 57     }
 58 }
 59 void connect(int x, int fa, int Son) {
 60     e[x].father = fa;
 61     e[fa].son[Son] = x;
 62 }
 63 int identify(int x) {
 64     return L(e[x].father) == x ? 0 : 1;
 65 }
 66 void rotate(int x) {
 67     int fa = e[x].father, fason = identify(x);
 68     int gfa = e[fa].father, gfason = identify(fa);
 69     int B = e[x].son[fason ^ 1];
 70     connect(B, fa, fason), connect(fa, x, fason ^ 1);
 71     connect(x, gfa, gfason);
 72     update(fa), update(x);
 73 }
 74 void splay(int now, int to) {
 75     int tofa = e[to].father;
 76     while (e[now].father != tofa) {
 77         int fa = e[now].father, gfa = e[fa].father;
 78         if (gfa != tofa) {
 79             rotate(identify(now) == identify(fa) ? fa : now);
 80         }
 81         rotate(now);
 82     }
 83     if (to == root) root = now;
 84 }
 85 int kth(int rank) {
 86     int now = root;
 87     while (true) {
 88         pushdown(now);
 89         if (e[L(now)].siz >= rank) {
 90             now = L(now);
 91         } else {
 92             rank -= e[L(now)].siz + 1;
 93             if (!rank) return now;
 94             now = R(now);
 95         }
 96     }
 97 }
 98 int split(int k, int tot) {
 99     int x = kth(k), y = kth(k + tot + 1);
100     splay(x, root), splay(y, R(x));
101     return L(y);
102 }
103 void Reverse(int k, int tot) {
104     int x = split(k, tot), y = e[x].father;
105     if (!e[x].tag) {
106         e[x].rev ^= 1;
107         swap(L(x), R(x));
108         swap(lx(x), rx(x));
109         update(y), update(e[y].father);
110     }
111 }
112 int rubbish() {
113     if (!top) return ++cnt;
114     int x = rub[top--];
115     return x;
116 }
117 void build(int l, int r, int fa) {
118     int mid = (l + r) / 2;
119     int now = id[mid], pre = id[fa];
120     if (l == r) {
121         mx(now) = sum(now) = a[l];
122         e[now].tag = e[now].rev = false;
123         lx(now) = rx(now) = max(a[l], 0);
124         e[now].siz = 1;
125     }
126     if (l < mid) build(l, mid - 1, mid);
127     if (r > mid) build(mid + 1, r, mid);
128     e[now].val = a[mid], e[now].father = pre, e[now].tag = 0;
129     update(now);
130     e[pre].son[mid >= fa] = now;
131 }
132 void Insert(int k, int tot) {
133     for (int i = 1; i <= tot; i++) a[i] = read();
134     for (int i = 1; i <= tot; i++) {
135         id[i] = rubbish();
136     }
137     build(1, tot, 0);
138     int z = id[(1 + tot) / 2];
139     int x = kth(k + 1), y = kth(k + 2);
140     splay(x, root), splay(y, R(x));
141     connect(z, y, 0);
142     update(y), update(x);
143 }
144 void remove(int x) {
145     if (L(x)) remove(L(x));
146     if (R(x)) remove(R(x));
147     rub[++top] = x;
148     e[x].father = L(x) = R(x) = e[x].tag = e[x].rev = 0;
149 }
150 void Erase(int k, int tot) {
151     int x = split(k, tot), y = e[x].father;
152     remove(x);
153     L(y) = 0;
154     update(y), update(e[y].father);
155 }
156 void change(int k, int tot, int v) {
157     int x = split(k, tot), y = e[x].father;
158     e[x].val = v, e[x].tag = true;
159     sum(x) = e[x].siz * v;
160     lx(x) = rx(x) = max(sum(x), 0);
161     mx(x) = max(sum(x), e[x].val);
162     update(y), update(e[y].father);
163 }
164 int query(int k, int tot) {
165     int x = split(k, tot);
166     return sum(x);
167 }
168 int main () {
169     n = read(), m = read();
170     mx(0) = a[1] = a[n + 2] = -inf;
171     for (int i = 1; i <= n; i++) a[i + 1] = read();
172     for (int i = 1; i <= n + 2; i++) id[i] = i;
173     build(1, n + 2, 0);
174     root = (n + 3) / 2;
175     cnt = n + 2;
176     int k, tot, v;
177     string s;
178     while (m--) {
179         cin >> s;
180         if (s != "MAX-SUM") {
181             k = read(), tot = read();
182         } else {
183             printf("%d
", mx(root));
184         }
185         if (s == "INSERT") Insert(k, tot);
186         if (s == "DELETE") Erase(k, tot);
187         if (s == "MAKE-SAME") {
188             v = read();
189             change(k, tot, v);
190         }
191         if (s == "REVERSE") Reverse(k, tot);
192         if (s == "GET-SUM") printf("%d
", query(k, tot));
193     }
194     return 0;
195 }