1562 玻璃切割

题目来源： CodeForces

基准时间限制：1.5 秒空间限制：131072 KB 分值: 20 难度：3级算法题

关注

现在有一块玻璃，是长方形的（w 毫米× h 毫米），现在要对他进行切割。

切割的方向有两种，横向和纵向。每一次切割之后就会有若干块玻璃被分成两块更小的玻璃。在切割之后玻璃不会被移动。

现在想知道每次切割之后面积最大的一块玻璃是多少。

样例解释：

对于第四次切割，下面四块玻璃的面积是一样大的。都是2。

Input

单组测试数据。
第一行有三个整数 w,h,n (2≤w,h≤200000, 1≤n≤200000)，表示玻璃在横向上长w 毫米，纵向上长h 毫米，接下来有n次的切割。
接下来有n行输入，每一行描述一次切割。
输入的格式是H y 或 V x。
H y表示横向切割，切割线距离下边缘y毫米(1≤y≤h-1)。
V x表示纵向切割，切割线距离左边缘x毫米(1≤x≤w-1)。
输入保证不会有两次切割是一样的。

Output

对于每一次切割，输出所有玻璃中面积最大的是多少。

Input示例

样例输入1
4 3 4
H 2
V 2
V 3
V 1

Output示例

样例输出1
8
4
4
2

题目题意稍微想一下肯定知道,要面积最大,两边都应该最大,但是每次切割又有不确定性,
其实可以用个set来维护,但是时间就是个比较大的问题了,这种题应该也可以用线段树
的找最大区间来做,但是有一种更好的方法就是,逆向思维,先把所有的边都放进去,然后
从后面删除之前放的边.(我也是瞄了一下大神的思路才想到的).

 1 #include <bits/stdc++.h>
 2 #define ll long long int
 3 #define N 200005
 4 #define bug cout<<"***"<<endl
 5 using namespace std;
 6 struct Node{
 7   ll l,r,val;
 8 };
 9 struct Line{
10   char ch;
11   ll x;
12 };
13 Node H[N],L[N];
14 Line s[N];
15 ll fx[N],fy[N],ans[N];
16 int main(){
17   ll w,h,n,bx,by,now;
18   scanf("%lld%lld%lld",&w,&h,&n);
19   fx[0]=fx[h]=fy[0]=fy[w]=1;
20   for(int i=1;i<=n;i++){//将边存起来,并记录.
21     scanf(" %c%lld",&s[i].ch,&s[i].x);//注意这里的输入,开始我的%前面没有空格就错了,加一个就过了.
22     if(s[i].ch=='H')
23       fx[s[i].x]=1;
24     else
25       fy[s[i].x]=1;
26     //bug;
27   }
28   bx=by=0;
29   for(int i=now=0;i<=h;i++){//找到所有边都插进去之后的最大x
30     if(fx[i]==1)
31       H[i].l=now,H[i].val=i-now,H[now].r=i,now=i,bx=max(bx,H[i].val);
32   }
33   H[h].r=h;
34   for(int i=now=0;i<=w;i++){//找到最大y
35     if(fy[i]==1)
36       L[i].l=now,L[i].val=i-now,L[now].r=i,now=i,by=max(by,L[i].val);
37   }
38   L[w].r=w;
39   ans[n]=bx*by;
40   for(int i=n;i>=2;i--){//逐项删除插进来的边
41     if(s[i].ch=='H'){
42       H[H[s[i].x].r].val=H[s[i].x].val+H[H[s[i].x].r].val;//好好体会
43       H[H[s[i].x].l].r=H[s[i].x].r;
44       H[H[s[i].x].r].l=H[s[i].x].l;
45       bx=max(bx,H[H[s[i].x].r].val);
46     }else{
47       L[L[s[i].x].r].val=L[s[i].x].val+L[L[s[i].x].r].val;
48       L[L[s[i].x].l].r=L[s[i].x].r;
49       L[L[s[i].x].r].l=L[s[i].x].l;
50       by=max(by,L[L[s[i].x].r].val);
51     }
52     ans[i-1]=bx*by;
53   }
54   for(int i=1;i<=n;i++){
55     printf("%lld
",ans[i]);
56   }
57   return 0;
58 }