做法

目前复杂度为 $O(24(n+2q)\log n)$

代码：

#include<iostream>
#include<vector>
#include<algorithm>
#include<vector>
using namespace std;
int n,q,a[100005],jd1[200005],tree[8000005],lc[8000005],rc[8000005],rcnt,b[100005],w[100005],w2[100005],ans[100005],c[100005],d[100005],e[100005],g[100005];
struct tuples{
	int fth,sth,tth,foth,id;
}qryc[200005],dyz[100005];
vector<int> G[200005];
pair<int,int> qrym[200005],dyz2[100005];
pair<int,int> ts[100005];
struct node{
	int l,r,c,d,id;
}qrys[100005];
int cmp(node x,node y){
	return x.d<y.d;
}
tuples gf(int a,int b,int c,int d){
	tuples ret;
	ret.fth=a;ret.sth=b;ret.tth=c;ret.foth=d;
	return ret;
}
int kk(int x,int k){
	return (x>>(24-k));
}
int get(int x,int k){
	return (x>>(24-k))&1;
}
int cmp2(tuples x,tuples y){
	if(x.fth!=y.fth){
		return x.fth<y.fth;
	}
	if(x.sth!=y.sth){
		return x.sth<y.sth;
	}
	if(x.tth!=y.tth){
		return x.tth<y.tth;
	}
	if(x.foth!=y.foth){
		return x.foth<y.foth;
	}
	return 0;
}
int find(tuples x){
	int cur=lower_bound(qryc+1,qryc+2*q+1,x,cmp2)-qryc;
	//cout<<cur<<endl;
	if(qryc[cur].fth==x.fth&&qryc[cur].sth==x.sth&&qryc[cur].tth==x.tth&&qryc[cur].foth==x.foth){
		return cur; 
	}
	return -1;
}
void add(int p,int l,int r,int wz,int v){
	if(l==r){
		//cout<<"我真强！我修改了一个tree[p]的值！"<<endl;
		tree[p]+=v;
		return ;
	}
	int mid=(l+r)>>1;
	if(wz<=mid){
		if(!lc[p]){
			lc[p]=++rcnt;
		}
		add(lc[p],l,mid,wz,v);
	}
	else{
		if(!rc[p]){
			rc[p]=++rcnt;
		}
		add(rc[p],mid+1,r,wz,v);
	}
	tree[p]=tree[lc[p]]+tree[rc[p]];
}
int qry(int p,int l,int r,int pl,int pr){
	if(!p){
		return 0;
	}
	if(pl<=l&&r<=pr){
		return tree[p];
	}
	int mid=(l+r)>>1,ret=0;
	if(pl<=mid){
		ret+=qry(lc[p],l,mid,pl,pr);
	}
	if(mid<pr){
		ret+=qry(rc[p],mid+1,r,pl,pr);
	}
	return ret;
}
void ins(tuples x,int y){
	int k=find(x);
	if(k!=-1){
		if(!jd1[k]){
			jd1[k]=++rcnt;
		}
		//cout<<jd1[k]<<" "<<y<<endl;
		add(jd1[k],1,n,y,1);
	}
}
void xg(int x,tuples y,tuples z){
	int k=find(y);
	if(k!=-1){
		if(!jd1[k]){
			jd1[k]=++rcnt;
		}
		//cout<<jd1[k]<<" "<<x<<endl;
		add(jd1[k],1,n,x,-1);
	}
	ins(z,x);
}
int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		b[i]++;
		ts[i]={b[i],i};
	}
	for(int i=1;i<=q;i++){
		cin>>qrys[i].l>>qrys[i].r>>qrys[i].c>>qrys[i].d;
		qrys[i].d++;
		qrys[i].id=i;
	}
	sort(qrys+1,qrys+q+1,cmp);
	sort(ts+1,ts+n+1);
	for(int i=1;i<=24;i++){
		for(int j=1;j<=rcnt;j++){
			lc[j]=rc[j]=tree[j]=0;
		}
		rcnt=0;
		for(int j=1;j<=n;j++){
			c[j]=kk(a[j],i-1);
			d[j]=kk(b[j],i-1);
			e[j]=get(a[j],i);
			g[j]=get(b[j],i);
		}	
		for(int j=1;j<=q;j++){
			qryc[(j<<1)-1]=gf(kk(qrys[j].c,i-1),get(qrys[j].c,i),1,1);
			qryc[j<<1]=gf(kk(qrys[j].c,i-1)^kk(qrys[j].d,i-1),get(qrys[j].c,i),0,0);
		}
		sort(qryc+1,qryc+q*2+1,cmp2);
		for(int j=1;j<=q*2;j++){
			jd1[j]=0;
			G[j].clear();
		}
		for(int j=1;j<=n;j++){
			dyz[j]=gf(c[j],e[j],0,0);
			ins(dyz[j],j);
		}
		int r=1;
		for(int j=1;j<=q;j++){
			while(r<=n&&ts[r].first<=qrys[j].d){
				int ids=ts[r].second;
				xg(ids,dyz[ids],gf(c[ids]^d[ids],e[ids],g[ids],1));
				r++;
			}
			int k=find(gf(kk(qrys[j].c,i-1),get(qrys[j].c,i),1,1)),k2=find(gf(kk(qrys[j].c,i-1)^kk(qrys[j].d,i-1),get(qrys[j].c,i),0,0));
			if(k!=-1){
				ans[qrys[j].id]+=qry(jd1[k],1,n,qrys[j].l,qrys[j].r);
			}
			if(k2!=-1){
				if(get(qrys[j].d,i)){
					ans[qrys[j].id]+=qry(jd1[k2],1,n,qrys[j].l,qrys[j].r);
				}
			}
			//cout<<kk(qrys[j].c,i-1)<<" "<<k<<" "<<k2<<" JINGOUBIAO"<<endl;
		}
	}
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}

目前该做法开O2只有最基础的暴力分，求问是否能优化到AC。