最近在补数学和几何，没啥好写的，因为已经决定每天至少写一篇了，今天随便拿个题水水。
题目大意：给你N个边平行于坐标轴的矩形，求它们并的周长。(N<=5000)
思路：这个数据范围瞎暴力就过了，但我们是有文化的人，下面讲讲利用扫描线和线段树的简单O(NlogN)做法。
先讲扫描线。我们先只考虑横着的边，竖着的等会儿一样做就是了。我们假设有一条横着的直线（这条就是扫描线啦）从所有矩形的上方扫到所有矩形的下方，我们时刻维护这条线上各个位置分别被几个矩形覆盖，一开始肯定都是0，如果碰到一个矩形上方的边，我们先查看这条边上哪些部分还未被其他矩形覆盖，计入答案，然后把扫描线上的这一整条边的被覆盖次数加一；如果遇到一个矩形下方的边，同理我们先把扫描线上这一部分的被覆盖次数减一，看看那些部分已经未被其他矩形覆盖了（即被当前边最后覆盖），再计入答案，扫一遍所有矩形，就算完了。实现上我们可以把所有横的边拿出来，记下纵坐标和左右端点，以及是矩形上方还是下方的边，然后按纵坐标排个序就可以处理了。
那么如何维护呢？我们只要支持区间加减以及查询区间内0的个数，看上去线段树就能做，区间加减都是小Case，问题是如何查区间内0的个数？在区间加减的同时似乎不是很好维护。其实很简单，我们只要维护区间最小值和最小值个数就可以了，由我们维护的信息的意义可知，这些信息的最小值不会小于0，如果有0，查询最小值及个数时一定能被我们找到，维护最小值区间加减也很容易。网络上看见有人O(n)暴力维护的，还有线段树维护很多信息来计算的，感觉都不是很好，更有甚者在线段树上每次O(n)暴力维护，看了令人汗颜……
#include<cstdio> #include<algorithm> using namespace std; #define MN 10000 #define MX 20000 #define L (k<<1) #define R ((k<<1)+1) struct work{int x,l,r,p;}x[MN+5],y[MN+5]; bool cmp(work a,work b){return a.x==b.x?a.p>b.p:a.x<b.x;} struct data{int x,s;}; data operator+(data a,data b) { if(a.x==b.x)return(data){a.x,a.s+b.s}; return a.x<b.x?a:b; } struct node{int l,r,mk;data x;}t[MX*4+5]; inline void up(int k){t[k].x=t[L].x+t[R].x;} inline void add(int k,int x){t[k].x.x+=x;t[k].mk+=x;} inline void down(int k){if(t[k].mk)add(L,t[k].mk),add(R,t[k].mk),t[k].mk=0;} void build(int k,int l,int r) { t[k].l=l;t[k].r=r; if(l==r){t[k].x.s=1;return;} int mid=l+r>>1; build(L,l,mid);build(R,mid+1,r); up(k); } void renew(int k,int l,int r,int x) { if(t[k].l==l&&t[k].r==r){add(k,x);return;} down(k); int mid=t[k].l+t[k].r>>1; if(r<=mid)renew(L,l,r,x); else if(l>mid)renew(R,l,r,x); else renew(L,l,mid,x),renew(R,mid+1,r,x); up(k); } data query(int k,int l,int r) { if(t[k].l==l&&t[k].r==r)return t[k].x; down(k); int mid=t[k].l+t[k].r>>1; if(r<=mid)return query(L,l,r); if(l>mid)return query(R,l,r); return query(L,l,mid)+query(R,mid+1,r); } int n,ans; void solve(work*x) { for(int i=0;i<n;++i) { if(x[i].p<0)renew(1,x[i].l,x[i].r,-1); data d=query(1,x[i].l,x[i].r); if(x[i].p>0)renew(1,x[i].l,x[i].r,1); ans+=d.x?0:d.s; } } int main() { int i,x0,y0,x1,y1; scanf("%d",&n); for(i=0;i<n;++i) { scanf("%d%d%d%d",&x0,&y0,&x1,&y1); x0+=MN;y0+=MN;x1+=MN;y1+=MN; x[i]=(work){y0,x0,x1-1,1};x[i+n]=(work){y1,x0,x1-1,-1}; y[i]=(work){x0,y0,y1-1,1};y[i+n]=(work){x1,y0,y1-1,-1}; } n<<=1;sort(x,x+n,cmp);sort(y,y+n,cmp); build(1,0,MX);solve(x);solve(y); printf("%d",ans); }