Leonid wants to become a glass carver (the person who creates beautiful artworks by cutting the glass). He already has a rectangular w mm ?×? h mm sheet of glass, a diamond glass cutter and lots of enthusiasm. What he lacks is understanding of what to carve and how.

In order not to waste time, he decided to practice the technique of carving. To do this, he makes vertical and horizontal cuts through the entire sheet. This process results in making smaller rectangular fragments of glass. Leonid does not move the newly made glass fragments. In particular, a cut divides each fragment of glass that it goes through into smaller fragments.

After each cut Leonid tries to determine what area the largest of the currently available glass fragments has. Since there appear more and more fragments, this question takes him more and more time and distracts him from the fascinating process.

Leonid offers to divide the labor — he will cut glass, and you will calculate the area of the maximum fragment after each cut. Do you agree?

Input

The first line contains three integers w,?h,?n (2?≤?w,?h?≤?200?000, 1?≤?n?≤?200?000).

Next n lines contain the descriptions of the cuts. Each description has the form H?y or V?x. In the first case Leonid makes the horizontal cut at the distance y millimeters (1?≤?y?≤?h?-?1) from the lower edge of the original sheet of glass. In the second case Leonid makes a vertical cut at distance x (1?≤?x?≤?w?-?1) millimeters from the left edge of the original sheet of glass. It is guaranteed that Leonid won't make two identical cuts.

Output

After each cut print on a single line the area of the maximum available glass fragment in mm2.

Examples

Input

Copy

4 3 4
H 2
V 2
V 3
V 1
Output

Copy

8
4
4
2
Input

Copy

7 6 5
H 4
V 3
V 5
H 2
V 1
Output

Copy

28
16
12
6
4
Note

Picture for the first sample test:

?

題意是給定一個矩形，不停地縱向或橫向切割，問每次切割后，最大的矩形面積是多少。 最大矩形面積=最長的長*最寬的寬 這題，長寬都是10^5，所以，用01序列表示每個點是否被切割，然后， 最長的長就是長的最長連續0的數量+1 最長的寬就是寬的最長連續0的數量+1 于是用線段樹維護最長連續零 ? 問題轉換成： 目標信息：區間最長連續零的個數 點信息：0 或 1 由于目標信息不符合區間加法，所以要擴充目標信息。 ? 轉換后的線段樹結構： 區間信息：從左，右開始的最長連續零，本區間是否全零，本區間最長連續零。 點信息：0 或 1 然后還是那2個問題： ? 1.區間加法： 這里，一個區間的最長連續零，需要考慮3部分： -（1）：左子區間最長連續零 -（2）：右子區間最長連續零 -（3）：左右子區間拼起來，而在中間生成的連續零（可能長于兩個子區間的最長連續零） 而中間拼起來的部分長度，其實是左區間從右開始的最長連續零+右區間從左開始的最長連續零。 所以每個節點需要多兩個量，來存從左右開始的最長連續零。 然而，左開始的最長連續零分兩種情況， --（1）：左區間不是全零，那么等于左區間的左最長連續零 --（2）：左區間全零，那么等于左區間0的個數加上右區間的左最長連續零 于是，需要知道左區間是否全零，于是再多加一個變量。 最終，通過維護4個值，達到了維護區間最長連續零的效果。 ? 2.點信息->區間信息 ：? 如果是0，那么 ?最長連續零=左最長連續零=右最長連續零=1 ，全零=true。 如果是1，那么 ?最長連續零=左最長連續零=右最長連續零=0， 全零=false。 ? 至于修改和查詢，有了區間加法之后，機械地寫一下就好了。 由于這里其實只有對整個區間的查詢，所以查詢函數是不用寫的，直接找根的統計信息就行了。

?

遞歸

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm>using namespace std;typedef long long ll; const int maxn = 2 * 1e5 + 10;struct SegTree {ll ls, rs, max0;bool is_all0; }segTree[2][maxn<<2];void pushup(int root, int flag) {SegTree &cur = segTree[flag][root], &lc = segTree[flag][root<<1], &rc = segTree[flag][root<<1|1];cur.ls = lc.ls + (lc.is_all0 ? rc.ls : 0);cur.rs = rc.rs + (rc.is_all0 ? lc.rs : 0);cur.max0 = max(lc.rs + rc.ls, max(lc.max0, rc.max0));cur.is_all0 = lc.is_all0 && rc.is_all0; }void build(int L, int R, int root, int flag) {if (L == R) {segTree[flag][root].ls = segTree[flag][root].rs = segTree[flag][root].max0 = 1;segTree[flag][root].is_all0 = true;return;}int mid = (L + R)>>1;build(L, mid, root<<1, flag);build(mid + 1, R, root<<1|1, flag);pushup(root, flag); }void update_node(int L, int R, int root, int pos, int flag) {if (L == R) {segTree[flag][root].ls = segTree[flag][root].rs = segTree[flag][root].max0 = 0;segTree[flag][root].is_all0 = false;return;}int mid = (L + R)>>1;if (pos <= mid) {update_node(L, mid, root<<1, pos, flag);}else {update_node(mid + 1, R, root<<1|1, pos, flag);}pushup(root, flag); }ll query(int L, int R, int root, int qL, int qR, int flag) {if (qL <= L && R <= qR) {return segTree[flag][root].max0;}int mid = (L + R)>>1;ll temp = 0;if (qL <= mid) {temp = max(temp, query(L, mid, root<<1, qL, qR, flag));}if (qR > mid) {temp = max(temp, query(mid + 1, R, root<<1|1, qL, qR, flag));}return temp; }int main() {int W, H, q, x;char c[5];while (scanf("%d %d %d", &W, &H, &q) == 3) {build(1, W - 1, 1, 0);build(1, H - 1, 1, 1);while (q--) {scanf("%s %d", c, &x);if (c[0] == 'V') {update_node(1, W - 1, 1, x, 0);}else {update_node(1, H - 1, 1, x, 1);}printf("%I64d\n", (query(1, W - 1, 1, 1, W - 1, 0) + 1) * (query(1, H - 1, 1, 1, H - 1, 1) + 1));}} } View Code

非遞歸

#include <iostream> #include <cstdio> #include <cmath> #define maxn 200001 using namespace std; int L[maxn<<2][2];//從左開始連續零個數 int R[maxn<<2][2];//從右 int Max[maxn<<2][2];//區間最大連續零 bool Pure[maxn<<2][2];//是否全零 int M[2]; void PushUp(int rt,int k){//更新rt節點的四個數據 Pure[rt][k]=Pure[rt<<1][k]&&Pure[rt<<1|1][k]; Max[rt][k]=max(R[rt<<1][k]+L[rt<<1|1][k],max(Max[rt<<1][k],Max[rt<<1|1][k]));L[rt][k]=Pure[rt<<1][k]?L[rt<<1][k]+L[rt<<1|1][k]:L[rt<<1][k];R[rt][k]=Pure[rt<<1|1][k]?R[rt<<1|1][k]+R[rt<<1][k]:R[rt<<1|1][k]; } void Build(int n,int k){//建樹，賦初值for(int i=0;i<M[k];++i) L[M[k]+i][k]=R[M[k]+i][k]=Max[M[k]+i][k]=Pure[M[k]+i][k]=i<n;for(int i=M[k]-1;i>0;--i) PushUp(i,k); } void Change(int X,int k){//切割，更新 int s=M[k]+X-1;Pure[s][k]=Max[s][k]=R[s][k]=L[s][k]=0;for(s>>=1;s;s>>=1) PushUp(s,k); } int main(void) {int w,h,n;while(cin>>w>>h>>n){//以下3行，找出非遞歸線段樹的第一個數的位置。 M[0]=M[1]=1;while(M[0]<h-1) M[0]<<=1;while(M[1]<w-1) M[1]<<=1;//建樹 Build(h-1,0);Build(w-1,1);for(int i=0;i<n;++i){//讀取數據 char x;int v;scanf(" %c%d",&x,&v);//切割 x=='H'?Change(v,0):Change(v,1);//輸出 printf("%I64d\n",(long long)(Max[1][0]+1)*(Max[1][1]+1));}} return 0; } View Code

?

其他解法

https://blog.csdn.net/zearot/article/details/44759437

?

轉載于:https://www.cnblogs.com/shuaihui520/p/9835973.html

總結

以上是生活随笔為你收集整理的Codeforces 527C Glass Carving （最长连续0变形+线段树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。