注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

USACO 5.5.1 Picture 线段树  

2012-08-31 13:43:28|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
高一的一位同学问了我这个问题,
搞了蛮久,然后发现自己不会做,T-T
可耻啊。
于是最终还是把这道题写了,其实真心很简单,被暴力的算法误导了,悲剧

/*
LANG:C++
PROB:picture
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXL=100000*2;
const int MAX=10000+10;

struct line
{
int l,r,flag,x;
line(int d,int a,int b,int c){x=d;l=a;r=b;flag=c;}
line(){}
}x[MAX],y[MAX];
int tx,ty;
int operator < (const line& a,const line& b)
{
if(a.x!=b.x)return a.x<b.x;
else return a.flag>b.flag;
}

int n,ans;

struct node
{
int sum,cover,delta;
node(){cover=sum=delta=0;}
}tree[MAXL*4];

void down(int u,int l,int r)
{
if(u<MAXL*4 && tree[u].delta)
{
tree[u].cover+=tree[u].delta;
tree[u].delta=0;
}
}

void update(int u,int l,int r)
{
if(tree[u].cover>0)tree[u].sum=r-l+1;
else tree[u].sum=tree[u*2].sum+tree[u*2+1].sum;
}

void revice(int now,int l,int r,int a,int b,int d)
{
if(r<a || b<l )return;
if(a<=l && r<=b)
{
tree[now].delta+=d;
down(now,l,r);
update(now,l,r);
return;
}
down(now,l,r);
int mid=(l+r)>>1;
revice(now*2,l,mid,a,b,d);
revice(now*2+1,mid+1,r,a,b,d);
update(now,l,r);
}

int work(line* a,int n)
{
sort(a+1,a+n+1);
memset(tree,0,sizeof tree);
int i,ans=0,c,d;
for(i=1;i<=n;++i)
{
c=tree[1].sum;
revice(1,1,30000,a[i].l,a[i].r-1,a[i].flag);
d=tree[1].sum;
ans+=abs(d-c);
}
return ans;
}

int main()
{
freopen("picture.in","r",stdin);freopen("picture.out","w",stdout);
int x1,y1,x2,y2,i;
scanf("%d",&n);
for(i=1;i<=n;++i)
{
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
x1+=10001;y1+=10001;x2+=10001;y2+=10001;
x[++tx]=line(x1,y1,y2,1);
x[++tx]=line(x2,y1,y2,-1);
y[++ty]=line(y1,x1,x2,1);
y[++ty]=line(y2,x1,x2,-1);
}
ans+=work(x,tx);
ans+=work(y,ty);
printf("%d\n",ans);
return 0;
}




  评论这张
 
阅读(197)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018