思路：

如果不考虑去重，一般都会想到可持久化字典树。

求的个数满足，很明显用字典树可以轻松的做到。求区间的内的个数的话加个可持久化，前个数组成第个版本的字典树，然后第个版本算出的值减去第个版本算出的值就是答案。

字典树求的个数满足的原理：

构建字典树时，每个节点存这个节点包含了多少个数。

搜索字典树时，假设当前访问到的第个二进制位，的这一位为。如果这一位为，字典树下一个节点的值如果是，那么得到的数一定是满足条件的，直接返回这个节点包含了多少数，然后继续访问值为的节点；如果这一位为，继续访问值为的节点。如果搜索到了字典树的叶子节点，那么直接返回这个节点包含了多少数。

考虑到一个节点内会包含多个相同的值，为了避免重复计数，不能直接记录这个节点包含了多少个数。处理区间内不同种类的数，套路一般是记录每个数的后缀，于是可以在构建字典树时，每个节点存经过这个节点的数的下标以及后缀。

搜索字典树时，假设当前节点中的数都满足，那么把询问插入这个节点中，该询问的后缀为其右端点，同时标记这条信息为询问。

遍历每个节点，按后缀从大到小取出存入的信息，如果该信息不是询问，用树状数组维护这条信息的下标，如果是询问，用树状数组查询有多少个下标在区间中。处理完一个节点后立马把树状数组情空。

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+7;
int pw[25],t[maxn*20][2],head[maxn],c[maxn],Next[maxn],ans[maxn],tot;
struct node{
    int l,r,x,id;
    bool operator<(const node& b)const{
        if(x!=b.x) return x>b.x;
        else if(id!=b.id) return id>b.id;
        else return l<b.l;
    }
};
vector<node>v[maxn*20];
int sum[maxn],n;
inline void add(int p,int v) {
    while(p<=n) {
        sum[p]+=v; p+=(p&-p);
    }
}
inline int query(int p) {
    int res(0);
    while(p) {
        res+=sum[p];    p-=(p&-p);
    }
    return res;
}
inline void ins(int x,int id) {
    int root(0);
    for(int i=18,p;~i;--i) {
        if(x&pw[i]) p=1;
        else p=0;
        if(!t[root][p]) t[root][p]=++tot;
        root=t[root][p];
        v[root].emplace_back(node{id,0,Next[id],0});
    }
}
void query(int l,int r,int x,int y,int id) {
    int root=0,v1,v2,p;
    for(int i=18;~i;--i) {
        v1=(x&pw[i])!=0,v2=(y&pw[i])!=0;
        if(v2) {
            if(t[root][v1]) v[t[root][v1]].emplace_back(node{l,r,r,id});
            root=t[root][v1^1];
            if(!root) return;
        }
        else {
            root=t[root][v1];
            if(!root) return;
        }
    }
    v[root].emplace_back(node{l,r,r,id});
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    pw[0]=1;
    for(int i=1;i<=18;++i) pw[i]=pw[i-1]*2;
    int Q,l,r,a,b;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>c[i];
    for(int i=n;i;--i) {
        if(!head[c[i]]) Next[i]=n+1;
        else Next[i]=head[c[i]];
        head[c[i]]=i;
        ins(c[i],i);
    }
    cin>>Q;
    for(int i=1;i<=Q;++i) {
        cin>>l>>r>>a>>b;
        query(l,r,a,b,i);
    }
    for(int i=1;i<=tot;++i) {
        sort(v[i].begin(),v[i].end());

        for(node x:v[i]) {
            if(!x.id) add(x.l,1);
            else ans[x.id]+=query(x.r)-query(x.l-1);
        }
        for(node x:v[i]) if(!x.id) add(x.l,-1);
    }
    for(int i=1;i<=Q;++i) printf("%d\n",ans[i]);
    return 0;
}