XOR Queries

时间限制: 1000ms   内存限制: 256M

描述

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

输入

输入第一行为一个整数T，表示一共有T组测试数据。

对于每组测试数据：

第一行为两个整数n，m（1≤n,m≤50000）。

第二行为n个整数表示数组C（0≤C[i]≤109）。

接下来m行中，第i行有四个整数Li，Ri，Ai，Bi（1≤Li≤Ri≤n, 0≤Ai,Bi≤109）。

输出

对于每次询问：输出一个整数表示满足条件的数组下标数目。

样例输入1 

15 21 2 3 4 51 3 1 12 5 2 3

样例输出1

22 分析：区间问题很容易想到莫队； 　　　然后有了区间内所有数，怎么查x^a>=b； 　　　考虑异或，建01字典树插入删除查询即可； 代码：

#include 
       
        using namespace std;const int maxn=5e4+10;int n,m,k,t,a[maxn],bel[maxn],tot,cnt,ans[maxn],ch[maxn*31][2],sz[maxn*31],num;long long ret;struct node{    int l,r,id,block,c,d;    bool operator<(const node&p)const    {        return block==p.block?r
        
         
          =0;i--)    {        int y=(x>>i&1);        if(ch[pos][y]==0)        {            ch[pos][y]=++num;            ch[num][0]=ch[num][1]=0;            sz[ch[pos][y]]=0;        }        sz[ch[pos][y]]++;        pos=ch[pos][y];    }}void del(int x){    int pos=0;    for(int i=30;i>=0;i--)    {        int y=(x>>i&1);        sz[ch[pos][y]]--;        pos=ch[pos][y];    }}int query(int x,int y){    int ret=0,pos=0;    for(int i=30;i>=0;i--)    {        int z=(x>>i&1),w=(y>>i&1);        if(w==1)        {            pos=ch[pos][z^1];            if(i==0)ret+=sz[pos];        }        else ret+=sz[ch[pos][z^1]],pos=ch[pos][z];        if(pos==0)break;    }    return ret;}int main(){    int i,j;    scanf("%d",&t);    while(t--)    {        cnt=0;        num=0;        sz[0]=0;        tot=0;        ch[0][0]=ch[0][1]=0;        scanf("%d%d",&n,&m);        int sz=(int)sqrt(n);        for(i=1;i<=n;i++)        {            bel[i]=tot;            if(++cnt==sz)tot++,cnt=0;        }        for(i=1;i<=n;i++)scanf("%d",&a[i]);        for(i=1;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+1,qu+m+1);        int l=1,r=0;        for(i=1;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=1;i<=m;i++)printf("%d\n",ans[i]);    }    return 0;}