acdream1197 Points In Cuboid

题目链接：http://acdream.info/problem?pid=1197

题意：给出一些点。每次给出一个长方体，问在长方体中的点的个数。

思路：kd-tree。

const int N=111111;
struct node
{
int x[3];
int L,R;
};
node a[N];
int root,n,m;
void insert(int u,int k,int d)
{
d%=3;
if(a[k].x[d]<a[u].x[d])
{
if(a[u].L==-1) a[u].L=k;
else insert(a[u].L,k,d+1);
}
else
{
if(a[u].R==-1) a[u].R=k;
else insert(a[u].R,k,d+1);
}
}
int p[3],q[3],ans;
void cal(int u,int d)
{
if(u==-1) return;
int i;
for(i=0;i<3;i++) if(a[u].x[i]<p[i]||a[u].x[i]>q[i]) break;
if(i==3) ans++;
d%=3;
if(a[u].x[d]>=p[d]) cal(a[u].L,d+1);
if(a[u].x[d]<=q[d]) cal(a[u].R,d+1);
}
void deal()
{
int i;
for(i=1;i<=n;i++)
{
a[i].L=a[i].R=-1;
scanf("%d%d%d",&a[i].x[0],&a[i].x[1],&a[i].x[2]);
if(i==1) root=i;
else insert(root,i,0);
}
m=getInt();
while(m--)
{
for(i=0;i<3;i++) scanf("%d",&p[i]);
for(i=0;i<3;i++)
{
scanf("%d",&q[i]);
if(p[i]>q[i]) swap(p[i],q[i]);
}
ans=0;
cal(root,0);
printf("%dn",ans);
}
}
int main()
{
int num=0;
while(scanf("%d",&n)!=-1)
{
printf("Case #%d:n",++num);
deal();
}
}