mcfx's blog - kdtree

mcfx's blog - kdtree 2016-12-11T14:51:00+08:00 Typecho /feed/atom/category/kd/ <![CDATA[BZOJ 1176&2683&4066]]> /archives/97/ 2016-12-11T14:51:00+08:00 2016-12-11T14:51:00+08:00 admin

[传送门][1] [传送门][2] [传送门][3]

题目大意：单点加，矩阵查询
直接上kdtree就好了，定期暴力重构

1176题代码：
```c++
#include<bits/stdc++.h>

typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

#define xx first
#define yy second

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline void repr(T &a,T b){if(a<b)a=b;}
template<typename T> inline void repl(T &a,T b){if(a>b)a=b;}
template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;}
template<typename T> T sqr(T x){return x*x;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define lb(x) ((x)&(-(x)))

namespace kd
{
	const int D=2,inf=1000000000;
	
	char dnow;
	
	struct point
	{
		int d[D],val;
		int operator[](int x){return d[x];}
	};
	
	inline bool operator<(point a,point b)
	{
		return a[dnow]<b[dnow];
	}
	
	inline int dis(point a,point b){int ret=0;for(int i=0;i<D;i++)ret+=abs(a[i]-b[i]);return ret;}
	
	struct kdnode
	{
		point p;
		int sum,l[D],r[D],lc,rc;
	};
	
	int ans,tm=2;
	point q1,q2,Q,*P;
	kdnode t[200010];
	
	inline void update(int k)
	{
		for(int i=0;i<D;i++)
		{
			if(t[k].lc)repl(t[k].l[i],t[t[k].lc].l[i]),repr(t[k].r[i],t[t[k].lc].r[i]);
			if(t[k].rc)repl(t[k].l[i],t[t[k].rc].l[i]),repr(t[k].r[i],t[t[k].rc].r[i]);
		}
		t[k].sum=t[k].p.val+t[t[k].lc].sum+t[t[k].rc].sum;
	}
	inline void init(int x)
	{
		for(int i=0;i<D;i++)t[x].l[i]=t[x].r[i]=t[x].p[i];t[x].sum=t[x].p.val;
	}
	int build(int l,int r,char now)
	{
		if(now==D)now=0;
		dnow=now;
		int mid=(l+r)>>1,x=tm++;
		std::nth_element(P+l,P+mid,P+r+1);
		t[x].p=P[mid];
		t[x].lc=t[x].rc=0;
		init(x);
		if(l<mid)t[x].lc=build(l,mid-1,now+1);
		if(r>mid)t[x].rc=build(mid+1,r,now+1);
		update(x);return x;
	}
	void insert(int k,char now)
	{
		if(now==D)now=0;
		if(Q[now]>=t[k].p[now])
		{
			if(t[k].rc)
				insert(t[k].rc,now+1);
			else 
			{
				t[k].rc=tm++;t[t[k].rc].p=Q;
				init(t[k].rc);
			}
		}
		else 
		{
			if(t[k].lc)
				insert(t[k].lc,now+1);
			else 
			{
				t[k].lc=tm++;t[t[k].lc].p=Q;
				init(t[k].lc);
			}
		}
		update(k);
	}
	void query(int k,char now)
	{
		if(now==D)now=0;
		bool tag=1;
		for(int i=0;i<D;i++)
			if(q1.d[i]>t[k].l[i]||q2.d[i]<t[k].r[i])
				tag=0;
	 	if(tag){ans+=t[k].sum;return;}
		tag=1;
		for(int i=0;i<D;i++)
			if(q1.d[i]>t[k].p.d[i]||q2.d[i]<t[k].p.d[i])
				tag=0;
		if(tag)ans+=t[k].p.val;
		tag=1;
		for(int i=0;i<D;i++)
			if(now==i)
			{
				if(q1.d[i]>t[k].p.d[i]||q2.d[i]<t[k].l[i])tag=0;
			}
			else
			{
				if(q1.d[i]>t[k].r[i]||q2.d[i]<t[k].l[i])tag=0;
			}
		if(tag&&t[k].lc)query(t[k].lc,now+1);
		tag=1;
		for(int i=0;i<D;i++)
			if(now==i)
			{
				if(q1.d[i]>t[k].r[i]||q2.d[i]<t[k].p.d[i])tag=0;
			}
			else
			{
				if(q1.d[i]>t[k].r[i]||q2.d[i]<t[k].l[i])tag=0;
			}
		if(tag&&t[k].rc)query(t[k].rc,now+1);
	}
	inline void build(point *p,int n){P=p;build(0,n-1,0);}
	inline int query(point a,point b){ans=0;q1=a,q2=b;query(1,0);return ans;}
	inline void insert(point p){Q=p;insert(1,0);}
}

kd::point pp[200000];

int main()
{
	int cx,n=0,opt;
	kd::point a,b;
	scanf("%d%*d",&cx);
	while(1)
	{
		scanf("%d",&opt);
		if(opt==1)
		{
			scanf("%d%d%d",&pp[n].d[0],&pp[n].d[1],&pp[n].val);
			kd::insert(pp[n++]);
		}
		else if(opt==2)
		{
			scanf("%d%d%d%d",&a.d[0],&a.d[1],&b.d[0],&b.d[1]);
			printf("%d\n",kd::query(a,b)+cx*(a.d[1]-a.d[0]+1)*(b.d[1]-b.d[0]+1));
		}
		else return 0;
		if(n>0&&n%10000==0)kd::tm=1,kd::build(pp,n);
	}
}
```
过不了就适当调参

[1]: http://www.lydsy.com/JudgeOnline/problem.php?id=1176
  [2]: http://www.lydsy.com/JudgeOnline/problem.php?id=2683
  [3]: http://www.lydsy.com/JudgeOnline/problem.php?id=4066

]]>