题解 CF527C 【Glass Carving】

题意

有一个w*h的矩形,每次要么横着切一刀,要么竖着切一刀,每次你都要回答切完后最大的子矩形的面积。

要么是横着在y位置切一刀,要么是竖着在x位置切一刀.

题解

原来想着用暴力写，但是数据范围比较大：2 <= w, h <= 200000, 1 <= n <= 200000。然后就想到了STL。

用两个multiset和两个set分别储存切的痕迹与原来的，面积就是最大的长和宽相乘。

代码

#include<bits/stdc++.h>
#define its set<int>::iterator
#define is mulitset<int>::iterator

using namespace std;
int w,h,n;
multiset<int> sx;
multiset<int> sy;
set<int> x;
set<int> y;
int main(){

    scanf("%d%d%d",&w,&h,&n);
    x.insert(0);
    x.insert(h);
    y.insert(w);
    y.insert(0);
    sx.insert(h);
    sy.insert(w);
    for(int i=1;i<=n;++i)
    {
        char c;
        int p;
        cin>>c;
        scanf("%d",&p);

        if(c=='V')
        {
            y.insert(p);
            its it,itt;
            it=y.lower_bound(p);
            itt=y.upper_bound(p);
            --it;

            int ls,rs;
            ls=p-*it;
            rs=*itt-p;
            int ss=*itt-*it;
            //cout<<*itt<<" "<<*it<<" "<<ss<<endl;
            sy.erase(sy.find(ss));
            sy.insert(ls);
            sy.insert(rs);
        }
        else
        {
            x.insert(p);
            its it,itt;
            it=x.lower_bound(p);
            itt=x.upper_bound(p);
            --it;

            int ls,rs;
            ls=p-*it;
            rs=*itt-p;
            int ss=*itt-*it;
            //cout<<*itt<<" "<<*it<<" "<<ss<<endl;
            sx.erase(sx.find(ss));
            sx.insert(rs);
            sx.insert(ls);

        }
        int a,b;
        a=*(--sx.end());
        b=*(--sy.end());
        printf("%lld\n",(1LL)*a*b);
    }

    return 0;
}