准备食物

食物"/>

准备食物

Description

给出一个序列，每次询问r,k表示所有的区间[i,r]中有多少个的异或和大于等于k。
n,q<=10^5

Solution

辣鸡出题人。（虽然我AC了，但是nq的暴力能过60分！）
拿衣服的我天真的认为异或是可以在不等式里瞎搞的。
然而。。。
于是看到这种位运算的题，trie树自然是首选。
这道题的r拍一个序就可以不用可持久化了。
然后，按照位运算每一位推下去就好了。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 100005
using namespace std;
struct note{int x,y,id;}ask[N];
bool cmp(note x,note y) {return x.x<y.x;}
int n,m,tot,a[N],an[N],trie[N*30][2],size[N*30];
void insert(int val) {int x=0;fd(i,29,0) {int t=(val&(1<<i))>0;if (!trie[x][t]) trie[x][t]=++tot;x=trie[x][t];size[x]++;}
}
int query(int val,int k) {int x=0,ans=0;fd(i,29,0) {int t=(val&(1<<i))>0,y=(k&(1<<i))>0;if (y) {x=trie[x][1-t];if (!x) break;} else {ans+=size[trie[x][1-t]];x=trie[x][t];if (!x) break;}}return ans+size[x];
}
int main() {freopen("food.in","r",stdin);freopen("food.out","w",stdout);scanf("%d",&n);fo(i,1,n) scanf("%d",&a[i]),a[i]^=a[i-1];scanf("%d",&m);fo(i,1,m) scanf("%d%d",&ask[i].x,&ask[i].y),ask[i].id=i;sort(ask+1,ask+m+1,cmp);insert(a[0]);int j=0;fo(i,1,m) {while (j<ask[i].x-1) insert(a[++j]);an[ask[i].id]=query(a[ask[i].x],ask[i].y);}fo(i,1,m) printf("%d\n",an[i]);
}