看到限制条件就想到右边不确定是没法做的,所以考虑把所有岛屿分成两类分类讨论。对于第一类岛屿(集合),满足。第二类岛屿(集合)满足。先考虑如何解决不带限制的询问如何解决。
对于集合中的岛屿,就是要求有多少个岛屿满足。我们可以把所有都丢进一个树里面,然后开始在上DFS。我们可以按照类似于数位的方法。如果这一位之后小于,就加上他子树内的个数(后面无论咋填一定满足限制)。如果这一位之后等于,我们就递归进去解决。这样搞一次复杂度是的。
对于集合中的岛屿,就是要求有多少个岛屿满足。我们发现很小,所以可以用和上面类似的方法来做。我们在空的一棵字典树上一次插入二元组。具体规则就是,如果这一位之后小于,就给这个目前位置的点打上一个标记,代表这个子树里面的所有,都能满足。如果如果这一位之后等于,递归解决。这上面所说的在初始化时解决即可。然后每次查询的时候遍历祖先统计祖先标记和即可。查询一次复杂度也是的。
然后我们发现,因为对于不同询问是会变的。所以我们只需要把排序,然后每次在询问前把一些集合的点挪到集合即可。初始化及移动的复杂度都是的。
最后来考虑如何来解决带的区间询问。可以直接使用线段树分治。把每个询问拆成个区间,每次进入一个区间时所有点都在区间。因为线段树所有区间长度和为,所以复杂度是。
细节有点多
/*
_|_| _| _| _|
_| _| _| _|_| _|_|_|_| _| _| _|
_| _| _|_| _| _| _|_|
_| _| _| _| _| _| _| _|
_|_| _| _|_|_|_| _|_| _| _|
*/
#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;
}