本文主要是介绍HDU 3265 Posters，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
求矩形面积的并 每个矩形里面有个小的矩形被挖空
思路：
经典的线段树扫描线 我竟然坑了3个小时没写出来…真是鄙视自己！！
学过扫描线的都会有思路 这里提出一个错误想法…（就是我的…）
你要是这样给线赋权值就大错特错了 因为会发现线段树的结构使得操作变得很麻烦
当你想更新某段区间的时候 并不知道准确的down到哪里 也不知道更新完了up要如何合并区间
当然像我一样一开始都更新到叶子节点是必须TLE的… TAT
正确思路是这样的
划分出4个矩形再求 为什么这样就对了呢？ 因为不用down
考虑每个矩形如果+1的边来了那就计数就好了 反正总有一个-1边会来到这里
如果你问第一种方法不也是可以等-1来么 答案是不可以
“能等待”这个性质需要保证现在考虑的这个小矩形内部不会有空产生 而第一种明显会有空
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL __int64
#define N 200005
#define M(x,y) ( (x+y)>>1 )
#define L(x) ( x<<1 )
#define R(x) ( (x<<1)|1 )int n,tot;
struct line
{int x,y1,y2;int flag;bool operator<(const line fa) const{if(x!=fa.x) return x<fa.x;return flag>fa.flag;}
}l[N*2];
struct node
{int l,r,cov,sum;
}tree[N*8];
LL ans;void init(int l,int r,int i)
{tree[i].l=l;tree[i].r=r;tree[i].cov=0;tree[i].sum=0;if(l+1==r) return ;int mid=M(l,r);init(l,mid,L(i));init(mid,r,R(i));
}void up(int i)
{if(tree[i].cov>0) tree[i].sum=tree[i].r-tree[i].l;else{if(tree[i].l+1==tree[i].r) tree[i].sum=0;else tree[i].sum=tree[L(i)].sum+tree[R(i)].sum;}
}void updata(int y1,int y2,int i,int flag)
{if(tree[i].l==y1&&tree[i].r==y2){tree[i].cov+=flag;up(i);return ;}int mid=M(tree[i].l,tree[i].r);if(y2<=mid) updata(y1,y2,L(i),flag);else if(y1>=mid) updata(y1,y2,R(i),flag);else{updata(y1,mid,L(i),flag);updata(mid,y2,R(i),flag);}up(i);
}int main()
{int i;int tx1,ty1,tx2,ty2,tx3,ty3,tx4,ty4;while(~scanf("%d",&n)){if(!n) break;tot=0;for(i=0;i<n;i++){scanf("%d%d%d%d%d%d%d%d",&tx1,&ty1,&tx2,&ty2,&tx3,&ty3,&tx4,&ty4);if(ty1!=ty3){l[tot].x=tx1;l[tot].y1=ty1;l[tot].y2=ty3;l[tot].flag=1;tot++;l[tot].x=tx2;l[tot].y1=ty1;l[tot].y2=ty3;l[tot].flag=-1;tot++;}
//--------------------------------if(ty4!=ty2){l[tot].x=tx1;l[tot].y1=ty4;l[tot].y2=ty2;l[tot].flag=1;tot++;l[tot].x=tx2;l[tot].y1=ty4;l[tot].y2=ty2;l[tot].flag=-1;tot++;}
//--------------------------------if(ty3!=ty4){l[tot].x=tx1;l[tot].y1=ty3;l[tot].y2=ty4;l[tot].flag=1;tot++;l[tot].x=tx3;l[tot].y1=ty3;l[tot].y2=ty4;l[tot].flag=-1;tot++;}
//--------------------------------if(ty3!=ty4){l[tot].x=tx4;l[tot].y1=ty3;l[tot].y2=ty4;l[tot].flag=1;tot++;l[tot].x=tx2;l[tot].y1=ty3;l[tot].y2=ty4;l[tot].flag=-1;tot++;}}sort(l,l+tot);init(0,50000,1);for(i=0,ans=0;i<tot;i++){if(i) ans+=(LL)(l[i].x-l[i-1].x)*tree[1].sum;updata(l[i].y1,l[i].y2,1,l[i].flag);}printf("%I64d\n",ans);}return 0;
}这篇关于HDU 3265 Posters的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
