线段树 矩形并周长 picture

线段树 我还是首推胡浩大牛的博客http://www.notonlysuccess.com/

线段树中扫描线一直是我比较吃力的一种题。矩形面积并，周长并，特别是周长并，一直无法解决，想不明白，现在终于做出来一个周长并的题目了， 是不是我的线段树水平又有了一点提高呢？

代码不长，写起来老麻烦了！

周长并与面积并不同的是，周长并需要记录竖着的边的情况。也就是说，需要记录边的合并问题，代码中分别使用lbd和rbd记录是否有边，如果合并的都有边，那么，合并之后的竖着的边的总数就要减2.

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 10010
struct note
{
int a,b,h,s;
note(){}
note(int l,int r,int c,int d):a(l) , b(r) , h(c) , s(d) {}
}data[N];
///线段树
#define lson l ,m ,rt<<1
#define rson m+1,r,rt<<1|1
#define fmid (l+r)>>1
#define M 22222
int len[M<<2],memseg[M<<2],lbd[M<<2],rbd[M<<2],cnt[M<<2];
void Push_up(int rt,int l,int r)
{
if(cnt[rt])
{
lbd[rt] = rbd[rt] = 1;
memseg[rt] = 2;
len[rt] = r-l+1;
}else if(l == r) lbd[rt] = rbd[rt] = memseg[rt] = len[rt] = 0;
else
{
lbd[rt] = lbd[rt<<1];
rbd[rt] = rbd[rt<<1|1];
len[rt] = len[rt<<1] + len[rt<<1|1];
memseg[rt] = memseg[rt<<1] + memseg[rt<<1|1];
if(rbd[rt<<1] && lbd[rt<<1|1] ) memseg[rt] -= 2;
}
}
/**
*矩形有个特点，已经出现的更新，必然会再次出现，这样的话，延迟标记也就可以不用push_down()!
*/
void update(int lx,int rx,int s,int l,int r,int rt)
{
if(lx <= l && rx >= r)
{
cnt[rt] += s;
Push_up(rt,l,r);
return;
}
int m = fmid;
if(lx <= m) update(lx,rx,s,lson);
if(m < rx) update(lx,rx,s,rson);
Push_up(rt,l,r);
}
//
bool cmp(const note a,const note b)
{
return a.h < b.h || (a.h == b.h && a.s < b.s); ///?????排序的时候可以不对s进行比较
}
int main()
{
int n;
while(~scanf("%d",&n))
{
int x,y,xx,yy;
int ll = 10000,rr = -10000;
int m = 0;
for(int i = 0;i < n;i++)
{
scanf("%d%d%d%d",&x,&y,&xx,&yy);
ll = min(ll,x);
rr = max(rr,xx);
data[m++] = note(x,xx,y,1);
data[m++] = note(x,xx,yy,-1);
}
sort(data,data+m,cmp);
data[m].h = data[m-1].h;
int ret = 0,last = 0;
for(int i = 0;i < m;i++)
{
if(data[i].a != data[i].b) update(data[i].a ,data[i].b-1,data[i].s,ll,rr,1);
ret += abs(len[1] - last);
ret += memseg[1] * (data[i+1].h - data[i].h);
last = len[1];
}
printf("%dn",ret);
}
return 0;
}

最后

以上就是难过小鸭子为你收集整理的线段树 矩形并周长 picture的全部内容，希望文章能够帮你解决线段树 矩形并周长 picture所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。