给出一个长度为n的数组C，回答m个形式为(L,R,A,B)的询问，含义为存在多少个不同的数组下标k∈[L,R]满足C[k]⨁A≥B（式中⨁为异或运算）。

#include <bits/stdc++.h>

using namespace std;

const int maxn=5e4+;

int n,m,k,t,a[maxn],bel[maxn],tot,cnt,ans[maxn],ch[maxn*][],sz[maxn*],num;

long long ret;

struct node

{

    int l,r,id,block,c,d;

    bool operator<(const node&p)const

    {

        return block==p.block?r<p.r:block<p.block;

    }

}qu[maxn];

void insert(int x)

{

    int pos=;

    for(int i=;i>=;i--)

    {

        int y=(x>>i&);

        if(ch[pos][y]==)

        {

            ch[pos][y]=++num;

            ch[num][]=ch[num][]=;

            sz[ch[pos][y]]=;

        }

        sz[ch[pos][y]]++;

        pos=ch[pos][y];

    }

}

void del(int x)

{

    int pos=;

    for(int i=;i>=;i--)

    {

        int y=(x>>i&);

        sz[ch[pos][y]]--;

        pos=ch[pos][y];

    }

}

int query(int x,int y)

{

    int ret=,pos=;

    for(int i=;i>=;i--)

    {

        int z=(x>>i&),w=(y>>i&);

        if(w==)

        {

            pos=ch[pos][z^];

            if(i==)ret+=sz[pos];

        }

        else ret+=sz[ch[pos][z^]],pos=ch[pos][z];

        if(pos==)break;

    }

    return ret;

}

int main()

{

    int i,j;

    scanf("%d",&t);

    while(t--)

    {

        cnt=;

        num=;

        sz[]=;

        tot=;

        ch[][]=ch[][]=;

        scanf("%d%d",&n,&m);

        int sz=(int)sqrt(n);

        for(i=;i<=n;i++)

        {

            bel[i]=tot;

            if(++cnt==sz)tot++,cnt=;

        }

        for(i=;i<=n;i++)scanf("%d",&a[i]);

        for(i=;i<=m;i++)scanf("%d%d%d%d",&qu[i].l,&qu[i].r,&qu[i].c,&qu[i].d),qu[i].id=i,qu[i].block=bel[qu[i].l];

        sort(qu+,qu+m+);

        int l=,r=;

        for(i=;i<=m;i++)

        {

            while(r < qu[i].r)

            {

                insert(a[++r]);

            }

            while(l > qu[i].l)

            {

                insert(a[--l]);

            }

            while(r > qu[i].r)

            {

                del(a[r--]);

            }

            while(l < qu[i].l)

            {

                del(a[l++]);

            }

            ans[qu[i].id]=query(qu[i].c,qu[i].d);

        }

        for(i=;i<=m;i++)printf("%d\n",ans[i]);

    }

    return ;

}