外层维护权值线段树，内层维护kd-tree。

修改的时候只往右儿子里插入，不平衡的时候替罪羊式重构。

查询的时候在外层线段树上走，在内层kd-tree上查询矩形内点数即可。

时间复杂度$O(q\log v(\log^2q+\sqrt{q}))$。

 

#include
     
      #include
      
       #include
       
        using namespace std;const double A=0.8;const int N=100010,M=1600010;inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}int n,ans,cmp_d,op,X1,Y1,X2,Y2,k;int tmp[N],deep,need[N],cnt,cur;int T[M],l[M],r[M],tot=1;struct node{int d[2],l,r,Max[2],Min[2],size;}t[M];inline bool cmp(int a,int b){return t[a].d[cmp_d]
        
         b)a=b;}inline void up(int x){  t[x].size=1+t[t[x].l].size+t[t[x].r].size;  if(t[x].l){    umax(t[x].Max[0],t[t[x].l].Max[0]);    umin(t[x].Min[0],t[t[x].l].Min[0]);    umax(t[x].Max[1],t[t[x].l].Max[1]);    umin(t[x].Min[1],t[t[x].l].Min[1]);  }  if(t[x].r){    umax(t[x].Max[0],t[t[x].r].Max[0]);    umin(t[x].Min[0],t[t[x].r].Min[0]);    umax(t[x].Max[1],t[t[x].r].Max[1]);    umin(t[x].Min[1],t[t[x].r].Min[1]);  }}int build(int l,int r,int D){  int mid=(l+r)>>1;  cmp_d=D;  nth_element(need+l+1,need+mid+1,need+r+1,cmp);  int x=need[mid];  t[x].Max[0]=t[x].Min[0]=t[x].d[0];  t[x].Max[1]=t[x].Min[1]=t[x].d[1];  if(l!=mid)t[x].l=build(l,mid-1,!D);else t[x].l=0;  if(r!=mid)t[x].r=build(mid+1,r,!D);else t[x].r=0;  up(x);  return x;}void dfs(int x){if(x)need[++cnt]=x,dfs(t[x].l),dfs(t[x].r);}inline void ins(int&root,int now){  if(!root){root=now;return;}  for(int D=deep=0,x=root;;D^=1){    tmp[++deep]=x;    umax(t[x].Max[0],t[now].Max[0]);    umax(t[x].Max[1],t[now].Max[1]);    umin(t[x].Min[0],t[now].Min[0]);    umin(t[x].Min[1],t[now].Min[1]);    t[x].size++;    if(t[now].d[D]>=t[x].d[D]){      if(!t[x].r){t[x].r=now;break;}else x=t[x].r;    }else{      if(!t[x].l){t[x].l=now;break;}else x=t[x].l;    }  }  tmp[++deep]=now;  if(deep
         
          X2||t[x].Max[1]
          
           Y2||ans>=k)return; if(t[x].Min[0]>=X1&&t[x].Max[0]<=X2&&t[x].Min[1]>=Y1&&t[x].Max[1]<=Y2){ans+=t[x].size;return;} if(t[x].d[0]>=X1&&t[x].d[0]<=X2&&t[x].d[1]>=Y1&&t[x].d[1]<=Y2)ans++; ask(t[x].l);ask(t[x].r);}inline void add(){ int x=1,a=1,b=1000000000,mid,flag=1; while(1){ if(flag){ cur++; t[cur].Max[0]=t[cur].Min[0]=t[cur].d[0]=X1; t[cur].Max[1]=t[cur].Min[1]=t[cur].d[1]=Y1; t[cur].size=1; ins(T[x],cur); } if(a==b)return; mid=(a+b)>>1; if(k<=mid){ if(!l[x])l[x]=++tot; x=l[x],b=mid,flag=0; }else{ if(!r[x])r[x]=++tot; x=r[x],a=mid+1,flag=1; } }}inline void query(){ ans=0,ask(T[1]); if(ans
           
            >1; ans=0,ask(T[r[x]]); if(ans>=k)x=r[x],a=mid+1;else k-=ans,x=l[x],b=mid; } printf("%d\n",ans=a);}int main(){ read(n),read(n); while(n--){ read(op),read(X1),read(Y1);X1^=ans,Y1^=ans; if(op==1){ read(k);k^=ans; add(); }else{ read(X2),read(Y2),read(k);X2^=ans;Y2^=ans;k^=ans; query(); } } return 0;}