[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 y = e[x].father;
 68     int yson = identify(x);
 69     int mroot = e[y].father;
 70     int mrootson = identify(y);
 71     int B = e[x].son[yson ^ 1];
 72     connect(B, y, yson), connect(y, x, yson ^ 1), connect(x, mroot, mrootson);
 73     update(y), update(x);
 74 }
 75 void splay(int at, int to) {
 76     int tofa = e[to].father;
 77     while (e[at].father != tofa) {
 78         int fa = e[at].father;
 79         int gfa = e[fa].father;
 80         if (gfa != tofa) {
 81             if (identify(at) != identify(fa)) {
 82                 rotate(at);
 83             } else {
 84                 rotate(fa);
 85             }
 86         }
 87         rotate(at);
 88     }
 89     if (to == root) root = at;
 90 }
 91 int kth(int rank) {
 92     int now = root;
 93     while (true) {
 94         pushdown(now);
 95         if (e[L(now)].siz >= rank) {
 96             now = L(now);
 97         } else {
 98             if (e[L(now)].siz + 1 == rank) {
 99                 return now;
100             } else {
101                 rank -= e[L(now)].siz + 1;
102                 now = R(now);
103             }
104         }
105     }
106 }
107 int split(int k, int tot) {
108     int x = kth(k), y = kth(k + tot + 1);
109     splay(x, root), splay(y, R(x));
110     return L(y);
111 }
112 void Reverse(int k, int tot) {
113     int x = split(k, tot), y = e[x].father;
114     if (!e[x].tag) {
115         e[x].rev ^= 1;
116         swap(L(x), R(x));
117         swap(lx(x), rx(x));
118         update(y), update(e[y].father);
119     }
120 }
121 int rubbish() {
122     if (!top) {
123         return ++cnt;
124     }
125     int x = rub[top--];
126     return x;
127 }
128 void build(int l, int r, int fa) {
129     int mid = (l + r) / 2;
130     int now = id[mid], pre = id[fa];
131     if (l == r) {
132         mx(now) = sum(now) = a[l];
133         e[now].tag = e[now].rev = false;
134         lx(now) = rx(now) = max(a[l], 0);
135         e[now].siz = 1;
136     }
137     if (l < mid) build(l, mid - 1, mid);
138     if (r > mid) build(mid + 1, r, mid);
139     e[now].val = a[mid], e[now].father = pre, e[now].tag = 0;
140     update(now);
141     e[pre].son[mid >= fa] = now;
142 }
143 void Insert(int k, int tot) {
144     for (int i = 1; i <= tot; i++) a[i] = read();
145     for (int i = 1; i <= tot; i++) {
146         id[i] = rubbish();
147     }
148     build(1, tot, 0);
149     int z = id[(1 + tot) / 2];
150     int x = kth(k + 1), y = kth(k + 2);
151     splay(x, root), splay(y, R(x));
152     connect(z, y, 0);
153     update(y), update(x);
154 }
155 void remove(int x) {
156     if (L(x)) remove(L(x));
157     if (R(x)) remove(R(x));
158     rub[++top] = x;
159     e[x].father = L(x) = R(x) = e[x].tag = e[x].rev = 0;
160 }
161 void Erase(int k, int tot) {
162     int x = split(k, tot), y = e[x].father;
163     remove(x);
164     L(y) = 0;
165     update(y), update(e[y].father);
166 }
167 void change(int k, int tot, int v) {
168     int x = split(k, tot), y = e[x].father;
169     e[x].val = v, e[x].tag = true;
170     sum(x) = e[x].siz * v;
171     lx(x) = rx(x) = max(sum(x), 0);
172     mx(x) = max(sum(x), e[x].val);
173     update(y), update(e[y].father);
174 }
175 int query(int k, int tot) {
176     int x = split(k, tot);
177     return sum(x);
178 }
179 int main () {
180     n = read(), m = read();
181     mx(0) = a[1] = a[n + 2] = -inf;
182     for (int i = 1; i <= n; i++) {
183         a[i + 1] = read();
184     }
185     for (int i = 1; i <= n + 2; i++) {
186         id[i] = i;
187     }
188     build(1, n + 2, 0);
189     root = (n + 3) / 2;
190     cnt = n + 2;
191     int k, tot, v;
192     string s;
193     while (m--) {
194         cin >> s;
195         if (s != "MAX-SUM") {
196             k = read(), tot = read();
197         } else {
198             printf("%d\n", mx(root));
199         }
200         if (s == "INSERT") {
201             Insert(k, tot);
202         }
203         if (s == "DELETE") {
204             Erase(k, tot);
205         }
206         if (s == "MAKE-SAME") {
207             v = read();
208             change(k, tot, v);
209         }
210         if (s == "REVERSE") {
211             Reverse(k, tot);
212         }
213         if (s == "GET-SUM") {
214             printf("%d\n", query(k, tot));
215         }
216     }
217     return 0;
218 }