758
poj 1171 Picture 線段樹
經典的線段樹問題，看了好久才看懂
解法很簡單，按y坐標從小到大，依次掃描每條線段，每次利用線段樹記錄當前圖形在x軸上的投影，然後用這次投影減去上次就是x軸上變化量，而y軸，因為按y軸枚舉，隻需要用y的差值乘以2再乘以當前線段數即可。
而線段樹的處理就是遇到下邊是加入線段樹，遇到上邊刪去及記錄當前投影長度，及投影分段情況
看到網上還有種括號匹配的方法，離散化後枚舉，複雜度n^2
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 5005
#define lson l,m,rt<<1
#define rson m,r,rt<<1|1
struct Node
{
int num,len,lnum,lazy; //num為此線段覆蓋次數，len為覆蓋長度，lnum為段數，lazy為延遲數
bool lc,rc; //表示線段兩端有無被覆蓋
};
struct Line
{
int l,r,y;
bool up;
};
Line line[maxn<<1];
Node node[maxn<<2];
int num,x[maxn<<1];
void pushup(int rt)//向上更新
{
node[rt].len=node[rt<<1].len+node[rt<<1|1].len;
node[rt].lnum=node[rt<<1].lnum+node[rt<<1|1].lnum;
node[rt].lc=node[rt<<1].lc;
node[rt].rc=node[rt<<1|1].rc;
node[rt].num=max(node[rt<<1].num,node[rt<<1|1].num);
if(node[rt<<1].rc&&node[rt<<1|1].lc) node[rt].lnum--;//如果左孩子的右節點和右孩子的左節點都被標記，則線段數減1
return;
}
void pushdown(int rt,int l,int r)//向上更新
{
if(node[rt].lazy)
{
int m=l+r>>1;
node[rt<<1].len=x[m-1]-x[l-1];
node[rt<<1|1].len=x[r-1]-x[m-1];
node[rt<<1].num+=node[rt].lazy;
node[rt<<1|1].num+=node[rt].lazy;
node[rt<<1].lazy+=node[rt].lazy;
node[rt<<1|1].lazy+=node[rt].lazy;
if(node[rt<<1].num>0) node[rt<<1].lnum=node[rt<<1].lc=node[rt<<1].rc=1;
else node[rt<<1].num=node[rt<<1].len=node[rt<<1].lnum=node[rt<<1].lc=node[rt<<1].rc=0; //如果覆蓋數為0，則刪除
if(node[rt<<1|1].num>0) node[rt<<1|1].lnum=node[rt<<1|1].lc=node[rt<<1|1].rc=1;
else node[rt<<1|1].num=node[rt<<1|1].len=node[rt<<1|1].lnum=node[rt<<1|1].lc=node[rt<<1|1].rc=0;
}
node[rt].lazy=0;
}
void add(int L,int R,int l,int r,int rt)//增加線段
{
if(L<=l&&R>=r)
{
node[rt].len=x[r-1]-x[l-1];
node[rt].num++;
node[rt].lc=node[rt].rc=node[rt].lnum=1;
node[rt].lazy++;//延遲更新
return;
}
pushdown(rt,l,r);
int m=(l+r)>>1;
if(L<m)add(L,R,lson);
if(R>m)add(L,R,rson);
pushup(rt);
return;
}
void del(int L,int R,int l,int r,int rt)//刪除線段
{
if(L<=l&&R>=r)
{
node[rt].num--;
if(node[rt].num<=0)
{
node[rt].len=0;
node[rt].lc=node[rt].rc=node[rt].lnum=0;
node[rt].num=0;
node[rt].lazy--;//如果此線段被刪除，延遲更新子線段
return;
}
if(r-l==1)return;
}
pushdown(rt,l,r);
int m=(l+r)>>1;
if(L<m)del(L,R,lson);
if(R>m)del(L,R,rson);
pushup(rt);
return;
}
bool cmp(Line a,Line b)
{
if(a.y==b.y) return a.l<b.l;
else return a.y<b.y;
}
inline int find(int key)//查詢x坐標對應的下標，因為線段樹要求從1開始，所以下標加1
{
return lower_bound(x,x+num,key)-x+1;
}
int main()
{
int n,i,x1,x2,y1,y2;
while(~scanf("%d",&n))
{
memset(node,0,sizeof(node));
num=0;
for(i=0;i<n;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x[num++]=x1;x[num++]=x2;
line[i<<1].l=x1;line[i<<1].r=x2;line[i<<1].y=y1;line[i<<1].up=1;
line[i<<1|1].l=x1;line[i<<1|1].r=x2;line[i<<1|1].y=y2;line[i<<1|1].up=0;
}
sort(x,x+num);//對x排序，離散化處理
num=unique(x,x+num)-x;//去重
n=n<<1;
sort(line,line+n,cmp);
int pre=0,ans=0;
for(i=0;i<n-1;i++)
{
if(line[i].up)//如果是下邊，則加邊
add(find(line[i].l),find(line[i].r),1,num,1);
else //如果是上邊，則刪除
del(find(line[i].l),find(line[i].r),1,num,1);
ans+=node[1].lnum*(line[i+1].y-line[i].y)*2;//平行y軸
ans+=abs(node[1].len-pre);//平行x軸
pre=node[1].len;
}
del(find(line[i].l),find(line[i].r),1,num,1);
ans+=abs(node[1].len-pre);
printf("%d\n",ans);
}
}
最後更新：2017-04-03 16:48:46