CodeForces

翻译

分析

这题有一点结论题的感觉。

首先你要发现,横着切与竖着切互相是没有影响的。

横着切成了很多段,显然此时面积最大的矩形的一边长就是这些段中长度最长的一段。

竖着切的也是一样的。

所以就可以用set/multiset来维护切过的横、纵坐标与每一段的长度。

修改时,先找到相邻的两刀,再找到对应的长度,删去这个长度,再加入切出来的两个新的长度。

一开始要把$W$、$H$这些东西加进去。

细节见代码。

当然你不用set也行,手写平衡树就行了

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int W,H,n;
set<int> X,Y;
multiset<int> lenx,leny;

mainint main() {
    W=read(),H=read(),n=read();
    lenx.insert(W),leny.insert(H);
    X.insert(0),X.insert(W),Y.insert(0),Y.insert(H);
    multiset<int>::iterator it;
    for (re int i=1;i<=n;++i) {
        char op[2]; scanf("%s",op);
        int k=read();
        if (op[0]=='H') {
            Y.insert(k);
            it=Y.find(k),--it; int L=*it;
            ++it,++it; int R=*it;
            leny.erase(leny.find(R-L));
            leny.insert(k-L),leny.insert(R-k);
        }
        else if (op[0]=='V') {
            X.insert(k);
            it=X.find(k),--it; int L=*it;
            ++it,++it; int R=*it;
            lenx.erase(lenx.find(R-L));
            lenx.insert(k-L),lenx.insert(R-k);
        }
        it=lenx.end(),--it; int maxx=*it;
        it=leny.end(),--it; int maxy=*it;
        printf("%lld\n",maxx*maxy);
    }
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 40 PM