[NOI 2005] 维修数列

题目链接

[BZOJ 1500] [NOI 2005] 维修数列

题解

高档题。题意大概是给定一组数列和一定的操作,包含插入、删除、修改、翻转、求和、求和最大的子列。
这种包含了翻转、删除、插入等操作的维护序列问题很容易校内感到splay。
套模板即可,不过写起来很麻烦。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 500005;
const int INF = 1 << 30;
int i, j, k, l, n, m, ans, root, posi;
int f[maxn], a[maxn], d[maxn], b[maxn], x, y, key[maxn], shan[maxn], num, zhi, son[maxn][2];
string s;

struct node {
    int maxSum, sum, size, l, r, flag, add;
}tree[maxn];

void update(int x) {
    if (!x)return;
    tree[x].size = 1 + tree[son[x][0]].size + tree[son[x][1]].size;
    tree[x].sum = key[x] + tree[son[x][0]].sum + tree[son[x][1]].sum;
    tree[x].l = max(tree[son[x][0]].l, tree[son[x][0]].sum + key[x] + tree[son[x][1]].l);
    tree[x].r = max(tree[son[x][1]].r, tree[son[x][1]].sum + key[x] + tree[son[x][0]].r);
    tree[x].maxSum = max(max(tree[son[x][0]].maxSum, tree[son[x][1]].maxSum), tree[son[x][0]].r + tree[son[x][1]].l + key[x]);
}

void makesame(int x, int y) {
    if (!x)return;
    tree[x].sum = tree[x].size*y;
    key[x] = y; tree[x].add = y;
    if (y>0)tree[x].l = tree[x].r = tree[x].maxSum = tree[x].sum;
    else tree[x].l = tree[x].r = 0, tree[x].maxSum = y;
}

bool issoneq(int x) {
    if (son[f[x]][0] == x)return 0; return 1;
}

void rotate(int x) {
    int y = f[x], z = issoneq(x);
    son[y][z] = son[x][1 - z];
    if (son[x][1 - z])f[son[x][1 - z]] = y; f[x] = f[y];
    if (f[y])son[f[y]][issoneq(y)] = x;
    f[y] = x; son[x][1 - z] = y;
    update(y); update(x);
}

void overturn(int x) {
    if (!x)return;
    swap(son[x][0], son[x][1]);
    swap(tree[x].l, tree[x].r);
    tree[x].flag ^= 1;
}

void down(int x) {
    if (!x)return;
    if (tree[x].flag) {
        overturn(son[x][0]);
        overturn(son[x][1]);
        tree[x].flag = 0;
    }
    if (tree[x].add != maxn) {
        makesame(son[x][0], tree[x].add);
        makesame(son[x][1], tree[x].add);
        tree[x].add = maxn;
    }
}

void remove(int x, int y) {
    do {
        d[++d[0]] = x;
        x = f[x];
    } while (x != y);
    while (d[0])down(d[d[0]--]);
}

int insert(int x) {
    int temp;
    if (shan[0])temp = shan[shan[0]--]; else temp = ++num;
    key[temp] = tree[temp].sum = tree[temp].maxSum = x; tree[temp].size = 1; tree[temp].l = tree[temp].r = max(0, x);
    f[temp] = tree[temp].flag = son[temp][0] = son[temp][1] = 0; tree[temp].add = maxn;
    return temp;
}

void splay(int x, int y) {
    if (x == y)return;
    remove(x, y);
    while (f[x] != y) {
        if (f[f[x]] != y)if (issoneq(f[x]) == issoneq(x))rotate(f[x]); else rotate(x);
        rotate(x);
    }
    if (!y)root = x;
}

int build(int l, int r, int y) {
    if (l>r)return 0;
    int mid = (l + r) / 2;
    int x = insert(a[mid]); f[x] = y;
    if (l == r)return x;
    son[x][0] = build(l, mid - 1, x);
    son[x][1] = build(mid + 1, r, x);
    update(x);
    return x;
}

int findpos(int x, int k) {
    down(x);
    if (tree[son[x][0]].size + 1 == k)return x;
    if (tree[son[x][0]].size + 1>k)return findpos(son[x][0], k);
    else return findpos(son[x][1], k - tree[son[x][0]].size - 1);
}

void del(int x) {
    if (!x)return;
    shan[++shan[0]] = x;
    del(son[x][0]); del(son[x][1]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    tree[0].maxSum = -INF;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    root = build(0, n + 1, 0);

    while (m--) {
        cin >> s;
        if (s[0] == 'I') {
            cin >> posi >> k; posi++;

            for (int i = 1; i <= k; i++)
                cin >> a[i];

            x = findpos(root, posi); splay(x, 0);
            y = findpos(root, posi + 1); splay(y, x);

            son[y][0] = build(1, k, y);

            update(y); update(x);
        }
        else if (s[0] == 'D') {
            cin >> posi >> k; posi++;

            x = findpos(root, posi - 1); splay(x, 0);
            y = findpos(root, posi + k); splay(y, x);

            del(son[y][0]);
            son[y][0] = 0;

            update(y); update(x);
        }
        else if (s[2] == 'K') {
            cin >> posi >> k >> zhi; posi++;

            x = findpos(root, posi - 1); splay(x, 0);
            y = findpos(root, posi + k); splay(y, x);

            makesame(son[y][0], zhi);

            update(y); update(x);
        }
        else if (s[0] == 'R') {
            cin >> posi >> k; posi++;

            x = findpos(root, posi - 1); splay(x, 0);
            y = findpos(root, posi + k); splay(y, x);

            overturn(son[y][0]);

            update(y); update(x);
        }
        else if (s[0] == 'G') {
            cin >> posi >> k; posi++;

            x = findpos(root, posi - 1); splay(x, 0);
            y = findpos(root, posi + k); splay(y, x);

            cout << tree[son[y][0]].sum << endl;
        }
        else if (s[2] == 'X') {
            x = findpos(root, 1); splay(x, 0);
            y = findpos(root, tree[root].size); splay(y, x);

            cout << tree[son[y][0]].maxSum << endl;
        }
    }
}

标签: data structures

添加新评论