CodeForces - 527C Glass Carving——線段樹

題意：給定一個矩形，每次可以橫向切割或縱向切割，求每次切割完後所有矩形的最大面積

思路：最大矩形的面積 = 最大的w * 最大的h，是以可以鍵兩棵線段樹，一棵維護最大的w，一棵維護最大的h，以維護最大的w為例：

我們可以把W - 1個劃分點作為線段樹的葉子，每個點如果被劃分就設為1， 沒有劃分設為0，那麼最長的w就是線段樹統計出的最長的連續0的個數+1.

因為最長連續0不符合區間加法，是以要對線段樹維護的區間資訊進行擴充，即維護這個區間【從左邊開始的連續0的數量】，【從右邊開始的連續0的數量】，【是否全部為0】，【最大連續0四個量】。

為什麼要這麼擴充？，下面來看一下一個區間的最大連續0是如何通過兩個子區間求出：

相信大家都接觸過分治法求最大連續和，原理是一樣的，一個區間的【最大連續0】 = max（左區間的最大連續0， 右區間的最大連續0，跨越中間的最大連續0）

左右區間的最大連續0遞歸就可以

跨越中間的最大連續0 = 左區間【從右邊開始的連續0】 + 右區間【從左開始的連續0】，為了求跨越中間的最大連續0我們的線段樹要維護這兩個量

那麼【是否全為0】這個資訊是幹什麼的呢？他是用來更新【從左邊開始的連續0】以及【從右邊開始的連續0】的

一個區間【從左邊開始的連續0】 = 左區間【從左邊開始的連續0】 + （左區間是否全為0） ？ 右區間【從左邊開始的連續0】 ： 0

一個區間【從右邊開始的連續0】 = 右區間【從右邊開始的連續0】 + （右區間是否全為0） ？ 左區間【從右邊開始的連續0】 ： 0

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
const int maxn = 2 * 1e5 + 10;

struct SegTree {
    ll ls, rs, max0;
    bool is_all0;
}segTree[2][maxn<<2];

void pushup(int root, int flag) {
    SegTree &cur = segTree[flag][root], &lc = segTree[flag][root<<1], &rc = segTree[flag][root<<1|1];
    cur.ls = lc.ls + (lc.is_all0 ? rc.ls : 0);
    cur.rs = rc.rs + (rc.is_all0 ? lc.rs : 0);
    cur.max0 = max(lc.rs + rc.ls, max(lc.max0, rc.max0));
    cur.is_all0 = lc.is_all0 && rc.is_all0;
}

void build(int L, int R, int root, int flag) {
    if (L == R) {
        segTree[flag][root].ls = segTree[flag][root].rs = segTree[flag][root].max0 = 1;
        segTree[flag][root].is_all0 = true;
        return;
    }
    int mid = (L + R)>>1;
    build(L, mid, root<<1, flag);
    build(mid + 1, R, root<<1|1, flag);
    pushup(root, flag);
}

void update_node(int L, int R, int root, int pos, int flag) {
    if (L == R) {
        segTree[flag][root].ls = segTree[flag][root].rs = segTree[flag][root].max0 = 0;
        segTree[flag][root].is_all0 = false;
        return;
    }
    int mid = (L + R)>>1;
    if (pos <= mid) {
        update_node(L, mid, root<<1, pos, flag);
    }
    else {
        update_node(mid + 1, R, root<<1|1, pos, flag);
    }
    pushup(root, flag);
}

ll query(int L, int R, int root, int qL, int qR, int flag) {
    if (qL <= L && R <= qR) {
        return segTree[flag][root].max0;
    }
    int mid = (L + R)>>1;
    ll temp = 0;
    if (qL <= mid) {
        temp = max(temp, query(L, mid, root<<1, qL, qR, flag));
    }
    if (qR > mid) {
        temp = max(temp, query(mid + 1, R, root<<1|1, qL, qR, flag));
    }
    return temp;
}

int main()
{
    int W, H, q, x;
    char c[5];
    while (scanf("%d %d %d", &W, &H, &q) == 3) {
        build(1, W - 1, 1, 0);
        build(1, H - 1, 1, 1);
        while (q--) {
            scanf("%s %d", c, &x);
            if (c[0] == 'V') {
                update_node(1, W - 1, 1, x, 0);
            }
            else {
                update_node(1, H - 1, 1, x, 1);
            }
            printf("%I64d\n", (query(1, W - 1, 1, 1, W - 1, 0) + 1) * (query(1, H - 1, 1, 1, H - 1, 1) + 1));
        }
    }
}