CodeForces-527C Glass Carving
题面
有一个w*h的矩形,每次要么横着切一刀,要么竖着切一刀,每次你都要回答切完后最大的子矩形的面积
输入三个整数w h n表示矩形的宽度和高度,以及操作的数量
接下来n行每行一个操作
要么是
H y (表示横着在y位置切一刀)
要么是
V x(表示竖着在x位置切一刀)
2 <= w, h <= 200000, 1 <= n <= 200000
总结
这道题以前做过：传送门
一：set和multset
二：将切割玻璃改成合并玻璃，从最后往前求
最大值永远在变大
每次删去一个切割你会获得一个比较长的玻璃
AC代码
#include<bits/stdc++.h>
#define MAXN 300000
using namespace std;
char caozuo[MAXN];
long long ans[MAXN];
set<int> hset,vset;
int x[MAXN],hi[MAXN],vi[MAXN],w,h,n,d,ht,vt,hmx=-1,vmx=-1;
int main(){
scanf("%d%d%d",&w,&h,&n);
hi[++ht]=0;vi[++vt]=0;
for(int i=1;i<=n;i++){
cin>>caozuo[i]>>x[i];
if(caozuo[i]=='H'){
hi[++ht]=x[i];
}else{
vi[++vt]=x[i];
}
}
hi[++ht]=h;vi[++vt]=w;
sort(hi+1,hi+1+ht);sort(vi+1,vi+1+vt);
for(int i=1;i<ht;i++){
hmx = max(hmx,hi[i+1]-hi[i]);
hset.insert(hi[i]);
}hset.insert(hi[ht]);
for(int i=1;i<vt;i++){
vmx = max(vmx,vi[i+1]-vi[i]);
vset.insert(vi[i]);
}vset.insert(vi[vt]);
set<int>::iterator l,r,c;
for(int i=n;i>=1;i--){
ans[i] = (long long)(hmx) * vmx;
if(caozuo[i]=='H'){
l = r = c = hset.lower_bound(x[i]);
l--;r++;
hmx = max(hmx,*r-*l);
hset.erase(x[i]);
}else{
l = r = c = vset.lower_bound(x[i]);
l--;r++;
vmx = max(vmx,*r-*l);
vset.erase(x[i]);
}
}
for(int i=1;i<=n;i++){
printf("%lld\n",ans[i]);
}
return 0;
}