BZOJ 4605 崂山白花蛇草水（权值线段树+KD树）

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=3000000,INF=1e9;
namespace KD_Tree{
struct Dot{
int d[2],mn[2],mx[2],l,r,sz;
Dot(){l=r=0;}
Dot(int x,int y){d[0]=x;d[1]=y;l=r=0;}
int& operator [] (int x){return d[x];}
};
int D,dcnt=0;
Dot T[N];
inline void umax(int&a,int b){if(a<b)a=b;}
inline void umin(int&a,int b){if(a>b)a=b;}
inline bool cmp(int x,int y){return T[x][D]<T[y][D];}
inline void up(int x){
T[x].sz=T[T[x].l].sz+T[T[x].r].sz+1;
T[x].mn[0]=T[x].mx[0]=T[x][0];
T[x].mn[1]=T[x].mx[1]=T[x][1];
if(T[x].l){
umax(T[x].mx[0],T[T[x].l].mx[0]);
umin(T[x].mn[0],T[T[x].l].mn[0]);
umax(T[x].mx[1],T[T[x].l].mx[1]);
umin(T[x].mn[1],T[T[x].l].mn[1]);
}
if(T[x].r){
umax(T[x].mx[0],T[T[x].r].mx[0]);
umin(T[x].mn[0],T[T[x].r].mn[0]);
umax(T[x].mx[1],T[T[x].r].mx[1]);
umin(T[x].mn[1],T[T[x].r].mn[1]);
}
}
inline int NewDot(int x,int y){
++dcnt;
T[dcnt][0]=x; T[dcnt][1]=y;
return up(dcnt),dcnt;
}
int query(int x,int x0,int y0,int x1,int y1){
if(!x||T[x].mn[0]>x1||T[x].mx[0]<x0||T[x].mn[1]>y1||T[x].mx[1]<y0)return 0;
if(T[x].mn[0]>=x0&&T[x].mx[0]<=x1&&T[x].mn[1]>=y0&&T[x].mx[1]<=y1)return T[x].sz;
int res=0;
if(T[x][0]>=x0&&T[x][0]<=x1&&T[x][1]>=y0&&T[x][1]<=y1)res++;
return res+query(T[x].l,x0,y0,x1,y1)+query(T[x].r,x0,y0,x1,y1);
}
int tot=0,pt[N];
int gt,gtd,gtf;
const double alp=0.8;
inline bool isbad(int x){
return max(T[T[x].l].sz,T[T[x].r].sz)>T[x].sz*alp+5;
}
void ins(int&x,int D,const Dot&p){
if(!x){x=NewDot(p.d[0],p.d[1]);return;}
if(p.d[D]<T[x][D])ins(T[x].l,D^1,p);
else ins(T[x].r,D^1,p);
up(x);
if(isbad(x))gt=x,gtd=D,gtf=0;
else if(gt==T[x].l||gt==T[x].r)gtf=x;
}
void treavel(int&x){
if(!x)return;
pt[++tot]=x;
treavel(T[x].l),treavel(T[x].r);
}
int build(int l,int r,int now){
if(l>r)return 0;
int mid=(l+r)>>1,x;
D=now;
nth_element(pt+l,pt+mid,pt+r+1,cmp);
x=pt[mid];
T[x].l=build(l,mid-1,now^1);
T[x].r=build(mid+1,r,now^1);
return up(x),x;
}
void Insert(int&x,const Dot&p){
gt=gtf=0,ins(x,0,p);
if(!gt)return;
tot=0,treavel(gt);
if(!gtf){x=build(1,tot,gtd);return;}
if(gt==T[gtf].l)T[gtf].l=build(1,tot,gtd);
else T[gtf].r=build(1,tot,gtd);
}
}
int tot=0;
struct data{int rt,l,r;}T[N];
void Insert(int &x,const KD_Tree::Dot&p,int val,int l=1,int r=INF){
if(!x)x=++tot;
KD_Tree::Insert(T[x].rt,p);
if(l==r)return;
int mid=(l+r)>>1;
if(val<=mid)Insert(T[x].l,p,val,l,mid);
else Insert(T[x].r,p,val,mid+1,r);
}
int query(int x,int x0,int y0,int x1,int y1,int k,int l=1,int r=INF){
if(l==r)return l;
int rcnt=KD_Tree::query(T[T[x].r].rt,x0,y0,x1,y1);
int mid=(l+r)>>1;
if(k<=rcnt)return query(T[x].r,x0,y0,x1,y1,k,mid+1,r);
return query(T[x].l,x0,y0,x1,y1,k-rcnt,l,mid);
}
int n,q,op,x0,y0,x1,y1,k,root=0,ans=0;
int main(){
scanf("%d%d",&n,&q);
while(q--){
scanf("%d",&op);
if(op==1){
scanf("%d%d%d",&x0,&y0,&k);
x0^=ans,y0^=ans,k^=ans;
KD_Tree::Dot p=KD_Tree::Dot(x0,y0);
Insert(root,p,k);
}else{
scanf("%d%d%d%d%d",&x0,&y0,&x1,&y1,&k);
x0^=ans,y0^=ans,x1^=ans,y1^=ans,k^=ans;
int res=KD_Tree::query(T[root].rt,x0,y0,x1,y1);
if(res<k)puts("NAIVE!ORZzyz."),ans=0;
else printf("%d\n",ans=query(root,x0,y0,x1,y1,k));
}
}return 0;
}