题解 P6492 【[COCI2010-2011#6] STEP】

· · 题解

看这道题，区间询问，答案具有可并性，于是考虑用线段树维护。

此题很像那种求区间最大子段，考虑维护一个线段树的节点。

每个节点维护如下信息：

考虑合并左右两个子节点并计算贡献。

lmax和rmax只需要考虑中间是否能拼接起来更新， allmax则是各段allmax取最值，再考虑中间是否能拼接起来更新。

其余的值直接调用左右节点的值来贡献即可。

inline Node operator + (const Node&rhs) const {
    return Node(
        allmax == len && rsum != rhs.lsum ? len + rhs.lmax : lmax,
        rhs.allmax == rhs.len && rsum != rhs.lsum ? rmax + rhs.len : rhs.rmax,
        max(rsum != rhs.lsum ? rmax + rhs.lmax : 0, allmax, rhs.allmax),
        lsum,
        rhs.rsum,
        len + rhs.len
    );
}

然后线段树就是常规操作。

struct SegmentTree {
    struct Node {
        int lmax, rmax, allmax, lsum, rsum, len;
        Node() { lsum = rsum = 0; len = lmax = rmax = allmax = 1; }
        Node(int _lmax, int _rmax, int _allmax, int _lsum, int _rsum, int _len)
        : lmax(_lmax), rmax(_rmax), allmax(_allmax), lsum(_lsum), rsum(_rsum), len(_len) {}
        inline void Vary(void) { rsum ^= 1; lsum ^= 1; }
        inline Node operator + (const Node&rhs) const {
            return Node(
                allmax == len && rsum != rhs.lsum ? len + rhs.lmax : lmax,
                rhs.allmax == rhs.len && rsum != rhs.lsum ? rmax + rhs.len : rhs.rmax,
                max(rsum != rhs.lsum ? rmax + rhs.lmax : 0, allmax, rhs.allmax),
                lsum,
                rhs.rsum,
                len + rhs.len
            );
        }
    } t[Maxn];

    inline void pushup(int pos) { t[pos] = t[pos << 1] + t[pos << 1 | 1]; }
    inline void build(int pos, int l, int r) {
        if (l == r) return;
        int mid = l + r >> 1;
        build(pos << 1, l, mid);
        build(pos << 1 | 1, mid + 1, r);
        pushup(pos);
    }

    inline void change(int pos, int l, int r, int idx) {
//      cout << l << ' ' << r << endl;
//      if (l > idx || r < idx) return;
        if (l == r) { t[pos].Vary(); return; }
        int mid = l + r >> 1;
        if (idx <= mid) change(pos << 1, l, mid, idx);
        else change(pos << 1 | 1, mid + 1, r, idx);
        pushup(pos);
    }

    inline Node query1(int pos, int l, int r, int L, int R) {
        if (L <= l && R >= r) return t[pos];
        int mid = l + r >> 1; // Node ret;
        if (L <= mid && R > mid) return query1(pos << 1, l, mid, L, R) + query1(pos << 1 | 1, mid + 1, r, L, R);
        if (L <= mid) return query1(pos << 1, l, mid, L, R);
        if (R > mid) return query1(pos << 1 | 1, mid + 1, r, L, R);
    }

    inline int query(void) { return t[1].allmax; }
} T;