一個th的題（a gensokyo）
難度系數在該知識點下為$2.1$
區間xor我們很明顯會想到trie樹，將每一個區間$l~r$異或和拆成$sum[l-1]$ $sum[r]$兩個數的異或
注意到二進制的性質，比當前低的位即使都取1加起來都沒有這位選1答案高，所以考慮貪心
題目中每次查詢的范圍都被限定在一個區間，所以考慮弄出了“$1~r$范圍中所有前綴異或和的trie”后怎么搞
考慮每一位，當這一位的某一個兒子在$s[r]$與當前trie節點xor為1，就設這個兒子為”大兒子”，否則是“小兒子”，分別記為$a$,$b$
記$ed[x]$表示在插入以后，$x$這個節點代表的數出現個數，$siz[x]$表示$x$節點子樹的所有節點$ed$值的和
根據異或的性質，如果$k$在當前考慮的這一位值為0，那么就將答案加上$sz[b]$（因為b所有子樹代表值都比$k$大），然后考慮下一位
否則，不累加答案，考慮下一位
當位數超出限制，返回當前節點$ed$值，當現在樹為空，返回$0$
于是本題成功解決
#include<bits/stdc++.h> using namespace std; #define N 100010 typedef unsigned int ui; ui n,k,a[N],ct,nc,sz[N<<6],tw[N],s[N]; int c[N<<6][2],d[N][35],rt[N],qq; void ins(int p,int &o,int x,int t){if(!o)o=++nc;sz[o]=sz[p]+1;if(x>32)return;c[o][!d[t][x]]=c[p][!d[t][x]];ins(c[p][d[t][x]],c[o][d[t][x]],x+1,t); } ui q(int o,int k,int x,int t){if(x>32||!o)return sz[o];int a=c[o][d[t][x]],b=c[o][!d[t][x]],p=k&tw[32-x];if(!p)return q(a,k,x+1,t)+sz[b];return q(b,k,x+1,t); } int main(){freopen("food.in","r",stdin);freopen("food.out","w",stdout);scanf("%u",&n);tw[0]=1;for(int i=1;i<=32;i++)tw[i]=tw[i-1]*2ll;for(int i=1;i<=n;i++){scanf("%u",&a[i]);s[i]=s[i-1]^a[i];}for(int i=1;i<=n;i++){ui x=s[i];ct=0;while(x){d[i][++ct]=x&1;x/=2;}reverse(d[i]+1,d[i]+33);ins(rt[i-1],rt[i],1,i-1);}scanf("%d",&qq);while(qq--){int r,k;scanf("%d%d",&r,&k);printf("%u\n",q(rt[r],k,1,r));} }
?
)
