Description
每个物品有 (a_i) 和 (b_i) 两个权，(Q) 次询问，给定 (c) 和 (d)，每次询问区间 ([l,r])，求 (sum_{i=l}^{r} [a_ioplus cleq min(b_i,d)])，(oplus) 表示异或。
Solution
首先想到的是将 (min) 拆开，分为 (dleq b_i) 和 (d>b_i) 的部分。
先考虑 (max{d_i}leq min{b_i}) 的部分分，那只需要求 (sum_{i=l}^{r} [a_ioplus cleq d])，这个可以建一个可持久 01-Trie 来实现，判断 (c) 和 (d) 的当前位，分类讨论 (a_i) 可能有哪些转移。也可以将询问离线，将询问拆成两个前缀作差，按右端点排序，就不用了可持久化了。
第二个是 (min{d_i}geq max{b_i})。也就是求 (sum_{i=l}^{r} [a_ioplus cleq b_i])，这次有两个变量，非常不好搞。但是我们观察原式，如果查询区间是全局的话，交换 ((a,b)) 和 ((c,d)) 是完全没有区别的，这是一个相当对称的式子。这就提示我们将询问和原序列交换，将询问当做序列，将序列当做询问，那么这就变成了第一种情况。唯一的区别是由于贡献永远是对询问做出的，所以这种情况应该是在 01-Trie 上打标记而不是询问。具体来说，首先将所有询问拆成两个前缀，按右端点排序。将所有的 (c) 插入 Trie。顺次枚举 ((a,b))，在 Trie 上加标记。对一个询问的贡献就是 (c) 的根缀上的标记和。
考虑合并上述两种情况，如何计算贡献和 (b) 和 (d) 的大小有关。考虑将询问和原序列合并，按 (b) 和 (d) 从小到大排序，然后 CDQ 分治。那么对于左边的询问和右边的原序列，就是第一种情况；对于右边的询问和左边的原序列就是第二种情况。分别维护两个 Tire 计算贡献即可。
复杂度 (O((n+q)log(n+q)log|V|))
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
inline ll read(){
ll x=0,flag=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-') flag=0;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
return flag? x:-x;
}
const int N=2e5+7;
struct Node{
ll x,y;
int q,l,r,id;
}a[N];
struct Trie{
int s[2],sz;
}t[N*23];
struct Que{
int pos,id,op;
bool operator <(const Que &X) const{
return pos<X.pos;
}
};
int ans[N],tot=0,rt[N],L,R,tag[N*23];
inline bool Cmp1(const Node &X,const Node &Y){return X.y<Y.y;}
inline bool Cmp2(const Node &X,const Node &Y){return X.id<Y.id;}
ll Val,P;
void ins(int &id,int pre,int k=23){
id=++tot;
t[id]=t[pre]; t[id].sz++;
int to=(Val>>k)&1;
if(~k) ins(t[id].s[to],t[pre].s[to],k-1);
}
void ins(){
int now=0;
for(int i=23;~i;i--){
int to=(Val>>i)&1;
if(!t[now].s[to])
t[now].s[to]=++tot;
now=t[now].s[to];
}
}
void Clear(int &id,int k=23){
tot--;
if(~k) Clear(t[id].s[(Val>>k)&1],k-1);
t[id]=(Trie){{0,0},0}; id=0;
}
void Clear2(int id){
if(t[id].s[0]) Clear2(t[id].s[0]);
if(t[id].s[1]) Clear2(t[id].s[1]);
t[id]=(Trie){{0,0},0};
tag[id]=0;
}
int query(int id,int k=23){
if(k==-1) return t[id].sz;
if(!id) return 0;
int x=(Val>>k)&1,y=(P>>k)&1;
if(y) return x? (query(t[id].s[0],k-1)+t[t[id].s[1]].sz):(query(t[id].s[1],k-1)+t[t[id].s[0]].sz);
else return x? query(t[id].s[1],k-1):query(t[id].s[0],k-1);
}
void modify(){
int now=0;
for(int i=23;~i;i--){
int x=(Val>>i)&1,y=(P>>i)&1;
if(y){
if(x){
if(t[now].s[1]) tag[t[now].s[1]]++;
if(!t[now].s[0]) return ;
else now=t[now].s[0];
}else{
if(t[now].s[0]) tag[t[now].s[0]]++;
if(!t[now].s[1]) return ;
else now=t[now].s[1];
}
}else{
if(x){
if(!t[now].s[1]) return ;
else now=t[now].s[1];
}else{
if(!t[now].s[0]) return ;
else now=t[now].s[0];
}
}
}
tag[now]++;
}
int query2(ll x){
int ret=0,now=0;
for(int i=23;~i;i--){
int to=(x>>i)&1;
now=t[now].s[to];
ret+=tag[now];
}
return ret;
}
void CDQ(int l,int r){
if(l==r) return ;
int mid=(l+r)>>1;
CDQ(l,mid),CDQ(mid+1,r);
vector<int> V; int ret=0;
sort(a+l,a+mid+1,Cmp2),sort(a+mid+1,a+r+1,Cmp2);
for(int i=mid+1;i<=r;i++)
if(!a[i].q) ++ret,Val=a[i].x,ins(rt[ret],rt[ret-1]),V.push_back(a[i].id);
for(int i=l;i<=mid;i++)
if(a[i].q){
L=lower_bound(V.begin(),V.end(),a[i].l)-V.begin()+1;
R=upper_bound(V.begin(),V.end(),a[i].r)-V.begin();
if(L>R) continue;
Val=a[i].x,P=a[i].y;
ans[a[i].id]+=query(rt[R])-query(rt[L-1]);
}
ret=0;
for(int i=mid+1;i<=r;i++)
if(!a[i].q) ++ret,Val=a[i].x,Clear(rt[ret]);
vector<Que> Q;
for(int i=mid+1;i<=r;i++)
if(a[i].q){
Val=a[i].x,ins();
Q.push_back((Que){a[i].r,i,1});
Q.push_back((Que){a[i].l-1,i,-1});
Val=a[i].x,ins();
}
sort(Q.begin(),Q.end());
int j=0;
for(int i=l;i<=mid;i++)
if(!a[i].q){
while(j<Q.size()&&Q[j].pos<a[i].id)
ans[a[Q[j].id].id]+=Q[j].op*query2(a[Q[j].id].x),j++;
Val=a[i].x,P=a[i].y,modify();
}
while(j<Q.size())
ans[a[Q[j].id].id]+=Q[j].op*query2(a[Q[j].id].x),j++;
Clear2(0),tot=0;
}
int main(){
int n=read(),q=read();
for(int i=1;i<=n;i++)
a[i].x=read(),a[i].y=read(),a[i].id=i;
for(int i=1;i<=q;i++)
a[n+i].l=read(),a[n+i].r=read(),
a[n+i].x=read(),a[n+i].y=read(),a[n+i].q=1,a[n+i].id=i;
sort(a+1,a+1+n+q,Cmp1),CDQ(1,n+q);
for(int i=1;i<=q;i++) printf("%d
",ans[i]);
}