题意:给定n个矩形,求他们的并的周长

n<=5e3,abs(x[i])<=1e4

思路:From https://www.cnblogs.com/kuangbin/archive/2013/04/10/3013437.html

真实“线段”树

 #include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef vector<int> VI;
#define fi first
#define se second
#define MP make_pair
#define N 11000
#define M 7010
#define eps 1e-8
#define pi acos(-1)
#define oo 1e9
#define MOD 10007 struct node
{
int l,r,cnt,num,c;
bool lc,rc;
}t[N<<]; struct Line
{
int x1,x2,y,f;
}line[N]; bool cmp(Line a,Line b)
{
return a.y<b.y;
} int x[N]; void build(int l,int r,int p)
{
t[p].l=x[l];
t[p].r=x[r];
t[p].cnt=t[p].num=t[p].c=;
t[p].lc=t[p].rc=false;
if(l+==r) return;
int mid=(l+r)>>;
build(l,mid,p<<);
build(mid,r,p<<|);
} void calc(int p)
{
if(t[p].c>)
{
t[p].cnt=t[p].r-t[p].l;
t[p].num=;
t[p].lc=t[p].rc=true;
return;
}
if(t[p].l+==t[p].r)
{
t[p].cnt=t[p].num=;
t[p].lc=t[p].rc=false;
}
else
{
t[p].cnt=t[p<<].cnt+t[p<<|].cnt;
t[p].lc=t[p<<].lc;
t[p].rc=t[p<<|].rc;
t[p].num=t[p<<].num+t[p<<|].num;
if(t[p<<].rc&&t[p<<|].lc) t[p].num--;
}
} void update(int l,int r,Line e,int p)
{
if(t[p].l==e.x1&&t[p].r==e.x2)
{
t[p].c+=e.f;
calc(p);
return;
}
int mid=(l+r)>>;
if(e.x2<=t[p<<].r) update(l,mid,e,p<<);
else if(e.x1>=t[p<<|].l) update(mid,r,e,p<<|);
else
{
Line tmp=e;
tmp.x2=t[p<<].r;
update(l,mid,tmp,p<<);
tmp=e;
tmp.x1=t[p<<|].l;
update(mid,r,tmp,p<<|);
}
calc(p);
} int main()
{
//freopen("poj1177.in","r",stdin);
//freopen("poj1177.out","w",stdout);
int n;
while(scanf("%d",&n)!=EOF)
{
int cnt=;
for(int i=;i<=n-;i++)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
line[cnt].x1=x1;
line[cnt].x2=x2;
line[cnt].y=y1;
line[cnt].f=;
x[cnt++]=x1;
line[cnt].x1=x1;
line[cnt].x2=x2;
line[cnt].y=y2;
line[cnt].f=-;
x[cnt++]=x2;
}
sort(line,line+cnt,cmp);
sort(x,x+cnt);
int m=unique(x,x+cnt)-x;
build(,m-,); int ans=;
int last=;
for(int i=;i<cnt-;i++)
{
update(,m-,line[i],); ans+=t[].num**(line[i+].y-line[i].y);
ans+=abs(t[].cnt-last);
last=t[].cnt;
}
update(,m-,line[cnt-],);
ans+=abs(t[].cnt-last);
printf("%d\n",ans);
} return ;
}

最新文章

  1. Oracle---------sql 中取值两列中值最大的一列
  2. C#相关
  3. html+css+javascript实现列表循环滚动示例代码
  4. 创建Java Web监听器
  5. redis window环境下的安装地址
  6. Repository模式介绍汇总
  7. Canvas 笔记(持续更新中)
  8. How to effectively work with multiple files in Vim?
  9. 什么时候用using (SPSite site = new SPSite(SPContext.Current.Web.Url))
  10. Oracle的卸载与安装
  11. 一道面试题与Java位操作 和 BitSet 库的使用
  12. javascript (十三) 函数
  13. React之组件通信
  14. 挑战常规--搭建gradle、maven私人仓库很简单
  15. 05-Mirrorgate数据库信息
  16. springMVC 使用WebApplicationContext获取ApplicationContext对象
  17. 使用CSS渐变
  18. Mysql添加字段.md
  19. Linux at 定时任务
  20. 下划线css

热门文章

  1. gitlab文件夹的权限不要随便给777
  2. 二十六、MySQL 临时表
  3. Android_组件_Activity基础
  4. SpringBoot日志输出至Logstash
  5. JZOJ 5771. 【NOIP2008模拟】遨游
  6. day 44 前端HTML
  7. 学习Spring框架系列(一):通过Demo阐述IoC和DI的优势所在
  8. Benelux Algorithm Programming Contest 2014 Final
  9. 5、CSS基础part-3
  10. 35、键盘布局的tableLayout备份