51nod 1562 玻璃切割

题目链接戳这里

方法是逆序操作。首先设计一个存储结构Line。l、r、val分别代表：左和右相邻的一条线的下标，以及当前线距离左相邻线的距离。

fx,fy的第i个元素为1表示x轴或y轴方向在i位置有切割操作。全部操作完之后，每次去掉一条线，更新左右的Line的数据，得出该操作的结果即可。

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(i,a,b) for(int i=(a);i<(b);++i)

const int maxN=2e5+5;

struct Line { ll l, r, val; };
struct Ope { char ch; ll x; };

Line H[maxN], V[maxN];
Ope s[maxN];
ll fx[maxN], fy[maxN], ans[maxN];

int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif

    ll w, h, n, bx, by, old;
    scanf("%lld%lld%lld\n", &w, &h, &n);
    fx[0] = fx[h] = fy[0] = fy[w] = 1;

    for (int i = 1; i <= n; ++i) {
        scanf("%c%lld\n", &s[i].ch, &s[i].x);
        if (s[i].ch == 'H') fx[s[i].x] = 1;
        else fy[s[i].x] = 1;
    }

    bx = by = 0;
    for (int i = old = 0; i <= h; ++i) {
        if (fx[i] == 1) {
            H[i].l = old;
            H[i].val = i - old;
            H[old].r = i;
            old = i;
            bx = max(bx, H[i].val);
        }
    }
    H[h].r = h;
    for (int i = old = 0; i <= w; ++i) {
        if (fy[i] == 1) {
            V[i].l = old;
            V[i].val = i - old;
            V[old].r = i;
            old = i;
            by = max(by, V[i].val);
        }
    }
    V[w].r = w;
    ans[n] = bx * by;

    for (int i = n; i >= 2; --i) {
        if (s[i].ch == 'H') {
            Line t = H[s[i].x];
            H[t.r].val += t.val;
            H[t.r].l = t.l;
            H[t.l].r = t.r;
            bx = max(bx, H[t.r].val);
        } else {
            Line t = V[s[i].x];
            V[t.r].val += t.val;
            V[t.r].l = t.l;
            V[t.l].r = t.r;
            by = max(by, V[t.r].val);
        }
        ans[i - 1] = bx * by;
    }
    for (int i = 1; i <= n; ++i)
        printf("%lld\n", ans[i]);
    return 0;
}