HDU-1255 覆盖的面积（线段树扫描线+离散化+改进后超快的算法）

2
5
1 1 4 2
1 3 3 7
2 1.5 5 4.5
3.5 1.25 7.5 4
6 3 10 7
3
0 0 1 1
1 0 2 1
2 0 3 1

7.63
0.00

题解：

这题我之前用区间单点暴力的做法1500ms过的，很不甘心，今天上午研究了几个人的写法，后来发现有一种很巧妙的思想，就是我们在扫描线模板的基础上，每一个节点保存的数据为2个，一个为覆盖一次的长度，另一个为覆盖两次以上的长度，那么我们每次更新两个长度，先更新len1，如果完全覆盖就赋全值，如果为一个点就为0，如果都不是就为子区间len1长度和，然后更新len2，如果覆盖两次赋权值，为点就为0，覆盖一次就改成子区间的len1和，其余情况为子区间len2和，然后其他和基本扫描线做法是一样了，还有就是答案依然要加上一个玄学控制精度的eps，这个做法速度可以达到190ms左右速度

附上之前的比较暴力的做法博客：http://blog.csdn.net/qq_37497322/article/details/77255966

代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<stdio.h>
#include<math.h>
#include<string>
#include<stdio.h>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<deque>
using namespace std;
#define lson k*2
#define rson k*2+1
#define M (t[k].l+t[k].r)/2
#define INF 1008611111
#define ll long long
#define eps 1e-15
struct node
{int l,r;double len1;//覆盖一次的长度double len2;//覆盖两次长度int v;//记录覆盖次数
}t[2005*4];
double xx[2005];//离散化后的数组
void Build(int l,int r,int k)
{t[k].l=l;t[k].r=r;t[k].len1=0;t[k].len2=0;t[k].v=0;if(l==r)return;int mid=M;Build(l,mid,lson);Build(mid+1,r,rson);
}
void pushup1(int k)//更新len1
{if(t[k].v>0){t[k].len1=xx[t[k].r+1]-xx[t[k].l];return;}else if(t[k].l==t[k].r){t[k].len1=0;}else{t[k].len1=t[lson].len1+t[rson].len1;}
}
void pushup2(int k)//更新len2
{if(t[k].v>1){t[k].len2=xx[t[k].r+1]-xx[t[k].l];return;}if(t[k].l==t[k].r){t[k].len2=0;}else if(t[k].v==1){t[k].len2=t[lson].len1+t[rson].len1;}else{t[k].len2=t[lson].len2+t[rson].len2;}
}
void update(int l,int r,int k,int d)
{if(l==t[k].l&&t[k].r==r){t[k].v+=d;pushup1(k);pushup2(k);return;}int mid=M;if(r<=mid)update(l,r,lson,d);else if(l>mid)update(l,r,rson,d);else{update(l,mid,lson,d);update(mid+1,r,rson,d);}pushup1(k);pushup2(k);
}
struct edge//存扫描线
{double l,r;double h;int d;//存扫描线性质，1为下底，-1为上底
}a[2005];
int cmp(edge x,edge y)//按高度从小到大排序
{if(x.h!=y.h)return x.h<y.h;return x.d<y.d;
}
int main()
{int i,j,k,n,tot,l,r,test,ans;double x1,x2,y1,y2;scanf("%d",&test);while(test--){scanf("%d",&n);tot=0;for(i=0;i<n;i++){scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);a[tot].l=x1;a[tot].r=x2;a[tot].h=y1;a[tot].d=1;a[tot+1].l=x1;a[tot+1].r=x2;a[tot+1].h=y2;a[tot+1].d=-1;xx[tot]=x1;xx[tot+1]=x2;tot+=2;}sort(xx,xx+tot);sort(a,a+tot,cmp);ans=unique(xx,xx+tot)-xx;//离散化去重Build(0,ans-1,1);double s=0.0;int l=lower_bound(xx,xx+ans,a[0].l)-xx;int r=lower_bound(xx,xx+ans,a[0].r)-xx-1;update(l,r,1,a[0].d);for(i=1;i<tot;i++){s+=(t[1].len2*(a[i].h-a[i-1].h));l=lower_bound(xx,xx+ans,a[i].l)-xx;r=lower_bound(xx,xx+ans,a[i].r)-xx-1;update(l,r,1,a[i].d);}printf("%.2lf\n",s+eps);//玄学}return 0;
}