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

 
 
 

日志

 
 

bzoj 2234 Sgu394 Berhatton  

2014-06-30 08:49:51|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
好久没写数据结构题了 再不写就又要成为一个大坑了 赶快拿点什么来练手==
-----------------------------------------------------------------------------------------------------------------
首先这题在网上可以搜到的题解主要是用 坐标变换+扫描线+BIT做的
首先把每个点坐标换为 x-y,x+y 然后每个点可以影响到的范围就是以该点为中心的
边长为2*d 的正方形 然后再把每个点拆成三个 一个是该点自身(作为询问点)
另外两个点都是事件点(这个思想在刚学扫描线的时候可以在POI采矿那题的题解中找到)
具体实现的话 就参考下代码吧
不过由于我自己的那种思路需要区间修改 为了写得方便点 就用线段树实现了==
这样做的复杂度是O(NlogN)N=n*3

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define rep(i,n) for(int i=1;i<=n;++i)
#define imax(x,y) (x>y?x:y)
#define imin(x,y) (x<y?x:y)
using namespace std;
const int N=100010,T=270000;
struct node
{
int x,z,num,x2;
long long y;
}a[N],b[N*3];
int pos[N],sum[T],flag[T];
int isans[N];
int n,m,all=0,ans=0;
bool cmp(node aa,node bb)
{
return aa.x<bb.x;
}
bool cmp2(node aa,node bb)
{
return aa.y<bb.y||(aa.y==bb.y&&aa.num<bb.num);
}
void change_tree(int x,int L,int R,int tl,int tr,int y)
{
if(L<=tl&&tr<=R)
{
sum[x]+=y;
flag[x]+=y;
return;
}
int mid=(tl+tr)>>1;
if(flag[x])
{
change_tree(x<<1,tl,mid,tl,mid,flag[x]);
change_tree(x<<1|1,mid+1,tr,mid+1,tr,flag[x]);
flag[x]=0;
}
if(L<=mid)change_tree(x<<1,L,R,tl,mid,y);
if(R>mid)change_tree(x<<1|1,L,R,mid+1,tr,y);
}
int inquiry_tree(int x,int tl,int tr,int y)
{
if(tl==tr)
return sum[x];
int mid=(tl+tr)>>1;
if(flag[x])
{
change_tree(x<<1,tl,mid,tl,mid,flag[x]);
change_tree(x<<1|1,mid+1,tr,mid+1,tr,flag[x]);
flag[x]=0;
}
if(y<=mid)return inquiry_tree(x<<1,tl,mid,y);
else return inquiry_tree(x<<1|1,mid+1,tr,y);
}
int getef(int x)
{
int L=1,R=all,mid;
while(L<R)
{
mid=(L+R)>>1;
if(pos[mid]>x)R=mid;
else L=mid+1;
}
while(pos[L]>x)--L;
return L;
}
int main()
{
int x,y,z;
scanf("%d%d",&n,&m);
rep(i,n)
{
scanf("%d%d%d",&x,&y,&z);
a[i].x=x-y;
a[i].y=x+y;
a[i].z=z;
a[i].num=i;
}
sort(a+1,a+1+n,cmp);
pos[++all]=a[1].x;
a[1].x2=1;
for(int i=2;i<=n;++i)
{
if(a[i].x!=a[i-1].x)
pos[++all]=a[i].x;
a[i].x2=all;
}
rep(i,n)
{
b[i]=a[i];
b[i+n]=a[i];b[i+n].y-=b[i].z;b[i+n].num=0;
b[i+n+n]=a[i];b[i+n+n].y+=b[i].z+1;b[i+n+n].num=-1;
}
sort(b+1,b+1+n*3,cmp2);
int tans;
for(int i=1;i<=n*3;++i)
{
if(b[i].num>0)
{
if(inquiry_tree(1,1,all,b[i].x2)>m)
{
isans[++ans]=b[i].num;
}
}
else if(!b[i].num)
{
x=getef(b[i].x+b[i].z);
y=getef(b[i].x-b[i].z-1);
change_tree(1,y+1,x,1,all,1);
}
else
{
x=getef(b[i].x+b[i].z);
y=getef(b[i].x-b[i].z-1);
change_tree(1,y+1,x,1,all,-1);
}
}
sort(isans+1,isans+1+ans);
printf("%d\n",ans);
rep(i,ans)
if(i!=ans)printf("%d ",isans[i]);
else printf("%d\n",isans[i]);
return 0;

}

这题还有CDQ分治的做法 不过还是要转坐标 还是要用BIT/线段树进行维护 最后就是nlog2n的 所以就不想写了==
  评论这张
 
阅读(220)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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