崂山白花蛇草水 权值线段树套KDtree

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define setIO(s) freopen(s".in","r",stdin) //,freopen(s".out","w",stdout) 
struct Data
{
	int ch[2],w,minv[2],maxv[2],p[2],siz,sum;  
}node[20000000], arr[20000000]; 
namespace KDtree
{
	#define maxn 20000000
	#define Min(a,b) (a = a>b?b:a) 
	#define Max(a,b) (a = b>a?b:a) 
	int d,c_arr;    
	std::queue<int>Q; 
	void Init()
	{
		for(int i=1;i<maxn;++i) Q.push(i);                
	} 
    int newnode(){ int q = Q.front(); Q.pop(); return q; }
	bool cmp(Data i,Data j)
	{      
		return i.p[d]==j.p[d]?i.p[d^1]<j.p[d^1]:i.p[d]<j.p[d]; 
	}
	bool isout(int k,int x1,int y1,int x2,int y2)
	{
		if(node[k].maxv[0]<x1||node[k].minv[0]>x2||node[k].maxv[1]<y1||node[k].minv[1]>y2) return 1; 
		return 0; 
	}
	bool isin(int k,int x1,int y1,int x2,int y2)
	{
		if(node[k].maxv[0]<=x2 && node[k].minv[0]>=x1&&node[k].maxv[1]<=y2&&node[k].minv[1]>=y1) return 1; 
		return 0; 
	}
	void pushup(int x,Data p)
	{
		node[x].sum+=p.sum;
		node[x].siz+=p.siz; 
		Min(node[x].minv[0],p.minv[0]); 
		Min(node[x].minv[1],p.minv[1]); 
		Max(node[x].maxv[0],p.maxv[0]); 
		Max(node[x].maxv[1],p.maxv[1]); 
	}
	int query(int x,int x1,int y1,int x2,int y2)
	{
		if(!x||isout(x,x1,y1,x2,y2)) return 0; 
		if(isin(x,x1,y1,x2,y2))  
        {
            return node[x].sum; 
        }
		int ans=0; 
		if(node[x].p[0]>=x1&&node[x].p[0]<=x2&&node[x].p[1]>=y1&&node[x].p[1]<=y2) ans=1; 
		ans += query(node[x].ch[0],x1,y1,x2,y2)+query(node[x].ch[1],x1,y1,x2,y2); 
		return ans; 
	} 
	void dfs(int &o)
	{
		if(!o) return; 
		dfs(node[o].ch[0]);
		arr[++c_arr] = node[o];
		arr[c_arr].sum=arr[c_arr].w=1; 
		arr[c_arr].maxv[0]=arr[c_arr].minv[0]=arr[c_arr].p[0]; 
		arr[c_arr].maxv[1]=arr[c_arr].minv[1]=arr[c_arr].p[1]; 
		arr[c_arr].siz=1;      
		Q.push(o);
		dfs(node[o].ch[1]); 
		o=0; 
	}   
	void rebuild(int &x,int l,int r,int o)
	{
		int mid=(l+r)>>1; 
		d=o,std::nth_element(arr+l,arr+mid,arr+1+r,cmp); 
		x=newnode(); 
		node[x]=arr[mid]; 
		node[x].minv[0]=node[x].maxv[0]=node[x].p[0]; 
		node[x].minv[1]=node[x].maxv[1]=node[x].p[1]; 
		node[x].sum=node[x].w=1;  
		node[x].ch[0]=node[x].ch[1]=0;
		node[x].siz=1; 
		if(l<mid) rebuild(node[x].ch[0],l,mid-1,o^1), pushup(x, node[node[x].ch[0]]); 
		if(r>mid) rebuild(node[x].ch[1],mid+1,r,o^1), pushup(x, node[node[x].ch[1]]); 
	} 
	void Reconstruct(int &u)
	{
		c_arr=0; 
		dfs(u); 
		rebuild(u,1,c_arr,d=0);       
	} 
	bool check(int son,int x)
	{ 
		if(son*10>x*9) return true; 
		return false; 
	}
	void insert(int &x,Data a,int de,int tag)
	{
		if(!x)
		{
			x=newnode(); 
			node[x].p[0]=node[x].maxv[0]=node[x].minv[0]=a.p[0]; 
			node[x].p[1]=node[x].maxv[1]=node[x].minv[1]=a.p[1]; 
			node[x].sum=node[x].w=1;
			node[x].siz=1,node[x].ch[0]=node[x].ch[1]=0; 
			return; 
		}
		d = de;
		int is=0;          
		if(cmp(a,node[x]) == 1)          
		{                    
			is = check(node[node[x].ch[0]].siz+1,node[x].siz+1);
			insert(node[x].ch[0],a,de^1,is||tag);
			pushup(x,a); 
		}
		//a is bigger (rson) 
		else 
		{
			is = check(node[node[x].ch[1]].siz+1,node[x].siz+1);
			insert(node[x].ch[1],a,de^1,is||tag);
			pushup(x,a); 
		}      
	if(tag && is) Reconstruct(x);   
	}
};       
#define y1 opopopop 
int lson[2000000],rson[2000000],rt[2000000]; 
int x1,y1,x2,y2, tot=0,root=0;  
void modify(int &x,int l,int r,int k,Data i)
{   
	if(!x) x = ++tot;           
	KDtree::insert(rt[x],i,0,0);                  
	if(l==r) return;         
	int mid = (l+r)>>1; 
	if(k <= mid) modify(lson[x],l,mid,k,i); 
	else modify(rson[x],mid+1,r,k,i); 
}        
int query(int x,int l,int r,int kth)
{              
	if(l==r) return l; 
	int u = KDtree::query(rt[rson[x]],x1,y1,x2,y2);                     
	int mid = (l + r) >> 1;             
	if(u < kth) 
	    return query(lson[x],l,mid,kth-u);  
	else 
	    return query(rson[x],mid+1,r,kth);  
}
int Query(int kth)
{    
	return query(root,0,1000000000,kth);      
}
int n,q,lastans=0; 
int main()
{
 	// setIO("input"); 
	KDtree::Init();  
	scanf("%d%d",&n,&q);            
	for(int cc=1;cc<=q;++cc)   
	{
		int opt,a,b,c,d; 
		scanf("%d",&opt); 
		if(opt==1)
		{    
			scanf("%d%d%d",&a,&b,&c);     
            a^=lastans,b^=lastans,c^=lastans; 
			Data f; 
			f.p[0]=f.maxv[0]=f.minv[0]=a;
			f.p[1]=f.maxv[1]=f.minv[1]=b; 
			f.ch[0]=f.ch[1]=0; 
			f.siz=1;    
			f.sum=f.w=1;                 
			modify(root,0,1000000000,c,f);   
		}
		if(opt==2)
		{
			scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&a); 
		    x1^=lastans,y1^=lastans,x2^=lastans,y2^=lastans,a^=lastans;             
			lastans = Query(a); 
			if(lastans==0)   
			    printf("NAIVE!ORZzyz.\n");   
			else  
			    printf("%d\n",lastans); 
		}
	}
	return 0; 
}