2
29
2016
0

[坑]KD-tree练习计划

之前的坑一直没填,因为找不到题

当然坑还是要填的,但是由于本人实在不太能找到kd-tree的题了于是把坑从10道减到了5道_(:зゝ∠)_

先放出最后一题的链接吧,慢慢填

http://www.lydsy.com/JudgeOnline/problem.php?id=3815

我有一种预感,这坑要填很久

现在:      4/5


bzoj4154 -->http://www.lydsy.com/JudgeOnline/problem.php?id=4154

以dfs序与深度建立k-d tree,修改就是矩阵修改,询问就是单点查询,有一个坑点,直接以坐标找点会找不到-。-,所以要记录下编号。。对于矩阵修改以及询问,打时间戳就行了。。

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0,f=1;char ch=nc();for(;(ch<'0'||ch>'9')&&(ch!='-');ch=nc());
	if(ch=='-')ch=nc(),f=-1;for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x*f;
}
#define N 100100
int i,j,k,m,n,x,y,c,q,cnt,last[N],T,in[N],out[N],now,dep[N],ans,loc[N];bool f,flag;
struct edge{int to,next;}e[N<<1];
inline void add(int u,int v){
	e[++cnt]=(edge){v,last[u]},last[u]=cnt;
	e[++cnt]=(edge){u,last[v]},last[v]=cnt;
}
struct point{int x,y,id;}P[N];
inline bool cmp(const point&a,const point&b){return f?a.x<b.x||a.x==b.x&&a.y<b.y:a.y<b.y||a.y==b.y&&a.x<b.x;}
#define Mx(a,b) (b>a?a=b:a)
#define Mn(a,b) (b<a?a=b:a)
struct Kd *null;
struct Kd{
	Kd*l,*r;int x1,x2,y1,y2,col,c,tim,t,f;point p;
	inline void up(Kd*b){Mn(x1,b->x1),Mx(x2,b->x2),Mn(y1,b->y1),Mx(y2,b->y2);}
	inline void set(const point&b){p=b,x1=x2=b.x,y1=y2=b.y,col=c=1,tim=t=0;}
	inline bool cmp(const point&b)const{return x1<=b.x&&x2>=b.x&&y1<=b.y&&y2>=b.y;}
}KD[N],*CC=KD,Null,*root;
void dfs(int x,int fa){
	in[x]=++now;
	for(int i=last[x];i;i=e[i].next)if(e[i].to!=fa)dep[e[i].to]=dep[x]+1,dfs(e[i].to,x);
	out[x]=now;
}
Kd*build(int l,int r,int d,int last){
	if(l>r)return null;int m=l+r>>1;f=d;
	nth_element(P+l+1,P+m+1,P+r+1,cmp);
	loc[P[m].id]=m;Kd*o=CC+m;o->l=null,o->r=null,o->set(P[m]),o->f=last;
	o->l=build(l,m-1,d^1,m),o->r=build(m+1,r,d^1,m);
	if(o->l!=null)o->up(o->l);if(o->r!=null)o->up(o->r);
	return o;
}
inline int ask(int o){
	int t=(CC+o)->tim,c=(CC+o)->col;
	while((CC+o)->f){
		o=(CC+o)->f;
		if((CC+o)->t>t)t=(CC+o)->t,c=(CC+o)->c;
	}return c;
}
void change(Kd*o,int c,int x1,int y1,int x2,int y2){
	if(o==null)return;
	if(o->x1>=x1&&o->x2<=x2&&o->y1>=y1&&o->y2<=y2){o->tim=o->t=i,o->c=o->col=c;return;}
	if(o->x1>x2||o->x2<x1||o->y1>y2||o->y2<y1)return;
	if(o->p.x>=x1&&o->p.x<=x2&&o->p.y>=y1&&o->p.y<=y2)o->tim=i,o->col=c;
	change(o->l,c,x1,y1,x2,y2),change(o->r,c,x1,y1,x2,y2);
}
const int mo=1e9+7;
int main(){
	for(null=&Null,T=read();T--;){
		for(CC=KD,ans=0,now=0,memset(last,0,sizeof last),cnt=0,n=read(),c=read(),q=read(),i=1;i<n;++i)add(i+1,read());
		for(dfs(1,0),i=1;i<=n;++i)P[i]=(point){in[i],dep[i],i};
		for(root=build(1,n,0,0),i=1;i<=q;++i){
			int a=read(),l=read(),c=read();
			if(c){
				if(l==0||in[a]==out[a])(CC+loc[a])->tim=i,(CC+loc[a])->col=c;
				change(root,c,in[a],dep[a],out[a],dep[a]+l);
			}else ans=(ans+1ll*i*ask(loc[a]))%mo;
		}
		printf("%d\n",ans);
	}
}

bzoj3616-->http://www.lydsy.com/JudgeOnline/problem.php?id=3616

首先m轮的话只要一轮算出来pow一下就行-。-,对于一轮,把每个点能打到的点都标记下来,这个用K-d tree 就行,然后下传整棵树,就能得到每个点会被哪些点打到,然后同阵营每一轮存活几个的概率就能得到了-。-累加一下就行了

$O(n \sqrt n + \frac{n^2}{32} )$

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<cmath>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 35500
int i,j,k,m,n,x,y,cnt,last[N],r[N],a[N],bel[N],Last[N],now,Cnt,Loc[N];
struct point{int x,y,v;}P[N],p[N];bool f;double ans;
inline int sqr(int x){return x*x;}
struct Kd{
	#define Mx(a,b) (b>a?a=b:a)
	#define Mn(a,b) (b<a?a=b:a)
	#define max(a,b) ((a)>(b)?(a):(b))
	Kd*l,*r;int x1,y1,x2,y2;point p;
	inline void up(Kd*b){Mn(x1,b->x1),Mx(x2,b->x2),Mn(y1,b->y1),Mx(y2,b->y2);}
	inline void set(const point&b){p=b,x1=x2=b.x,y1=y2=b.y;}
	inline int check1(const point&p,const int&r)const{
		int d1=sqr(max(max(p.x-x2,x1-p.x),0))+sqr(max(max(p.y-y2,y1-p.y),0))<=r*r,d2=max(sqr(p.x-x1),sqr(p.x-x2))+max(sqr(p.y-y1),sqr(p.y-y2))<=r*r;
		if(d1&&d2)return 1;if(d1)return 2;return 0;
	}
	inline int check2(const point&p,const int&d)const{
		int d1=max(x1-p.x,0)+max(p.x-x2,0)+max(y1-p.y,0)+max(p.y-y2,0)<=d,d2=max(abs(x1-p.x),abs(p.x-x2))+max(abs(y1-p.y),abs(p.y-y2))<=d;
		if(d1&&d2)return 1;if(d1)return 2;return 0;
	}
}KD[N],*CC=KD,*root,Null,*null=&Null;
struct edge{int to,next;}e[N<<1],E[10000010];
#define add(u,v) (e[++cnt]=(edge){v,last[u]},last[u]=cnt)
inline bool cmp(const point&a,const point&b){return f?a.x<b.x:a.y<b.y;}
Kd *build(int l,int r,int d){
	if(l>r)return null;int m=l+r>>1;f=d;
	nth_element(P+l+1,P+m+1,P+r+1,cmp);
	Kd*o=CC++;Loc[P[m].v]=now++,o->set(P[m]);
	o->l=build(l,m-1,d^1),o->r=build(m+1,r,d^1);
	if(o->l!=null)o->up(o->l);if(o->r!=null)o->up(o->r);
	return o;
}
bitset<N>G[N];
#define Add(u,v) (E[++Cnt]=(edge){v,Last[u]},Last[u]=Cnt)
void change(Kd*o,const point&p){
	if(o==null)return;int d1,d2;
	if((d1=o->check1(p,r[i]))==1){G[o-KD][i]=1;return;}
	if((d2=o->check2(p,a[i]))==1){G[o-KD][i]=1;return;}
	if(d2==0&&d1==0)return;
	if(sqr(o->p.x-p.x)+sqr(o->p.y-p.y)<=r[i]*r[i])Add(o-KD,i);
	else if(abs(o->p.x-p.x)+abs(o->p.y-p.y)<=a[i])Add(o-KD,i);
	change(o->l,p),change(o->r,p);
}
void down(Kd*o){
	if(o->l!=null)G[o->l-KD]|=G[o-KD],down(o->l);
	if(o->r!=null)G[o->r-KD]|=G[o-KD],down(o->r);
	for(int i=Last[o-KD];i;i=E[i].next)G[o-KD][E[i].to]=1;
}
int main(){
	for(n=read(),m=read(),k=read(),i=1;i<=n;++i)P[i].x=read(),P[i].y=read(),P[i].v=i,p[i]=P[i],r[i]=read(),a[i]=read(),bel[i]=read(),add(bel[i],i);
	for(root=build(1,n,0),i=1;i<=n;++i)change(root,p[i]);
	for(down(root),i=1;i<=k;++i){
		bitset<N>res;res.reset();
		for(j=last[i];j;j=e[j].next)res|=G[Loc[e[j].to]];
		for(j=last[i];j;j=e[j].next)res[e[j].to]=0;
		ans+=pow(1-1.0*res.count()/n,m);
	}
	printf("%.5lf",ans);
}

bzoj4130-->http://qiancl.is-programmer.com/user_files/qiancl/Image/Problem%204130.%20--%20[PA2011]Kangaroos.html

Claris bzoj4358permu 的做法给了我灵感-。-,按询问建立坐标系,然后对于序列里的每个区间依次加入,等价于区间加1和区间覆盖为0 的操作,ans就是历史最大值。。然后这个东西-。-就可以标记乱搞辣

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 200020
int i,j,k,m,n,Loc[N],now;bool f;
struct Point{int x,y,v;inline void in(){x=read(),y=read();}}P[N],Q[N];
struct point{int x,y;}PP;struct Kd*null;
struct Kd{
	#define Mn(a,b) ((b)<a?a=(b):a)
	#define Mx(a,b) ((b)>a?a=(b):a)
	Kd*l,*r;int x1,y1,x2,y2,smx,jmx,fo,jo,so;point p;
	inline void up(Kd*b){Mx(x2,b->x2),Mn(x1,b->x1),Mx(y2,b->y2),Mn(y1,b->y1);}
	inline void set(const point&b){p=b,x1=x2=b.x,y1=y2=b.y;}
	inline void down(int x,int y){if(x!=-1)(fo!=-1?Mx(jmx,x-jo-1):fo=x),Mx(smx,x-so-1),so=jo=y;}
	inline void Down(){if(l!=null)l->down(fo,jo);if(r!=null)r->down(fo,jo);fo=-1;}
	inline int check(const point&p)const{
		int k=(x1<=p.x&&y1>=p.y)+(x1<=p.x&&y2>=p.y)+(x2<=p.x&&y1>=p.y)+(x2<=p.x&&y2>=p.y);
		if(k==4)return 1;if(k)return 2;return 0;
	}
}KD[N],*CC=KD,Null,*root;
void change(Kd*o){
	if(o==null)return;int d=o->check(PP);
	if(!d){o->down(i,i);return;}if(d==1)return;
	if(o->p.x>PP.x||o->p.y<PP.y)Mx(o->smx,i-o->so-1),o->so=i;
	o->Down(),change(o->l),change(o->r);
}
inline bool cmp(const Point&a,const Point&b){return f?a.x<b.x:a.y<b.y;}
Kd*build(int l,int r,int d){
	if(l>r)return null;int m=l+r>>1;f=d;
	nth_element(P+l+1,P+m+1,P+r+1,cmp);
	Kd*o=CC++;Loc[P[m].v]=now++,o->set((point){P[m].x,P[m].y});
	o->l=build(l,m-1,d^1),o->r=build(m+1,r,d^1);
	if(o->l!=null)o->up(o->l);if(o->r!=null)o->up(o->r);
	return o;
}
void down(Kd*o,int last){if(o==null)return;o->Down(),Mx(o->smx,n-o->so),Mx(o->jmx,last),Mx(o->smx,last),Mx(o->smx,o->jmx),down(o->l,o->jmx),down(o->r,o->jmx);}
int main(){
	for(null=&Null,n=read(),m=read(),i=1;i<=n;++i)Q[i].in();
	for(i=1;i<=m;++i)P[i].in(),P[i].v=i;
	for(root=build(1,m,1),i=1;i<=n;++i)PP=(point){Q[i].y,Q[i].x},change(root);
	for(down(root,0),i=1;i<=m;++i)printf("%d\n",(KD+Loc[i])->smx);
}

bzoj3489-->http://www.lydsy.com/JudgeOnline/problem.php?id=3489

标算好像是可持久化树套树,然而k-d tree跑的不知道比树套树快到哪里去了_(:зゝ∠)_,模型随便转一下就变成裸的三维k-d tree题了,第一次写三维的好兴奋啊

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 100010
int i,j,k,m,n,x,y,f,pre[N],nex[N],a[N],I,now[N],L,R,ans;
#define inf 1000000000
struct KD{
	#define max(a,b) ((a)>(b)?(a):(b))
	#define min(a,b) ((a)<(b)?(a):(b))
	KD*l,*r;int d[3],mn[3],mx[3],v,vmx;
	int& operator [](int i){return d[i];}
	inline void up(){
		for(I=0;I<=2;++I)mn[I]=min(d[I],min(l->mn[I],r->mn[I])),mx[I]=max(d[I],max(l->mx[I],r->mx[I]));
		vmx=max(v,max(l->vmx,r->vmx));
	}
}CC[N],*c=CC,*root;
inline bool operator <(KD a,KD b){return a[f]<b[f];}
KD *build(int l,int r,int d){
	f=d;int m=l+r>>1;nth_element(CC+l,CC+m,CC+r+1);
	((CC+m)->l=l<m?build(l,m-1,(d+1)%3):CC),((CC+m)->r=m<r?build(m+1,r,(d+1)%3):CC);
	return (CC+m)->up(),CC+m;
}
inline void Mx(int&a,int b){if(b>a)a=b;}
inline bool check(KD*o){
	if(o==CC)return 0;
	if(o->mx[1]<=R||o->mn[2]>=L)return 0;
	if(o->mn[0]>R||o->mx[0]<L)return 0;
	return 1;
}
void ask(KD *o){
	if(o==CC)return;
	if(o->mn[0]>=L&&o->mx[0]<=R&&o->mn[1]>R&&o->mx[2]<L){Mx(ans,o->vmx);return;}
	if(o->d[0]>=L&&o->d[0]<=R&&o->d[1]>R&&o->d[2]<L)Mx(ans,o->v);
	if(o->l->vmx>o->r->vmx){
		if(o->l->vmx>ans&&check(o->l))ask(o->l);
		if(o->r->vmx>ans&&check(o->r))ask(o->r);
	}else{
		if(o->r->vmx>ans&&check(o->r))ask(o->r);
		if(o->l->vmx>ans&&check(o->l))ask(o->l);
	}	
}
int main(){
	for(i=0;i<=2;++i)c->mn[i]=inf,c->mx[i]=-inf;
	c->vmx=-1,n=read(),m=read();
	for(i=1;i<=n;++i)pre[i]=now[a[i]=read()],now[a[i]]=i;
	for(i=1;i<=n;++i)nex[pre[i]]=i;
	for(i=1;i<=n;++i)if(!nex[i])nex[i]=n+1;
	for(i=1;i<=n;++i)++c,c->d[0]=i,c->d[1]=nex[i],c->d[2]=pre[i],c->v=a[i];
	for(root=build(1,n,0),i=1;i<=m;++i){
		x=read(),y=read(),L=min((x+ans)%n+1,(y+ans)%n+1),R=max((x+ans)%n+1,(y+ans)%n+1);
		ans=0,ask(root),printf("%d\n",ans);
	}
	
}

 

updating...

Category: 数据结构 | Tags: | Read Count: 847

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com