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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1818][Cqoi2010]内部白点  

2014-12-16 16:38:07|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1818: [Cqoi2010]内部白点

大水题……
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1E5+100;
const int P = N*2;
int n,m,list[N],T;
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return re*fh;
}
struct Point{
Point(){}
int x,y;
Point (int a,int b):x(a),y(b){}
}point[N];
int ROOT,lson[P],rson[P],tree[P],down[N],up[N];
int Build(int l=1,int r=list[0]){
int re = ++T;
if(l<r){
int mid=(l+r)/2;
lson[re] = Build(l,mid);
rson[re] = Build(mid+1,r);
//tree[re] = tree[lson[re]] + tree[rson[re]];
}//else tree[re] = down[l] && up[l];
return re;
}
inline void move(int ro,int x,int l=1,int r=list[0]){
if(l==r){
up[l]++;down[l]--;
tree[ro] = (up[l]!=0) && (down[l]!=0);
return;
}
int mid = (l+r)/2;
if(x<=mid) move(lson[ro],x,l,mid);
else move(rson[ro],x,mid+1,r);
tree[ro] = tree[lson[ro]] + tree[rson[ro]];
}
inline int ask(int ro,int la,int ra,int l=1,int r=list[0]){
//if(ro==ROOT){printf("%d %d %d\n",la,ra,tree[ro]);}
if(la > ra)return 0;
if(la<=l && r<=ra)return tree[ro];
int re=0,mid = (l+r)/2;
if(la<=mid)re += ask(lson[ro],la,ra,l,mid);
if(mid+1<=ra)re += ask(rson[ro],la,ra,mid+1,r);
return re;
}
bool operator < (Point a,Point b){return a.y==b.y?a.x<b.x:a.y<b.y;}
int main(){
//freopen("in.txt","r",stdin);
int i,j,a,b;
n = scan();
for(i=1;i<=n;i++){
a = scan();b = scan();
point[i] = Point(a,b);
list[++list[0]] = a;
}
//printf("sort\n");
sort(point+1,point+1+n);
sort(list+1,list+1+list[0]);
list[0] = unique(list+1,list+1+list[0])-list-1;
//printf("Clac\n");
for(i=1;i<=n;i++){
point[i].x = lower_bound(list+1,list+1+list[0],point[i].x)-list;
down[point[i].x]++;
}
//printf("Build\n");
ROOT = Build();
ll ans=0;int last;
for(i=1;i<=n;i++){
if(i==1 || point[i].y!=point[i-1].y)last = n+1;

ans += ask(ROOT,last+1,point[i].x-1);
last = point[i].x;
move(ROOT,point[i].x);
}
cout << ans+n << endl;
return 0;
}

题解:
基本思路就是按照y第一关键字x第二关键字排序之后扫一遍,用线段树维护一下需要的信息。
可以说是[SDOI2009]虔诚的墓主人这题弱化版
  评论这张
 
阅读(53)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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