解题:CQOI 2017 老C的任务

题面

找到真正的KD-Tree题目了!然而出题人并不打算放KD-Tree过,只能O2了

 // luogu-judger-enable-o2
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int cmp;
struct a
{
int pos[],val;
}mem[N],kdt[N];
bool operator < (a x,a y)
{
return x.pos[cmp]<y.pos[cmp];
}
struct b
{
int mn[],mx[];
}qry;
int son[N][],mini[N][],maxx[N][];
long long sum[N],ans;
int n,m,f,t1,t2,cnt;
void read(int &x)
{
x=f=; char ch=getchar();
while(!isdigit(ch))
f|=ch=='-',ch=getchar();
while(isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
x=f?-x:x;
}
void write(long long x)
{
if(x>) write(x/);
putchar(x%|);
}
bool Outof(int nde)
{
for(int i=;i<=;i++)
if(qry.mn[i]>maxx[nde][i]||qry.mx[i]<mini[nde][i])
return true; return false;
}
bool Allin(int nde)
{
for(int i=;i<=;i++)
if(qry.mn[i]>mini[nde][i]||qry.mx[i]<maxx[nde][i])
return false; return true;
}
bool Partin(a nde)
{
for(int i=;i<=;i++)
if(qry.mn[i]>nde.pos[i]||qry.mx[i]<nde.pos[i])
return false; return true;
}
void Pushup(int nde)
{
int lson=son[nde][],rson=son[nde][];
sum[nde]=sum[nde]+sum[lson]+sum[rson];
for(int i=;i<=;i++)
if(son[nde][i])
{
int sn=son[nde][i];
for(int j=;j<=;j++)
{
mini[nde][j]=min(mini[nde][j],mini[sn][j]);
maxx[nde][j]=max(maxx[nde][j],maxx[sn][j]);
}
}
}
void Create(int nde,int l,int r,int typ)
{
int mid=(l+r)/;
cmp=typ,nth_element(mem+l,mem+mid,mem+r+);
kdt[nde]=mem[mid],sum[nde]=mem[mid].val;
for(int i=;i<=;i++)
mini[nde][i]=maxx[nde][i]=mem[mid].pos[i];
if(l<mid) Create(son[nde][]=++cnt,l,mid-,typ^);
if(r>mid) Create(son[nde][]=++cnt,mid+,r,typ^);
Pushup(nde);
}
void Query(int nde)
{
if(Outof(nde)) return ;
if(Allin(nde)) {ans+=sum[nde]; return;}
if(Partin(kdt[nde])) ans+=kdt[nde].val;
Query(son[nde][]),Query(son[nde][]);
}
int main()
{
register int i;
read(n),read(m);
for(i=;i<=n;i++)
read(mem[i].pos[]),read(mem[i].pos[]),read(mem[i].val);
cnt=,Create(,,n,);
for(i=;i<=m;i++)
{
read(qry.mn[]),read(qry.mn[]);
read(qry.mx[]),read(qry.mx[]);
ans=,Query(),write(ans),puts("");
}
return ;
}
上一篇:html5 manifest 离线缓存知识点


下一篇:url编码模块