一道蛮有意思的线段树+扫描线，
很值得思考的一道题。
因为题目给的条件很强，
有很多可以根据题目优化的地方。
只是优化的时候可千万不要手滑哦~
尽量按照规范的写法来写，可以防止出错。
题目链接：http://acm.sgu.ru/problem.php?contest=0&problem=319
题意：
在一个W*H的平面上
给定n互不相交但可能相互包含的矩形框架。
这n个框架将平面分成n+1个部分，
分别求这n+1个部分的面积
算法：
把整个平面也算作一个矩形的话，
显然平面上的矩形形成了一系列嵌套关系。
每个矩形都有一个直接父矩形（当然 ，W*H的大矩形除外）
那么我们在一个矩形进入扫描线的时候找到它的父矩形，
并在父矩形代表的区域中减去当前矩形的面积。
然后将这个矩形所在区间覆盖成它的标号，
在这个矩形离开的时候再将该区间的标号恢复成它的父矩形的标号。
对于这道题，
需要细细琢磨的就是以下两个性质：
1、对于同一区间上的矩形来说，它们的Y坐标遵循“先进后出”原则
2、对于每一次查询来说，查询的各个子区间 一定是标号相同的
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;
const int MAXN=61000;
int tr[MAXN<<3],cot[MAXN<<3],p[MAXN];
int x[2][MAXN],y[2][MAXN];
long long s[MAXN];
vector<int>hash;
vector<pair<int,int> >seg;
bool cmp(const pair<int,int>& a, const pair<int,int>& b)
{
return y[a.second][a.first]<y[b.second][b.first];
}
void pushdown(int rt)
{
if(cot[rt]!=-1)
{
cot[rt<<1]=cot[rt<<1|1]=tr[rt<<1]=tr[rt<<1|1]=cot[rt];
cot[rt]=-1;
}
}
void update(int L, int R, int c, int l, int r, int rt)
{
if(L<=l&&r<=R)
{
tr[rt]=cot[rt]=c;
return;
}
pushdown(rt);
int mid=(l+r)>>1;
if(L<=mid)
{
update(L,R,c,l,mid,rt<<1);
}
if(R>mid)
{
update(L,R,c,mid+1,r,rt<<1|1);
}
}
int query(int L, int R, int l, int r, int rt)
{
if(L<=l&&r<=R)
{
return tr[rt];
}
pushdown(rt);
int mid=(l+r)>>1;
if(L<=mid)
{
return query(L,R,l,mid,rt<<1);
}
return query(L,R,mid+1,r,rt<<1|1);
}
int main()
{
int n,w,h;
scanf("%d%d%d",&n,&w,&h);
memset(cot,-1,sizeof(cot));
memset(tr,0,sizeof(tr));
seg.clear();
hash.clear();
s[0]=(long long)w*h;
for(int i=1; i<=n; i++)
{
scanf("%d%d%d%d",&x[0][i],&y[0][i],&x[1][i],&y[1][i]);
if(x[1][i]<x[0][i])
{
swap(x[1][i],x[0][i]);
}
if(y[1][i]<y[0][i])
{
swap(y[1][i],y[0][i]);
}
s[i]=(long long)(x[1][i]-x[0][i])*(y[1][i]-y[0][i]);
seg.push_back(make_pair(i,0));
seg.push_back(make_pair(i,1));
hash.push_back(x[0][i]);
hash.push_back(x[1][i]);
}
sort(seg.begin(),seg.end(),cmp);
sort(hash.begin(),hash.end());
hash.erase(unique(hash.begin(),hash.end()),hash.end());
int m=hash.size();
for(int i=0; i<2*n; i++)
{
int j=seg[i].first;
int L=lower_bound(hash.begin(),hash.end(),x[0][j])-hash.begin();
int R=lower_bound(hash.begin(),hash.end(),x[1][j])-hash.begin()-1;
if(L>R)
{
continue;
}
if(seg[i].second==0)
{
p[j]=query(L,R,0,m-1,1);
s[p[j]]-=(long long)(x[1][j]-x[0][j])*(y[1][j]-y[0][j]);
update(L,R,j,0,m-1,1);
}
else
{
update(L,R,p[j],0,m-1,1);
}
}
sort(s,s+n+1);
for(int i=0; i<=n; i++)
{
printf("%lld",s[i]);
i==n?puts(""):putchar(' ');
}
return 0;
}
一些细节上还有一些其它写法。
例如可以用节点保存点而非线段。
然后网上的一些代码一般都是直接用cot数组代替tr数组。
其实我认为我这样分两个数组可能更稳妥一些。