1
7
2016
0

[bzoj]1176&2683&4066: 简单题

1176-->http://qiancl.is-programmer.com/user_files/qiancl/File/Problem%201176.%20--%20[Balkan2007]Mokia.html

2683-->http://qiancl.is-programmer.com/user_files/qiancl/File/Problem%202683.%20--%20%E7%AE%80%E5%8D%95%E9%A2%98.html

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

以前的坑,今天填了。。三倍经验题好爽啊

裸的k-d tree,注意直接上会T,插若干次重构就行

 

#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 f*x;
}
#define N 200100
struct point{int x,y,v;}q[N];
#define Mx(a,b) (b>a?a=b:a)
#define Mn(a,b) (b<a?a=b:a)
struct KD{
	KD*l,*r;int x1,x2,y1,y2,v,sum;point p;
	inline void up(KD*b){Mn(x1,b->x1),Mx(x2,b->x2),Mn(y1,b->y1),Mx(y2,b->y2),sum+=b->sum+b->v;}
	inline void set(const point&b){p=b,v=b.v,x1=x2=b.x,y1=y2=b.y;}
}*C[N],Null,*root,*null=&Null;
int i,j,k,n,m,s,x1,y1,ans,x2,y2,x,y,flag,v,cnt,w;bool f;
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;}
inline void insert(KD*root,const point&p){
	KD*o=new KD();o->set(p),o->l=o->r=null,f=0;
	if(root==null){::root=o;return;}
	for(;1;f^=1){
		if(p.x==root->p.x&&p.y==root->p.y){root->v+=p.v;return;}root->up(o);
		if(cmp(o->p,root->p))if(root->l==null){root->l=o;break;}else root=root->l;
		else if(root->r==null){root->r=o;break;}else root=root->r;
	}
}
KD *build(int l,int r,int d){
	if(l>r)return null;int m=l+r>>1;f=d;
	nth_element(q+l+1,q+m+1,q+r+1,cmp);
	delete C[w],C[w]=new KD();KD*o=C[w++];o->set(q[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;
}
void dfs(KD*o){if(o==null)return;dfs(o->l),q[++cnt]=(point){o->p.x,o->p.y,o->v},dfs(o->r);}
inline void rebuild(KD*o){cnt=0,dfs(o),w=0,root=build(1,cnt,0);}
int ask(KD*o,int x1,int y1,int x2,int y2){
	if(o==null)return 0;
	if(o->x1>=x1&&o->y1>=y1&&o->x2<=x2&&o->y2<=y2)return o->v+o->sum;
	int ans=0;
	if(o->p.x>=x1&&o->p.x<=x2&&o->p.y>=y1&&o->p.y<=y2)ans+=o->v;
	if(!(o->l->x1>x2||o->l->x2<x1||o->l->y1>y2||o->l->y2<y1))ans+=ask(o->l,x1,y1,x2,y2);
	if(!(o->r->x1>x2||o->r->x2<x1||o->r->y1>y2||o->r->y2<y1))ans+=ask(o->r,x1,y1,x2,y2);
	return ans;
}
int main(){
	s=read(),n=read(),root=null;
	while(1){
		if((flag=read())==3)return 0;
		if(flag==1){
			x=read(),y=read(),v=read();
			insert(root,(point){x,y,v}),++m;
			if(m==15000)rebuild(root),m=0;
		}else{
			x1=read(),y1=read(),x2=read(),y2=read();
			printf("%d\n",ask(root,x1,y1,x2,y2)+s*(x2-x1+1)*(y2-y1+1));
		}
	}
}
#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 f*x;
}
struct point{int x,y,v;};
#define N 200100
#define Mx(a,b) (b>a?a=b:a)
#define Mn(a,b) (b<a?a=b:a)
struct KD{
	KD*l,*r;int x1,x2,y1,y2,v,sum;point p;
	inline void up(KD*b){Mn(x1,b->x1),Mx(x2,b->x2),Mn(y1,b->y1),Mx(y2,b->y2),sum+=b->sum+b->v;}
	inline void set(const point&b){p=b,v=b.v,x1=x2=b.x,y1=y2=b.y;}
}*q[N],Null,*root,*null=&Null;
int i,j,k,n,m,x1,y1,x2,y2,x,y,flag,v,cnt;bool f;
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;}
inline bool cmp1(KD*a,KD*b){return f?a->p.x<b->p.x||a->p.x==b->p.x&&a->p.y<b->p.y:a->p.y<b->p.y||a->p.y==b->p.y&&a->p.x<b->p.x;}
inline void insert(KD*root,const point&p){
	KD*o=new KD();o->set(p),o->l=o->r=null,f=0;
	if(root==null){::root=o;return;}
	for(;1;f^=1){
		if(p.x==root->p.x&&p.y==root->p.y){root->v+=p.v;return;}root->up(o);
		if(cmp(o->p,root->p))if(root->l==null){root->l=o;break;}else root=root->l;
		else if(root->r==null){root->r=o;break;}else root=root->r;
	}
}
int ask(KD*o,int x1,int y1,int x2,int y2){
	if(o==null)return 0;
	if(o->x1>=x1&&o->y1>=y1&&o->x2<=x2&&o->y2<=y2)return o->v+o->sum;
	int ans=0;
	if(o->p.x>=x1&&o->p.x<=x2&&o->p.y>=y1&&o->p.y<=y2)ans+=o->v;
	if(!(o->l->x1>x2||o->l->x2<x1||o->l->y1>y2||o->l->y2<y1))ans+=ask(o->l,x1,y1,x2,y2);
	if(!(o->r->x1>x2||o->r->x2<x1||o->r->y1>y2||o->r->y2<y1))ans+=ask(o->r,x1,y1,x2,y2);
	return ans;
}
int main(){
	n=read(),root=null;
	while(1){
		if((flag=read())==3)return 0;
		if(flag==1){
			x=read(),y=read(),v=read();
			insert(root,(point){x,y,v});
		}else{
			x1=read(),y1=read(),x2=read(),y2=read();
			printf("%d\n",ask(root,x1,y1,x2,y2));
		}
	}
}
#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 f*x;
}
#define N 200100
struct point{int x,y,v;}q[N];
#define Mx(a,b) (b>a?a=b:a)
#define Mn(a,b) (b<a?a=b:a)
struct KD{
	KD*l,*r;int x1,x2,y1,y2,v,sum;point p;
	inline void up(KD*b){Mn(x1,b->x1),Mx(x2,b->x2),Mn(y1,b->y1),Mx(y2,b->y2),sum+=b->sum+b->v;}
	inline void set(const point&b){p=b,v=b.v,x1=x2=b.x,y1=y2=b.y;}
}*C[N],Null,*root,*null=&Null;
int i,j,k,n,m,x1,y1,ans,x2,y2,x,y,flag,v,cnt,w;bool f;
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;}
inline void insert(KD*root,const point&p){
	KD*o=new KD();o->set(p),o->l=o->r=null,f=0;
	if(root==null){::root=o;return;}
	for(;1;f^=1){
		if(p.x==root->p.x&&p.y==root->p.y){root->v+=p.v;return;}root->up(o);
		if(cmp(o->p,root->p))if(root->l==null){root->l=o;break;}else root=root->l;
		else if(root->r==null){root->r=o;break;}else root=root->r;
	}
}
KD *build(int l,int r,int d){
	if(l>r)return null;int m=l+r>>1;f=d;
	nth_element(q+l+1,q+m+1,q+r+1,cmp);
	delete C[w],C[w]=new KD();KD*o=C[w++];o->set(q[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;
}
void dfs(KD*o){if(o==null)return;dfs(o->l),q[++cnt]=(point){o->p.x,o->p.y,o->v},dfs(o->r);}
inline void rebuild(KD*o){cnt=0,dfs(o),w=0,root=build(1,cnt,0);}
int ask(KD*o,int x1,int y1,int x2,int y2){
	if(o==null)return 0;
	if(o->x1>=x1&&o->y1>=y1&&o->x2<=x2&&o->y2<=y2)return o->v+o->sum;
	int ans=0;
	if(o->p.x>=x1&&o->p.x<=x2&&o->p.y>=y1&&o->p.y<=y2)ans+=o->v;
	if(!(o->l->x1>x2||o->l->x2<x1||o->l->y1>y2||o->l->y2<y1))ans+=ask(o->l,x1,y1,x2,y2);
	if(!(o->r->x1>x2||o->r->x2<x1||o->r->y1>y2||o->r->y2<y1))ans+=ask(o->r,x1,y1,x2,y2);
	return ans;
}
int main(){
	n=read(),root=null;
	while(1){
		if((flag=read())==3)return 0;
		if(flag==1){
			x=read()^ans,y=read()^ans,v=read()^ans;
			insert(root,(point){x,y,v}),++m;
			if(m==16000)rebuild(root),m=0;
		}else{
			x1=read()^ans,y1=read()^ans,x2=read()^ans,y2=read()^ans;
			printf("%d\n",ans=ask(root,x1,y1,x2,y2));
		}
	}
}

 

loading...

Category: bzoj | Tags: 重构 K-D tree | Read Count: 902

登录 *


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