求周长并，思路和注意事项与求面积并类似，我用了最简单的思路，即x轴做一次线段树，y轴做一次线段树。
还有一种方法，只做一次线段树，在做线段树的同时求另一个方向的长度，大概的想法我知道，不过在左右区间合并
这个问题上不是很理解。
做了两个线段树的题目，分别是求面积并和周长并。这些问题是几何问题，是二维的，运用线段树可以先在一个维度
上，得到当前覆盖的线段的长度。
还遗留一个问题：对边排序时，为什么y坐标相同，入线排在出线的前面？
画了两个矩形演示了一下，如果两个矩形是相交的，先入线后出线，没有问题；如果两个矩形的出线和入线重合，
如果先出线后入线，会导致多算重合部分的长度
#include<cstdio> #include<algorithm> #include<algorithm> using namespace std; const int maxn=5010;//矩形最大个数 struct edge{ int a1,a2,b; int f;//1表示入，-1表示出 edge(){} edge(int _a1,int _a2,int _b,short _f) { a1=_a1,a2=_a2,b=_b,f=_f; } bool operator <(const edge&e){ if(b!=e.b) return b<e.b; else return f>e.f; } }; int num[maxn*2*4]; int len[maxn*2*4]; void build(int root,int l,int r) { num[root]=len[root]=0; if(l==r)return; int mid=(l+r)/2; build(root*2,l,mid); build(root*2+1,mid+1,r); } void pushUp(int root,int l,int r,int a[]) { if(num[root]!=0)len[root]=a[r+1]-a[l]; else if(l==r)len[root]=0; else len[root]=len[root*2]+len[root*2+1]; } void update(int root,int L,int R,int f,int l,int r,int a[]) { if(L<=l&&r<=R){ num[root]+=f; pushUp(root,l,r,a); return; } int mid=(l+r)/2; if(L<=mid)update(root*2,L,R,f,l,mid,a); if(mid<R)update(root*2+1,L,R,f,mid+1,r,a); pushUp(root,l,r,a); } int nEx,nEy; edge ex[maxn*2],ey[maxn*2]; int nVx,nVy; int vx[maxn*2],vy[maxn*2]; int bin(int k,int a[],int n) { int l=0,r=n-1,mid; while(l<=r){ mid=(l+r)/2; if(a[mid]==k)return mid; else if(a[mid]>k)r=mid-1; else l=mid+1; } return -1; } int myUnique(int a[],int n) {//有序去重 int sz=1; for(int i=1;i<n;i++){ if(a[i]!=a[i-1])a[sz++]=a[i]; } return sz; } int main() { //freopen("in.txt","r",stdin); int n; while(scanf("%d",&n)!=EOF&&n!=0){ nEx=nEy=nVx=nVy=0; for(int i=0;i<n;i++){ int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); vx[nVx++]=x1,vx[nVx++]=x2; vy[nVy++]=y1,vy[nVy++]=y2; ex[nEx++]=edge(x1,x2,y1,1); ex[nEx++]=edge(x1,x2,y2,-1); ey[nEy++]=edge(y1,y2,x1,1); ey[nEy++]=edge(y1,y2,x2,-1); } sort(ex,ex+nEx); sort(vx,vx+nVx); nVx=myUnique(vx,nVx); build(1,0,nVx-1); int preL=0,curL=0,tot=0; for(int i=0;i<nEx;i++){ int l=bin(ex[i].a1,vx,nVx); int r=bin(ex[i].a2,vx,nVx)-1; update(1,l,r,ex[i].f,0,nVx-1,vx); preL=curL; curL=len[1]; //printf("%d ",len[1]); tot+=abs(curL-preL); } //puts(" "); sort(ey,ey+nEy); sort(vy,vy+nVy); nVy=myUnique(vy,nVy); build(1,0,nVy-1); preL=curL=0; for(int i=0;i<nEy;i++){ int l=bin(ey[i].a1,vy,nVy); int r=bin(ey[i].a2,vy,nVy)-1; update(1,l,r,ey[i].f,0,nVy-1,vy); //printf("%d ",len[1]); preL=curL; curL=len[1]; tot+=abs(curL-preL); } printf("%d ",tot); } //while(1); }
参考资料