[NOI Online 2021 提高组] 岛屿探险

看到限制条件$(a \oplus c)\leq min(b,d)$就想到右边不确定是没法做的，所以考虑把所有岛屿分成两类分类讨论。对于第一类岛屿（集合$A$），满足$b_i \leq d$。第二类岛屿（集合$B$）满足$b_i>d$。先考虑如何解决不带$l,r$限制的询问如何解决。

对于集合$B$中的岛屿，就是要求有多少个岛屿满足$(a_i \oplus c)\leq d$。我们可以把所有$a_i$都丢进一个$0/1\space trie$树里面，然后开始在$trie$上DFS。我们可以按照类似于数位$DP$的方法。如果这一位$\oplus c$之后小于$d$，就加上他子树内的$a_i$个数（后面无论咋填一定满足限制）。如果这一位$\oplus c$之后等于$d$，我们就递归进去解决。这样搞一次复杂度是$O(\log a_i)$的。

对于集合$A$中的岛屿，就是要求有多少个岛屿满足$(a_i \oplus c)\leq b_i$。我们发现$c$很小，所以可以用和上面类似的方法来做。我们在空的一棵字典树上一次插入二元组$(a_i,b_i)$。具体规则就是，如果这一位$\oplus c$之后小于$b_i$，就给这个$a_i$目前位置的点打上一个标记，代表这个子树里面的所有$c$，都能满足$(a_i \oplus c)\leq b_i$。如果如果这一位$\oplus c$之后等于$b_i$，递归解决。这上面所说的在初始化时解决即可。然后每次查询$c$的时候遍历祖先统计祖先标记和即可。查询一次复杂度也是$O(\log a_i)$的。

然后我们发现，因为对于不同询问$d$是会变的。所以我们只需要把$d$排序，然后每次在询问前把一些$B$集合的点挪到$A$集合即可。初始化及移动的复杂度都是$q\log a_i$的。

最后来考虑如何来解决带$l,r$的区间询问。可以直接使用线段树分治。把每个询问拆成$\log$个区间，每次进入一个区间时所有点都在$B$区间。因为线段树所有区间长度和为$n\log n$，所以复杂度是$n\log q\log a_i$。

细节有点多

/*
                                                  
  _|_|                              _|  _|    _|  
_|    _|  _|  _|_|  _|_|_|_|        _|  _|  _|    
_|    _|  _|_|          _|          _|  _|_|      
_|    _|  _|          _|      _|    _|  _|  _|    
  _|_|    _|        _|_|_|_|    _|_|    _|    _|  
                                                                                                    
*/ 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
#define ls (rt<<1)
#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=1e5+100;
pii ild[maxn];
struct trie{
	int ch[maxn*50][2],size[maxn*50],mk[maxn*50],cnt,stk[50];
	trie(){cnt=0;}
	void clear(){ch[0][0]=ch[0][1]=0;size[0]=mk[0]=0;cnt=0;}
	void insa(int a,int b){
		int x=0,top=0;stk[++top]=x;
		for(int i=24;i>=0;i--){
			int nxt;
			rep(tar,0,1){
				if(!ch[x][tar])ch[x][tar]=++cnt,ch[cnt][0]=ch[cnt][1]=size[cnt]=mk[cnt]=0;
				if(((a&(1<<i))^(tar<<i))<(b&(1<<i)))size[ch[x][tar]]++;
				if(((a&(1<<i))^(tar<<i))==(b&(1<<i)))nxt=ch[x][tar];
			}
			x=nxt;
		}
		size[x]++;
	}
	void dela(int a,int b){
		int x=0,top=0;stk[++top]=x;
		for(int i=24;i>=0;i--){
			int nxt;
			rep(tar,0,1){
				if(((a&(1<<i))^(tar<<i))<(b&(1<<i)))size[ch[x][tar]]--;
				if(((a&(1<<i))^(tar<<i))==(b&(1<<i))){
					nxt=ch[x][tar];
				}
			}
			x=nxt;
		}
		size[x]--;
	}
	void insb(int a){
		int x=0,top=0;stk[++top]=x;
		for(int i=24;i>=0;i--){
			int tar=(a&(1<<i))>>i;
			
			if(!ch[x][tar])ch[x][tar]=++cnt,ch[cnt][0]=ch[cnt][1]=size[cnt]=mk[cnt]=0;
			x=ch[x][tar];
			stk[++top]=x;
		}
		mk[x]++;
		while(top){int x=stk[top--];size[x]=mk[x];rep(i,0,1)if(ch[x][i])size[x]+=size[ch[x][i]];}
	}
	void delb(int a){
		int x=0,top=0;stk[++top]=x;
		for(int i=24;i>=0;i--){
			int tar=(a&(1<<i))>>i;
			x=ch[x][tar];
			stk[++top]=x;
		}
		mk[x]--;
		while(top){int x=stk[top--];size[x]=mk[x];rep(i,0,1)if(ch[x][i])size[x]+=size[ch[x][i]];}
	}
	int querya(int c){
		int x=0;int ans=0;
		for(int i=24;i>=0;i--){
			int tar=(c&(1<<i))>>i;
			if(!ch[x][tar])break;
			x=ch[x][tar];
			ans+=size[x];
		}
		return ans;
	}
	int queryb(int c,int d){
		int x=0;int ans=0;bool flag=0;
		for(int i=24;i>=0;i--){
			int nxt=-1;
			rep(tar,0,1){
				if(!ch[x][tar])continue;
				if(((c&(1<<i))^(tar<<i))<(d&(1<<i)))ans+=size[ch[x][tar]];
				if(((c&(1<<i))^(tar<<i))==(d&(1<<i)))nxt=ch[x][tar];
			}
			if(nxt==-1){flag=1;break;}
			x=nxt;
		}
		if(!flag)ans+=size[x];
		return ans;
	}
}ta,tb;
int out[maxn];
struct segment_tree{
	struct query{
		int c,d,idx;
	};
	struct island{
		int a,b;
	};
	vector<island>is;
	vector<query>q[maxn<<4];
	static bool cmp1(query a,query b){return a.d<b.d;}
	static bool cmp2(island x,island y){return x.b<y.b;}
	void ins(int l,int r,int rt,int tl,int tr,int c,int d,int num){
		if(tl<=l&&r<=tr){
			q[rt].pb((query){c,d,num});return;
		}
		int mid=(l+r)>>1;
		if(tl<=mid)ins(l,mid,ls,tl,tr,c,d,num);
		if(tr>=mid+1)ins(mid+1,r,rs,tl,tr,c,d,num);
	}
	void solve(int l,int r,int rt){
		ta.clear();tb.clear();
		sort(q[rt].begin(),q[rt].end(),cmp1);is.clear();
		rep(i,l,r){
			is.pb((island){ild[i].fi,ild[i].se});
			tb.insb(ild[i].fi);
		}
		sort(is.begin(),is.end(),cmp2);
		int aline=-1;
		rep(i,0,(int)(q[rt].size())-1){
			int lim=q[rt][i].d,idx=q[rt][i].idx;
			while((aline+1)<(int)is.size()&&is[aline+1].b<=lim){
				ta.insa(is[aline+1].a,is[aline+1].b);
				tb.delb(is[aline+1].a);aline++;
			}
			out[idx]+=ta.querya(q[rt][i].c)+
			tb.queryb(q[rt][i].c,q[rt][i].d);
		}
		if(l==r)return;
		int mid=(l+r)>>1;
		solve(l,mid,ls);solve(mid+1,r,rs);
	}
}t;
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
    char ch=nc();int sum=0;
    while(!(ch>='0'&&ch<='9'))ch=nc();
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
    return sum;
}
int main(){
	int n=rd(),q=rd();
	rep(i,1,n){
		ild[i].fi=rd();ild[i].se=rd();
	}
	rep(i,1,q){
		int l=rd(),r=rd(),c=rd(),d=rd();
		t.ins(1,n,1,l,r,c,d,i);
	}
	t.solve(1,n,1);
	rep(i,1,q){
		printf("%d\n",out[i]);
	}
	return 0;
}