【题目分析】
刚开始想的是KD-Tree去暴力求解。
写了半天还没有暴力得的分数多（说好的nlogn呢）
直接按照四个维度排序。
然后扫一遍，用bitset去维护，然后对于四个维度小于一个询问的结果取一个交就可以了。
Bitset大法好。
【代码】
垃圾KD-Tree
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
#define maxn 500005
#define mlog 16
#define F(i,j,k) for (int i=j;i<=k;++i)
#define inf (1e18)
void Finout()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
#endif
}
struct node{double d[4],mn[4],mx[4];int siz,l,r;}t[maxn],now;
int n,q,D,rt,tot=0,m;
bool operator < (node x,node y){return x.d[D]<y.d[D];}
void update(int k)
{
F(i,0,3)
{
t[k].mx[i]=max(max(t[k].d[i],t[t[k].l].mx[i]),t[t[k].r].mx[i]);
t[k].mn[i]=min(min(t[k].d[i],t[t[k].l].mn[i]),t[t[k].r].mn[i]);
}
t[k].siz=t[t[k].l].siz+t[t[k].r].siz+1;
}
int build(int l,int r,int dir)
{
int mid=(l+r)/2;
D=dir;
nth_element(t+l,t+mid,t+r+1);
t[mid].siz=1;
F(i,0,3) t[mid].mx[i]=t[mid].mn[i]=t[mid].d[i];
t[mid].l=mid>l?build(l,mid-1,(dir+1)%4):0;
t[mid].r=mid<r?build(mid+1,r,(dir+1)%4):0;
update(mid);
return mid;
}
bool in(int o)
{
int flag=1;
F(i,0,3)
{
{
if (t[o].mx[i]>=0&&t[o].mx[i]<=now.d[i]);
else flag=0;
}
{
if (t[o].mn[i]>=0&&t[o].mn[i]<=now.d[i]);
else flag=0;
}
}
return flag;
}
void print(int o){
if (!o) return;
printf("%d t[o].mn[0]=%f t[o].mn[1]=%f t[o].mx[0]=%f t[o].mx[1]=%f l :%d r: %d
",o,t[o].mn[0],t[o].mn[1],t[o].mx[0],t[o].mx[1],t[o].l,t[o].r);
print(t[o].l);
print(t[o].r);
}
bool din(int o)
{
int flag=1;
F(i,0,3)
{
if (t[o].d[i]>=0&&t[o].d[i]<=now.d[i]);
else flag=0;
}
return flag;
}
bool out(int o)
{
int flag=1;
F(i,0,3)
{
if ((t[o].mx[i]>now.d[i]&&t[o].mn[i]>now.d[i])||(t[o].mx[i]<0&&t[o].mn[i]<0));
else flag=0;
}
return flag;
}
int query(int o)
{
if (!o) return 0;
if (in(o)){return t[o].siz;}
else
{
int ret=0;
if (din(o)) ret+=1;
if (t[o].l)
{
if (out(t[o].l)); else ret+=query(t[o].l);
}
if (t[o].r)
{
if (out(t[o].r)); else ret+=query(t[o].r);
}
return ret;
}
}
int main()
{
Finout();
F(i,0,3) t[0].mx[i]=inf,t[0].mn[i]=-inf;
scanf("%d",&m);n=1;
F(i,1,m)
{
int flag=1;
F(j,0,3)
{
scanf("%lf",&t[n].d[j]);
if (t[n].d[j]<0) flag=0;
}
if (flag) n++;
}
n--;
rt=build(1,n,1);
scanf("%d",&q);
F(i,1,q)
{
int flag=1;
F(j,0,3)
{
scanf("%lf",&now.d[j]);
if (now.d[j]<0) flag=0;
}
if (flag) printf("%d
",query(rt));
else printf("0
");
}
}
有趣的Bitset
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <bitset>
#include <string>
#include <algorithm>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
#define maxn 30010
#define F(i,j,k) for (int i=j;i<=k;++i)
int Getint()
{
int x=0,f=1; char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
bitset<maxn> b[maxn],now;
struct node{double d[4];int id;}a[maxn],q[maxn];
int n,m,D;
bool cmp(node x,node y){return x.d[D]<y.d[D];}
int main()
{
scanf("%d",&n);
F(i,1,n)
{
scanf("%lf%lf%lf%lf",&a[i].d[0],&a[i].d[1],&a[i].d[2],&a[i].d[3]);
a[i].id=i;
}
scanf("%d",&m);
F(i,1,m)
{
scanf("%lf%lf%lf%lf",&q[i].d[0],&q[i].d[1],&q[i].d[2],&q[i].d[3]);
q[i].id=i;
b[i].set();
}
F(i,0,3)
{
D=i;
sort(a+1,a+n+1,cmp);
sort(q+1,q+m+1,cmp);
now.reset();
int p=1;
F(j,1,m)
{
while (p<=n&&a[p].d[i]<=q[j].d[i]) now[a[p].id]=1,p++;
b[q[j].id]&=now;
}
}
F(i,1,m) printf("%d
",b[i].count());
}