splay 入门题。
- #include < iostream > #include < cstdio > #include < cstdlib > #include < cstring > #include < ctime > #include < cmath > #include < algorithm > #include < iomanip > #include < queue > #include < set > using namespace std;#define LL long long#define FILE "dealing"#define mid((l + r) >> 1)#define pii pair < int,
- int > #define up(i, j, n) for (int i = (j); i <= (n); i++) LL read() {
- LL x = 0,
- f = 1,
- ch = getchar();
- while (ch < '0' || ch > '9') {
- if (ch == ' - ') f = -1;
- ch = getchar();
- }
- while (ch >= '0' && ch <= '9') {
- x = (x << 1) + (x << 3) + ch - '0';
- ch = getchar();
- }
- return f * x;
- }
- const int maxn = 605000,
- inf = 1000000000;
- int n,
- m;
- int a[maxn];
- int fa[maxn],
- c[maxn][2],
- sum[maxn],
- lm[maxn],
- rm[maxn],
- Max[maxn],
- rev[maxn],
- f[maxn],
- q[maxn],
- siz[maxn],
- val[maxn],
- h[maxn],
- root,
- head = 1,
- tail = 0;
- void updata(int x) { //updata sum siz maxse
- if (!x) return;
- siz[x] = siz[c[x][0]] + siz[c[x][1]] + 1;
- h[x] = max(h[c[x][0]], h[c[x][1]]);
- h[x] = max(h[x], val[x]);
- sum[x] = sum[c[x][0]] + sum[c[x][1]] + val[x];
- lm[x] = max(lm[c[x][0]], sum[c[x][0]] + val[x] + lm[c[x][1]]);
- rm[x] = max(rm[c[x][1]], sum[c[x][1]] + val[x] + rm[c[x][0]]);
- Max[x] = max(Max[c[x][0]], Max[c[x][1]]);
- Max[x] = max(Max[x], rm[c[x][0]] + val[x] + lm[c[x][1]]);
- }
- inline void add(int x) {
- q[++tail] = x;
- if (tail == 600000) tail = 0;
- }
- inline int pop() {
- if (head == 600001) head = 1;
- return q[head++];
- }
- void change(int x, int c) {
- if (!x) return;
- val[x] = f[x] = h[x] = c;
- Max[x] = lm[x] = rm[x] = max(0, siz[x] * c);
- sum[x] = siz[x] * c;
- }
- void revv(int x) {
- if (!x) return;
- rev[x] ^= 1;
- swap(lm[x], rm[x]);
- swap(c[x][0], c[x][1]);
- }
- void pushdown(int x) {
- if (!x) return;
- if (rev[x]) rev[x] = 0,
- revv(c[x][0]),
- revv(c[x][1]);
- if (f[x] != inf) change(c[x][0], f[x]),
- change(c[x][1], f[x]),
- f[x] = inf;
- }
- void rotate(int x) {
- if (!x) return;
- int y = fa[x],
- z = fa[y],
- d = c[y][1] == x;
- fa[y] = x,
- fa[x] = z;
- if (c[x][d ^ 1]) fa[c[x][d ^ 1]] = y;
- c[y][d] = c[x][d ^ 1];
- c[x][d ^ 1] = y;
- if (z) c[z][c[z][1] == y] = x;
- updata(y),
- updata(x);
- }
- int p[maxn],
- top = 0;
- void splay(int x, int S) {
- if (!x) return;
- for (int i = x; i; i = fa[i]) p[++top] = i;
- while (top) pushdown(p[top--]);
- while (fa[x] != S) {
- int y = fa[x],
- z = fa[y];
- if (z != S) {
- if ((c[y][1] == x) ^ (c[z][1] == y)) rotate(x);
- else rotate(y);
- }
- rotate(x);
- }
- if (!S) root = x;
- }
- int find(int k) { //返回大于k个数的splay节点
- int x = root;
- pushdown(x);
- while (siz[c[x][0]] != k) {
- pushdown(x);
- if (siz[c[x][0]] > k) x = c[x][0];
- else k = k - 1 - siz[c[x][0]],
- x = c[x][1];
- }
- splay(x, 0);
- return x;
- }
- int t[4000000];
- void build(int & x, int Fa, int l, int r) {
- if (l > r) return void(x = 0);
- if (!x) x = pop();
- lm[x] = rm[x] = Max[x] = max(0, h[x] = sum[x] = val[x] = t[mid]);
- fa[x] = Fa;
- siz[x] = 1;
- f[x] = inf;
- if (l == r) return;
- build(c[x][0], x, l, mid - 1);
- build(c[x][1], x, mid + 1, r);
- updata(x);
- }
- void insert(int pos, int cnt) {
- int x = find(pos),
- y = find(pos + 1);
- splay(x, 0);
- splay(y, root);
- build(c[y][0], y, 1, cnt);
- updata(y),
- updata(x);
- }
- void Det(int x) {
- if (!x) return;
- Det(c[x][0]);
- Det(c[x][1]);
- fa[x] = c[x][0] = c[x][1] = sum[x] = lm[x] = rm[x] = Max[x] = rev[x] = siz[x] = val[x] = 0;
- f[x] = inf;
- h[x] = -inf;
- add(x);
- }
- void delet(int pos, int cnt) {
- int x = find(pos - 1),
- y = find(pos + cnt);
- splay(x, 0);
- splay(y, root);
- Det(c[y][0]);
- c[y][0] = 0;
- updata(y),
- updata(x);
- }
- void Change(int pos, int cnt, int w) {
- int x = find(pos - 1),
- y = find(pos + cnt);
- splay(x, 0);
- splay(y, root);
- change(c[y][0], w);
- updata(y),
- updata(x);
- }
- void reverse(int pos, int cnt) {
- int x = find(pos - 1),
- y = find(pos + cnt);
- splay(x, 0);
- splay(y, root);
- revv(c[y][0]);
- updata(y),
- updata(x);
- }
- void getsum(int pos, int cnt) {
- int x = find(pos - 1),
- y = find(pos + cnt);
- splay(x, 0);
- splay(y, root);
- printf("%d\n", sum[c[y][0]]);
- updata(y),
- updata(x);
- }
- void maxseg() {
- int x = find(0),
- y = find(siz[root] - 1);
- splay(x, 0);
- splay(y, root);
- printf("%d\n", (!Max[c[y][0]]) ? h[c[y][0]] : Max[c[y][0]]);
- }
- int main() {
- //freopen("dealing.in","r",stdin);
- //freopen("dealing.out","w",stdout);
- n = read(),
- m = read();
- memset(val, -10, sizeof(val));
- f[0] = inf;
- up(i, 1, 600000) add(i);
- t[1] = -inf,
- t[2] = inf;
- build(root, 0, 1, 2);
- h[0] = -inf;
- up(i, 1, n) t[i] = a[i] = read();
- insert(0, n);
- char s[10];
- int pos,
- cnt,
- w;
- up(i, 1, m) {
- scanf("%s", s);
- if (s[0] == 'I') {
- pos = read(),
- cnt = read();
- up(j, 1, cnt) t[j] = read();
- if (!cnt) continue;
- insert(pos, cnt);
- }
- if (s[0] == 'D') {
- pos = read(),
- cnt = read();
- if (!cnt) continue;
- delet(pos, cnt);
- }
- if (s[2] == 'K') {
- pos = read(),
- cnt = read(),
- w = read();
- if (!cnt) continue;
- Change(pos, cnt, w);
- }
- if (s[0] == 'R') {
- pos = read(),
- cnt = read();
- if (!cnt) continue;
- reverse(pos, cnt);
- }
- if (s[0] == 'G') {
- pos = read(),
- cnt = read();
- if (!cnt) {
- printf("0\n");
- continue;
- }
- getsum(pos, cnt);
- }
- if (s[2] == 'X') maxseg();
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-1945469.html