51nod 1562 玻璃切割 （set+离线处理）

传送门：51nod 1562

思路：

最核心的思路是离线处理，也就是不用每次切割都立即输出结果，而是先把所有结果处理完再统一输出。用讨论区的话说就是把武功倒着打。

我们注意到，当前面积最大的玻璃一定是横向最大长度乘以纵向最大长度，所以我们只需要维护横向和纵向的最大长度就可以了。如果是每次切割都要计算面积的话，我们不禁要求出新产生的两块玻璃的长度，还要删除切割前的长度。这样就导致时间消耗比较大。

如果离线处理的话，相当于我们已经把玻璃全部切割完，现在需要从后往前依次去掉一根切割线，然后计算面积。这样玻璃的长度一定会增大，所以只需要维护玻璃横向和纵向的最大值即可。

具体做法就是把横向和纵向的切割线分别放入两个集合，求出最大的横向距离和纵向距离。从后往前依次去掉一个切割线（在集合中删除），然后查找该切割线左右两边的切割线并更新该方向上长度的最大值。

代码：

#include<stdio.h>
#include<iostream>
#include<set>
using namespace std;
typedef long long LL;

LL ans[200010]; //存放结果 

int main()
{		
	int i,w,h,n,maxr,maxc,x[200010];
	char c[200010]; //在哪个方向切割 
	set<int> row,col; //行和列上的切割线 
	set<int>:: iterator it;
	while(~scanf("%d%d%d",&w,&h,&n))
	{
		maxr=maxc=0;
		row.clear(); //清空集合 
		col.clear();
		row.insert(0); //插入开始时的两端 
		row.insert(h);
		col.insert(0);
		col.insert(w);
		for(i=0;i<n;i++)
		{ //读入操作并将切割线插入到相应集合 
			scanf("%*c%c%d",&c[i],&x[i]);
			if(c[i]=='H') row.insert(x[i]);
			else col.insert(x[i]);
		}
		int l,r;				
		for(it=row.begin();it!=row.end();)
		{ //求纵向上长度的最大值 
			l=*it;
			it++;
			r=*it;
			if(r-l>maxr) maxr=r-l;
		}
		for(it=col.begin();it!=col.end();)
		{ //求横向上长度的最大值 
			l=*it;
			it++;
			r=*it;					
			if(r-l>maxc) maxc=r-l;
		}
		for(i=n-1;i>=0;i--)
		{ //从后往前处理 
			ans[i]=(LL)maxr*maxc; //先计算结果 
			if(c[i]=='H')
			{ //如果是横向切割 
				it=row.lower_bound(x[i]); //二分查找当前切割线的位置 
				it--;
				l=*it;
				it++;
				it++;
				r=*it;
				if(r-l>maxr) maxr=r-l; //维护最大值 
				row.erase(x[i]); //删除该切割线 
			}
			else
			{ //如果是纵向切割
				it=col.lower_bound(x[i]); //二分查找当前切割线的位置 
				it--;
				l=*it;
				it++;
				it++;
				r=*it;
				if(r-l>maxc) maxc=r-l; //维护最大值 
				col.erase(x[i]); //删除该切割线 
			}
		}
		for(i=0;i<n;i++) printf("%lld\n",ans[i]);			
	}
	return 0;
}