正题
题目链接:https://www.luogu.com.cn/problem/P7470
题目大意
给出(n)个二元组((a,b))。
(q)次询问给出((l,r,c,d))表示询问([l,r])中有多少二元组满足(c xor aleq min(b,d))。
(1leq n,qleq 10^5)
解题思路
这个(min)一看就很迷，显然是让我们分两种情况讨论。
再把询问拆一下，就变成了两个条件(posleq r/pos<l)且(bleq d/b>d)。
两个偏序条件的话直接上(CDQ)，然后考虑两种情况怎么处理。
- (c xor aleq b)：这样对于每个二元组合法的(c)开业被拆成(Trie)上最多(log)个区间，建(Trie)即可
- (c xor aleq d)：对于每组询问在(Trie)上跑区间求和即可。
时间复杂度(O(nlog^2 n))
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+10,M=N*24;
struct node{
int w,l,id;
}q[N<<1],a[N];
int n,m,tot,rt1,rt2,ans[N];
vector<node> v[N];
struct Trie1{
int cnt,ch[M][2],w[M];
void Clear(){rt1=0;cnt=0;return;}
int Newp(){++cnt;ch[cnt][0]=ch[cnt][1]=w[cnt]=0;return cnt;}
void Insert(int &x,int d,int l,int val){
if(!x)x=Newp();
if(d<0){w[x]++;return;}
int c=(val>>d)&1;
if((l>>d)&1){
Insert(ch[x][c^1],d-1,l,val);
if(!ch[x][c])ch[x][c]=Newp();
w[ch[x][c]]++;
}
else Insert(ch[x][c],d-1,l,val);
}
int Ask(int x,int d,int val){
if(!x)return 0;
if(d<0)
return w[x];
int c=(val>>d)&1;
return Ask(ch[x][c],d-1,val)+w[x];
}
}T1;
struct Trie2{
int cnt,ch[M][2],w[M];
void Clear(){rt2=0;cnt=0;return;}
int Newp(){++cnt;ch[cnt][0]=ch[cnt][1]=w[cnt]=0;return cnt;}
void Insert(int &x,int d,int val){
if(!x)x=Newp();
if(d<0){w[x]++;return;}
int c=(val>>d)&1;
Insert(ch[x][c],d-1,val);
w[x]=w[ch[x][0]]+w[ch[x][1]];
return;
}
int Ask(int x,int d,int l,int val){
if(d<0)return w[x];
int c=(val>>d)&1;
if((l>>d)&1)
return Ask(ch[x][c^1],d-1,l,val)+w[ch[x][c]];
return Ask(ch[x][c],d-1,l,val);
}
}T2;
bool cmp(node x,node y)
{return x.l<y.l;}
void CDQ(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
CDQ(l,mid);
CDQ(mid+1,r);
sort(a+l,a+mid+1,cmp);
T1.Clear();T2.Clear();tot=0;
for(int i=mid+1;i<=r;i++)
for(int j=0;j<v[i].size();j++)
q[++tot]=v[i][j];
sort(q+1,q+1+tot,cmp);
for(int i=1,z=l;i<=tot;i++){
while(z<=mid&&a[z].l<=q[i].l)
T1.Insert(rt1,23,a[z].l,a[z].w),z++;
if(q[i].id<0)ans[-q[i].id]-=T1.Ask(rt1,23,q[i].w);
else ans[q[i].id]+=T1.Ask(rt1,23,q[i].w);
}
for(int i=tot,z=mid;i>=1;i--){
while(z>=l&&a[z].l>q[i].l)
T2.Insert(rt2,23,a[z].w),z--;
if(q[i].id<0)ans[-q[i].id]-=T2.Ask(rt2,23,q[i].l,q[i].w);
else ans[q[i].id]+=T2.Ask(rt2,23,q[i].l,q[i].w);
}
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].w,&a[i].l);
for(int i=1;i<=m;i++){
int l,r,c,d;
scanf("%d%d%d%d",&l,&r,&c,&d);
v[l].push_back((node){c,d,-i});
v[r+1].push_back((node){c,d,i});
}
sort(q+1,q+1+n,cmp);
CDQ(1,n+1);
for(int i=1;i<=m;i++)
printf("%d
",ans[i]);
return 0;
}