题目大意：求矩形相交部分面积和
#include<iostream> #include<algorithm> using namespace std; #define N 2001 struct node { int l,r,cover; double one_len,more_len; int getmid(){ return (l+r)>>1; } }p[3*N]; struct Line { double l,r,h; int flag; }L[N]; int m; double X[N]; double h[N]; bool cmp(Line x,Line y) { return x.h<y.h; } int find(double x) { int f=0,l=m-1; while(f<=l) { int mid=(f+l)>>1; if(h[mid]==x) return mid; if(h[mid]>x) l=mid-1; else f=mid+1; } } void setlen(int id) { int l=p[id].l,r=p[id].r; if(p[id].cover>1) p[id].one_len=p[id].more_len=h[r]-h[l]; else if(p[id].cover==1) { p[id].one_len=h[r]-h[l]; if(p[id].l+1==p[id].r) p[id].more_len=0; else p[id].more_len=p[id<<1].one_len+p[id<<1|1].one_len; } else { if(p[id].l+1==p[id].r) p[id].more_len=p[id].one_len=0; else { p[id].more_len=p[id<<1].more_len+p[id<<1|1].more_len; p[id].one_len=p[id<<1].one_len+p[id<<1|1].one_len; } } } void build(int l,int r,int id) { p[id].l=l; p[id].r=r; p[id].cover=0; p[id].one_len=p[id].more_len=0; if(r-l==1) return; int mid=p[id].getmid(); build(l,mid,id<<1); build(mid,r,id<<1|1); } void update(int l,int r,int flag,int id) { if(p[id].l==l&&r==p[id].r) { p[id].cover+=flag; setlen(id); return; } int mid=p[id].getmid(); if(r<=mid) update(l,r,flag,id<<1); else if(l>=mid) update(l,r,flag,id<<1|1); else { update(l,mid,flag,id<<1); update(mid,r,flag,id<<1|1); } setlen(id); } int main(void) { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); m=0; while(n--) { double x1,y1,x2,y2; scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); X[m]=x1; L[m].l=x1; L[m].r=x2; L[m].h=y1; L[m].flag=1; m++; X[m]=x2; L[m].l=x1; L[m].r=x2; L[m].h=y2; L[m].flag=-1; m++; } sort(X,X+m); sort(L,L+m,cmp); build(0,m-1,1); int mm=m; m=1; h[0]=X[0]; for(int i=1;i<mm;i++) if(X[i]!=X[i-1]) h[m++]=X[i]; double ans=0; for(int i=0;i<mm-1;i++) { int l=find(L[i].l); int r=find(L[i].r); update(l,r,L[i].flag,1); ans+=p[1].more_len*(L[i+1].h-L[i].h); } printf("%.2lf/n",ans); } }
此时线段区间的变量不能是单纯一个len了，如果只用一个变量len的话，每次update的时候就要更新到底，这样浪费很多时间，可以设置两个变量：one_len, more_len。分别记录此区间覆盖次数>=1与>=2的长度，最后用的结果就是more_len,函数setlen()描述了如何更新这两个变量
