[矩形并-掃描線-線段樹]Picture

最近在補數學和幾何，沒啥好寫的，因為已經決定每天至少寫一篇了，今天隨便拿個題水水。

?

題目大意：給你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);
}

?