1.题目描述：点击打开链接
2.解题思路：本题要求每切一刀，输出目前的最大玻璃的面积。这道题的思路很明显：每次切完后找目前的最大长度，最大宽度，相乘即可。不过问题的关键是如何快速的找到这个最大值。
一开始我没有太好的思路，想用数组，但总感觉数组力不从心，不知道怎么才能很好地更新切完后的长度值，也不知道如何快速的找到这个最大值。接着想到了STL中的set，可以把所有的切割位置存放在set中，然后逐个找最大值。不过这样的结果就是效率过低，导致TLE了。看了别人的代码才恍然大悟：可以直接除掉被切割的线段，同时添加上切割后的线段。
但问题又来了，，如何存放这些线段？答案是利用标记数组。如果线段值存在，标记为1，否则标记为0，这样就能很方便地更新线段值了。同时查找最长的线段也很方便，由于每次切割后，最大长度是不会增加的，因此只需要从切割前的最大长度开始，逐一减小，看是否存在即可。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;typedef long long LL;#define N 200000+10set<int>wd, hd;//记录切割的位置int w, h, n;set<int>::iterator i, j;int wi[N], hi[N];//分别标记目前存在的边长值void cut(set<int>&s, int*a, int p){s.insert(p), i = j = s.find(p);–i, ++j, –a[*j – *i];//除掉被分开的长/宽++ a[p – *i], ++a[*j – p];//新产生了两个长/宽}int main(){//freopen("t.txt", "r", stdin);while (cin >> w >> h >> n){int p, maxw, maxh;char c;memset(wi, 0, sizeof(wi));memset(hi, 0, sizeof(hi));wd.clear(), hd.clear();wd.insert(0), wd.insert(w);hd.insert(0), hd.insert(h);wi[w] = hi[h] = 1;maxw = w, maxh = h;while (n–){cin >> c >> p;if (c == 'V')cut(wd, wi, p);else cut(hd, hi, p);while (!wi[maxw])–maxw;//找切割后的最大值while (!hi[maxh])–maxh;cout << (LL)maxh*maxw << endl;}}return 0;}
走过一个又一个陌生的城市，去感受旖旎的自然风光，
