题意：给一堆长宽平行于坐标轴的长方形求并的面积
我个沙茶快写了一晚上…
大概思想就是先根据$y$坐标排个序，把$y$坐标离散化一下，放到线段树里面维护，这里的写法是让线段树的节点储存这个点对应的整段线段的信息，更新的时候如果不行就把线段拆开，以及注意一些细节（比如这里右孩子的区间是[mid,r]而不是[mid+1,r]因为下标其实应该是连续的实数）
我也讲不清楚了具体看代码…
#include<cstdio> #include<algorithm> #define rep(i,n) for(register int i=1;i<=n;i++) #define REP(i,a,b) for(register int i=a;i<=b;i++) #define debug(x) printf("%s = %d ",#x,x) using namespace std; typedef double dl; const int N=105; struct tree { dl l,r,s;int c; }tr[N<<3]; struct Line { dl x,y1,y2;int f; Line(dl x=0,dl y1=0,dl y2=0,int f=0):x(x),y1(y1),y2(y2),f(f){} }ls[N<<1]; int T,n,cnt,tot; dl y[N<<1],ans,x1,x2,y1,y2; inline bool operator <(Line a,Line b) { return a.x<b.x; } #define lson (o<<1) #define rson (o<<1|1) inline void push_up(int o,int l,int r) { if(tr[o].c>0) tr[o].s=tr[o].r-tr[o].l; else if(l+1==r) tr[o].s=0; else tr[o].s=tr[lson].s+tr[rson].s; } inline void build(int o,int l,int r) { tr[o].l=y[l];tr[o].r=y[r]; if(l+1==r)return; int mid=(l+r)>>1; build(lson,l,mid);build(rson,mid,r); } inline void modify(int o,int l,int r,Line e) { if(tr[o].l==e.y1&&tr[o].r==e.y2) { tr[o].c+=e.f; push_up(o,l,r);return; }int mid=(l+r)>>1; if(e.y2<=tr[lson].r)modify(lson,l,mid,e); else if(e.y1>=tr[rson].l)modify(rson,mid,r,e); else { modify(lson,l,mid,Line(e.x,e.y1,tr[lson].r,e.f)); modify(rson,mid,r,Line(e.x,tr[rson].l,e.y2,e.f)); } push_up(o,l,r); } int main() { while(scanf("%d",&n)&&n) { rep(i,n) { scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); y[++cnt]=y1;y[++cnt]=y2; ls[++tot]=Line(x1,y1,y2,1);ls[++tot]=Line(x2,y1,y2,-1); } sort(y+1,y+cnt+1);sort(ls+1,ls+tot+1); build(1,1,cnt);modify(1,1,cnt,ls[1]); REP(i,2,tot) { ans+=(ls[i].x-ls[i-1].x)*tr[1].s; modify(1,1,cnt,ls[i]); } printf("Test case #%d ",++T); printf("Total explored area: %.2lf ",ans); ans=tot=cnt=0; } return 0; }