HDU - 1828 Picture

线段树求矩形周长并

写得十分优美（自己改得已经不优美了）

和求面积的一样的思路，不同的是，对于竖着的周长，每次对答案的贡献是这次和上次在Y轴投影之差的绝对值，对于横着的周长，要考虑一段区间里可能有很多隔着一段距离的矩形，我们记录ll，rr分别表示左边和右边是不是一个矩形（合并的时候处理中间是不是同一个矩形），ss表示这段区间一共有多少个矩形，横着的对答案的贡献就是 ss[1]*2*(x[i+1]-x[i]);

//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#define lc x<<1
#define rc x<<1|1
#define mid ((l+r)>>1)
#define MX 1e9
#define MI -1e9
using namespace std;
const int maxn=(10000+9)*2;
const int maxm=5000+9;
struct edge {
int x,y1,y2,v;
edge(){}
edge(int x,int y1,int y2,int v):x(x),y1(y1),y2(y2),v(v){}
friend bool operator <(const edge&A,const edge&B) {
return A.x<B.x||(A.x==B.x&&A.v>B.v);
}
}e[maxn*2];
int n,a,tot,sz,b,c,d,y[maxn],sg[maxn*2],ll[maxn*2],rr[maxn*2],ss[maxn*2],sum[maxn*2],ans,ql,qr,val;
void add(int x,int l,int r) {
if(y[l]>=ql&&y[r]<=qr) sg[x]+=val;
else {
if(ql<y[mid]) add(lc,l,mid);
if(qr>y[mid]) add(rc,mid,r);
}
if(sg[x]) {ll[x]=rr[x]=ss[x]=1; sum[x]=y[r]-y[l];}
else if(l==r) ll[x]=rr[x]=ss[x]=sum[x]=0;
else {
ll[x]=ll[lc]; rr[x]=rr[rc];
ss[x]=ss[lc]+ss[rc]-(rr[lc]&ll[rc]);
sum[x]=sum[lc]+sum[rc];
}
}
void clear(){
memset(ll,0,sizeof(ll));
memset(rr,0,sizeof(rr));
memset(sg,0,sizeof(sg));
memset(sum,0,sizeof(sum));
memset(ss,0,sizeof(ss));
}
int main()
{
while(~scanf("%d",&n))
{
tot=0;
clear();
for(int i=1;i<=n;i++) {
scanf("%d%d%d%d",&a,&b,&c,&d);
e[++tot]=edge(a,b,d,1); y[tot]=b;
e[++tot]=edge(c,b,d,-1); y[tot]=d;
}
sort(y+1,y+tot+1);
sort(e+1,e+tot+1);
sz=unique(y+1,y+tot+1)-(y+1);
int pre=0; ans=0;
for(int i=1;i<=tot;i++) {
ql=e[i].y1; qr=e[i].y2; val=e[i].v;
add(1,1,sz);
ans+=((e[i+1].x-e[i].x)*ss[1]*2+abs(sum[1]-pre));
pre=sum[1];
}
printf("%dn",ans);
}
return 0;
}