poj 1171 Picture 线段树

60 阅读 0 评论 40 点赞

我是靠谱客的博主可爱发夹，最近开发中收集的这篇文章主要介绍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("%dn",ans);
}
}