题目链接：http://poj.org/problem?id=1151
实际上不下放lazytag就是一个保持另一层记录的过程。简单的来说，就是当cnt为0的时候，t[rt<<1].len+t[rt<<1|1].len才是真实信息，当cnt不为0的时候，这段的段长才是真实信息，t[rt<<1].len+t[rt<<1|1].len是把这个矩形去掉之后该段的覆盖情况。
题目描述和解释什么的，我就不说了，我是看了lyd的《算法竞赛进阶指南》之后思考了lyd的lazytag不需要下放的说法，其实这是一个很简单的问题，我们只设定lazytag，但是并不下放，因为左右线段是同样的几段构成的，如果执行了对[x,y]段+=k的操作之后一个段的cnt不为0，说明他至少被一个矩形所覆盖，这个覆盖，指的是那个矩形的右边界还没有达到。可以想象这样的矩形一定存在，否则这段的cnt将会变成0。
下面，当一个段在执行操作之后cnt变成了0，说明所有覆盖这个区间段的矩形的右边界都已经完了，刚刚执行的一定是对这个区间段的cnt-1的行为，因为cnt只可能是从1变成0，故刚刚扫描的边一定会一个矩形的右边界，对于这一段而言，这个矩形的右边界截断之后，这个[x_i-1,x_i]段的扫描线被覆盖长度是多少呢？答案就是在不放这个矩形的情况下，最后一次操作中这一段的两个子区间被覆盖的长度之和，之所以没有下放这个标记，就是为了造成这样一种局面：在这个段下面的两个子段，其实是没有放这最后一个矩形的局面，正好就把它所掩盖的小段的段长和记录了。这就是lyd的方法的来源说明。
我们试想，这一段的宽度很大，在截断之后，会露出更短的段长，没有下放标记，就使得这些更短的段长的和都在两个字段中被记录了。通过对两个字段的段长和进行求和，就得到了这段的当前段长。
代码：
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int maxn = 10010; struct node{ int l,r,cnt; double len;//维护被覆盖的次数以及覆盖的长度 }t[maxn<<3]; int n; int T=0; struct P {//记录一条边 double x,y1,y2; int k;//记录左边还是右边 bool operator < (const P& o)const {//按照x进行排序 return x<o.x; } }a[maxn<<1]; double raw[maxn<<1]; int num; int get(double x){ return lower_bound(raw+1,raw+num+1,x)-raw; } void build(int rt,int l,int r){ t[rt].l=l; t[rt].r=r; t[rt].cnt=0; t[rt].len=0; if(l==r)return ; int mid=l+r>>1; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); } void update(int rt,int L,int R,int C){ if(t[rt].l>=L && t[rt].r<=R){ t[rt].cnt+=C; if(t[rt].cnt==0){//该段没有被完全覆盖 if(t[rt].l==t[rt].r)t[rt].len=0;//叶结点 else t[rt].len=t[rt<<1].len+t[rt<<1|1].len; }else{ t[rt].len=raw[t[rt].r+1]-raw[t[rt].l]; } return ; } int mid=(t[rt].l+t[rt].r)>>1; if(L<=mid)update(rt<<1,L,R,C); if(R>mid)update(rt<<1|1,L,R,C); // 不可能是叶子结点，所以只有两种更新方式 if(t[rt].cnt)t[rt].len=raw[t[rt].r+1]-raw[t[rt].l]; else t[rt].len=t[rt<<1].len+t[rt<<1|1].len; } void solve(){ cout<<"Test case #"<<++T<<endl; for(int i=1;i<=n;i++){ double x1,x2,y1,y2; scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); raw[2*i-1]=y1; raw[2*i]=y2; a[2*i-1].x=x1,a[2*i-1].y1=y1,a[2*i-1].y2=y2,a[2*i-1].k=1; a[2*i].x=x2,a[2*i].y1=y1,a[2*i].y2=y2,a[2*i].k=-1; } sort(raw+1,raw+2*n+1); num=unique(raw+1,raw+2*n+1)-(raw+1); build(1,1,num-1);//最多有num-1段 sort(a+1,a+2*n+1);//从x最小的开始扫描 double ans=0; for(int i=1;i<2*n;i++){ int l=get(a[i].y1),r=get(a[i].y2)-1; update(1,l,r,a[i].k); ans+=t[1].len*(a[i+1].x-a[i].x); } printf("Total explored area: %.2f ",ans); } int main(){ while(cin>>n && n)solve(); return 0; }