[NOI2005] 维护数列

一道锻炼代码能力的好(毒瘤)题!

历经 \(10h+\) , 终于过了这道题...用指针的人太少了, 只能自己查错, 而且由于空指针的存在, 指针本身需要特判的情况就更多. 但是无奈对于指针の爱...唉~

这道题本身没有任何思维难度, 只要会一棵趁手的, 支持区间反转的平衡树就够了, 这里我选择我最爱的, 最容易理解也最容易写的 \(FHQ\ Treap\) .

本身没有难度, 我就不多说了, 但是由于支持的操作较为蛋疼, 加上指针党比较少, 所以.

指针党看这里!!!

这里主要是针对指针党, 因为指针党数量少, 而且指针本身需要注意的就更多, 所以嘛...

空指针

不管是什么操作, 在不保证当前节点不是空指针时, 一定要特判空指针, 一定要特判空指针!!! 尤其是取左儿子大小时, 这个格外容易忽视.

更新区间最大字段和

重点来了!!!

这个卡我好几个小时的地方, 就是这里.

\(code:\)

    void Maintain() {
        s = 1, sum = msum = v, lsum = rsum = max(v, 0);
        if (ls != NULL && rs != NULL) {
            s += ls->s + rs->s, sum += ls->sum + rs->sum;
            lsum = max(ls->lsum, ls->sum + v + rs->lsum);
            rsum = max(rs->rsum, rs->sum + v + ls->rsum);
            msum = max(max(ls->msum, rs->msum), ls->rsum + v + rs->lsum);
        }
        else if (ls != NULL) {
            s += ls->s, sum += ls->sum;
            msum = max(ls->msum, ls->rsum + v);
            lsum = max(ls->lsum, ls->sum + v);
            rsum = max(ls->rsum + v, 0);
        }
        else if (rs != NULL) {
            s += rs->s, sum += rs->sum;
            msum = max(rs->msum, rs->lsum + v);
            lsum = max(rs->lsum + v, 0);
            rsum = max(rs->rsum, rs->sum + v);
        }
    }

没错就是这里, 这个题最难搞的莫过于这个区间最大子段和, 而指针由于空指针的存在, 我们经常会忘记更新 \(msum, lsum, rsum\) 这几个值, 所以每次更新的时候记得先赋初值, 这样就不用担心空指针啦~

需要注意的是, 这里是不能选空段的, 所以 \(msum\) 的初值一定要是当前节点的值, 处理的时候也是, 但是 \(lsum\) 和 \(rsum\) 是可以滴, 因为我们在合并的时候会默认加上当前节点的值, 所以即使 \(lsum\) 和 \(rsum\) 都是空的, 那我们的 \(msum\) 也是有一个当前节点的.

区间反转

\(Reserve\) 的时候记得把 \(lsum, rsum\) 也给 \(Swap\) 了, 因为左右儿子换了, 所以左右最大前缀和也得交换.

插入

出于效率, 我们每次插入一个片段的时候, 不要一个一个的插, 这样死慢, 也不要新建一棵树然后一个一个插再 \(Merge\) , 这样虽然 \(O2\) 可以过, 但是常熟极大, 所以这里最建议的写法是这样的.

\(code:\)

Node *Build(int l, int r) {
    Node *o;
    if (l == r) return o = new Node(a[l]);
    int mid = l + r >> 1;
    return Merge(Build(l, mid), Build(mid + 1, r));
}
void Insert(int pos, int k) {
    Node *x, *y, *o;
    for (int i = 1; i <= k; i++) a[i] = read();
    o = Build(1, k);
    Split(Root, pos, x, y);
    Root = Merge(Merge(x, o), y);
}

这样可以有较高的效率.

内存回收

指针党嘛, 既然有它的坏处, 那就一定有他的好处, 我们的内存回收是相当的好写, 这里不建议使用内存池, 尽管常数上可能会优一些, 但是我们内存回收会难搞一些, 我们用 \(new\) 新建节点, 用 \(delete\) 删除节点.

\(code:\)

void Recycle(Node* o) {
    if (o == NULL) return;
    if (o->ls != NULL) Recycle(o->ls);
    if (o->rs != NULL) Recycle(o->rs);
    delete o;
}
void Delete(int pos, int k) {
    Node *x, *y, *z;
    Split(Root, pos - 1, x, y);
    Split(y, k, y, z);
    Recycle(y);
    Root = Merge(x, z);
}

是不是很简洁? 数组还需要开栈, 我们只需要 \(new\) 和 \(delete\) 就行啦!

总结

到这里, 注意事项就差不多了, 写数据结构嘛, 一定要有一颗良好的心态, 你看我笑着写, 欸嘿~ 欸嘿~ (bushi) .

总而言之, 是一道好(毒瘤)题.

\(code:\)

#include <bits/stdc++.h>
using namespace std;
int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
struct Node {
    Node *ls, *rs;
    int v, s, r, rvs, chg, sum, lsum, rsum, msum;
    bool hv;
    Node(int x) {
        v = x, s = 1, r = rand();
        ls = rs = NULL;
        rvs = chg = hv = 0;
        sum = msum = x, lsum = rsum = max(x, 0);
    }
    void Maintain() {
        s = 1, sum = msum = v, lsum = rsum = max(v, 0);
        if (ls != NULL && rs != NULL) {
            s += ls->s + rs->s, sum += ls->sum + rs->sum;
            lsum = max(ls->lsum, ls->sum + v + rs->lsum);
            rsum = max(rs->rsum, rs->sum + v + ls->rsum);
            msum = max(max(ls->msum, rs->msum), ls->rsum + v + rs->lsum);
        }
        else if (ls != NULL) {
            s += ls->s, sum += ls->sum;
            msum = max(ls->msum, ls->rsum + v);
            lsum = max(ls->lsum, ls->sum + v);
            rsum = max(ls->rsum + v, 0);
        }
        else if (rs != NULL) {
            s += rs->s, sum += rs->sum;
            msum = max(rs->msum, rs->lsum + v);
            lsum = max(rs->lsum + v, 0);
            rsum = max(rs->rsum, rs->sum + v);
        }
    }
    void Update(int x) {
        v = chg = x, sum = s * x, hv = 1;
        msum = max(sum, x), lsum = rsum = max(sum, 0);
    }
    void Swap() {
        rvs ^= 1; swap(ls, rs); swap(lsum, rsum);
    }
    void Pushdown() {
        if (rvs) {
            if (ls != NULL) ls->Swap();
            if (rs != NULL) rs->Swap();
            rvs ^= 1;
        }
        if (hv) {
            if (ls != NULL) ls->Update(chg);
            if (rs != NULL) rs->Update(chg);
            hv = 0;
        }
        Maintain();
    }
} *Root;
void Split(Node* o, int k, Node* &l, Node* &r) {
    if (o == NULL) {
        l = r = NULL; return;
    }
    o->Pushdown();
    int ls = o->ls == NULL ? 1 : o->ls->s + 1;
    if (k >= ls) {
        l = o; Split(o->rs, k - ls, o->rs, r);
    }
    else {
        r = o; Split(o->ls, k, l, o->ls);
    }
    o->Maintain();
}
Node *Merge(Node* l, Node* r) {
    if (l == NULL || r == NULL) return l == NULL ? r : l;
    if (l->r < r->r) {
        l->Pushdown();
        l->rs = Merge(l->rs, r);
        l->Maintain(); return l;
    }
    else {
        r->Pushdown();
        r->ls = Merge(l, r->ls);
        r->Maintain(); return r;
    }
}
void Recycle(Node* o) {
    if (o == NULL) return;
    if (o->ls != NULL) Recycle(o->ls);
    if (o->rs != NULL) Recycle(o->rs);
    delete o;
}
int a[500005];
Node *Build(int l, int r) {
    Node *o;
    if (l == r) return o = new Node(a[l]);
    int mid = l + r >> 1;
    return Merge(Build(l, mid), Build(mid + 1, r));
}
void Insert(int pos, int k) {
    Node *x, *y, *o;
    for (int i = 1; i <= k; i++) a[i] = read();
    o = Build(1, k);
    Split(Root, pos, x, y);
    Root = Merge(Merge(x, o), y);
}
void Delete(int pos, int k) {
    Node *x, *y, *z;
    Split(Root, pos - 1, x, y);
    Split(y, k, y, z);
    Recycle(y);
    Root = Merge(x, z);
}
void Change(int pos, int k) {
    Node *x, *y, *z;
    Split(Root, pos - 1, x, y);
    Split(y, k, y, z);
    if (y != NULL) y->Update(read());
    Root = Merge(Merge(x, y), z);
}
void Reverse(int pos, int k) {
    Node *x, *y, *z;
    Split(Root, pos - 1, x, y);
    Split(y, k, y, z);
    if (y != NULL) y->Swap();
    Root = Merge(Merge(x, y), z);
}
void Get_Sum(int pos, int k) {
    Node *x, *y, *z;
    Split(Root, pos - 1, x, y);
    Split(y, k, y, z);
    printf("%d\n", y == NULL ? 0 : y->sum);
    Root = Merge(Merge(x, y), z);
}
void Max_Sum() {
    printf("%d\n", Root->msum);
}
char opt[20];
int main() {
    int n = read(), m = read(), pos, k;
    Insert(1, n);
    while (m--) {
        scanf("%s", opt);
        if(opt[2] != 'X') pos = read(), k = read();
        switch (opt[2]) {
            case 'S': //INSERT
                Insert(pos, k);
                break;
            case 'L': //DELETE
                Delete(pos, k);
                break;
            case 'K': //MAKE-SAME
                Change(pos, k);
                break;
            case 'V': //REVERSE
                Reverse(pos, k);
                break;
            case 'T': //GET-SUM
                Get_Sum(pos, k);
                break;
            case 'X': //MAX-SUM
                Max_Sum();
                break;
        }
    }
    return 0;
}

不懂指针的同志可以学一下, 如果懂指针的同志, 也可以学习一下这种函数式编程, 用构造函数写数据结构真的是一种享受~ 指针 + 构造函数真的太美了!