今天刚看到这个模板我是懵逼的，这个线段树既没有建树，也没有查询，只有一个update，而且区间成段更新也没有lazy标记....研究了一下午，我突然我发现我以前根本不懂扫描线，之所以没有lazy标记，是因为扫描线每次只查询1-n里的所有有值的区间长度，因为只要1-n,而不会查找到某些小区间，所以也就不用lazy，而且也无需查询，每次插入完只需要 知道sum[1]是多少即可。所以一个update函数即可。注意的是，线段树的叶子节点不是x轴或者y轴上的点，而是一个个区间，由矩形的长或者宽间距所构成的区间。比如 你现在要更新的这条边的两个端点在x轴上是 x=1，和x=6，更新的l=1，r=5，因为1->6 中间有5个区间 偷别人博客的一张图来看一下就是这样的效果：
所以线段树维护的是 这些小区间
然后剩下的细节就很好懂了
#include<cstdio>
#include<string.h>
#include<algorithm>
#define inf 0x3f3f3f3f
const int maxn=;
using namespace std;
#define lson (id<<1)
#define rson ((id<<1)|1)
#define mid ((l+r)>>1)
double a[maxn+];
double sum[maxn+];
int flag[maxn+];
int n,l,r,k,cnt,icase;
double ans;
double X1,Y1,X2,Y2;
struct node{
double lx,rx,y;
int f;
node(){};
node(double lx_,double rx_,double y_,int f_){
lx=lx_,rx=rx_,y=y_,f=f_;
}
}line[maxn+];
int cmp(node a,node b){
return a.y<b.y;
}
int bin_search(double val){
int lb=,ub=k;
int Mid=(lb+ub)>>;
while(ub-lb>){
Mid=(ub+lb)>>;
if(a[Mid]==val) return Mid;
else if(a[Mid]>val) ub=Mid;
else if(a[Mid]<val) lb=Mid;
}
if(a[Mid]==val) return Mid;
if(a[ub]==val) return ub;
if(a[lb]==val) return lb;
}
void push_up(int id,int l,int r){
if(flag[id]) sum[id]=a[r+]-a[l];
else if(l==r) sum[id]=;
else sum[id]=sum[lson]+sum[rson];
}
void update(int id,int l,int r,int ql,int qr,int val){
if(ql<=l&&r<=qr){
flag[id]+=val;
push_up(id,l,r);
return ;
}
if(ql<=mid){
update(lson,l,mid,ql,qr,val);
}
if(qr>=mid+){
update(rson,mid+,r,ql,qr,val);
}
if(qr<=mid){
update(lson,l,mid,ql,qr,val);
} else if(ql>=mid+){
update(rson,mid+,r,ql,qr,val);
} else {
update(lson,l,mid,ql,mid,val);
update(rson,mid+,r,mid+,qr,val);
}
push_up(id,l,r);
}
void init(){
k=;
cnt=;
ans=;
memset(flag,,sizeof(flag));
memset(sum,,sizeof(sum));
}
void solve(){
for(int i=;i<=n;i++){
scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2);
line[++cnt]=node(X1,X2,Y1,);
a[cnt]=X1;
line[++cnt]=node(X1,X2,Y2,-);
a[cnt]=X2;
}
sort(a+,a++cnt);
sort(line+,line++cnt,cmp);
k=;
for(int i=;i<=cnt;i++){
if(a[i]!=a[i+]){
a[++k]=a[i];
}
}
for(int i=;i<cnt;i++){
l=bin_search(line[i].lx);
r=bin_search(line[i].rx)-;
update(,,k,l,r,line[i].f);
ans+=sum[]*(line[i+].y-line[i].y);
}
printf("Test case #%d\n",++icase);
printf("Total explored area: %.2f\n\n",ans);
}
int main()
{
while(scanf("%d",&n)!=EOF&&n){
init();
solve();
}
return ;
}