E. Beautiful Subarrays(Trie维护前缀异或和)

思路:看题,不难知道要做前缀和.枚举 r r r,我们需要一种数据结构,得知前缀异或和中有多少 l < r , p r e r ⊕ p r e l − 1 > = k l=k l=k. 前缀异或和,这是一个01Trie树的经典运用.异或和相关的问题可以用Trie01树维护,具体思想就是把一个数字的二进制形式看成01的字符串,每个数字就转化成一个长度为30~60的01字符串. 在这题中,我们从高向低建树,当 k k k的第 i i i位是0时, p r e r ⊕ p r e l − 1 pre_r\oplus pre_{l-1} prer​⊕prel−1​第 i i i位两个位置都可以取,取0就是继续往Trie树向下走,取1就是立马结算贡献. 当k第i位是1时,显然 p r e r ⊕ p r e l − 1 pre_r\oplus pre_{l-1} prer​⊕prel−1​只能取1。 式子中 p r e r ⊕ p r e l − 1 pre_r\oplus pre_{l-1} prer​⊕prel−1​, p r e r pre_r prer​事实上是一个定值,根据需要的,取 p r e l − 1 pre_{l-1} prel−1​即可,而 p r e l − 1 pre_{l-1} prel−1​取值决定了怎么继续向Trie向下走.

#include
using namespace std;
const int maxn = 1000005;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector G[maxn];
//前向星
// for(int i=head[u];i!=-1;i=nxt[i]) v = to[i]
//int nxt[maxn],head[maxn],to[maxn];// head[u],cnt 初始值是-1
//int tot = -1;
//void add(int u,int v){
//	nxt[++tot] = head[u];
//	head[u] = tot;
//	to[tot] = v;
//}
int tr[maxn*30][2];int cnt[maxn*30];int idx = 1;
void insert(int x){
	int p = 1;
	for(int i=30;i>=0;i--){
		int c = (x>>i&1);
		if(!tr[p][c]) tr[p][c] = ++idx;
		p = tr[p][c];
		cnt[p]++;
	}
}
int query(int x,int k){
	int p = 1;// x is pre_r
	int res = 0;
	for(int i=30;i>=0;i--){
		int c = (x>>i&1);
		if(k>>i&1)  p = tr[p][c^1];//k是1,pre_r ^ pre_l=1,那么此时c取pre_r相反数字,且不能统计答案,因为还没有确定后续状态
		else res+=cnt[tr[p][c^1]],p =tr[p][c];
		//k是0,pre_r ^ pre_l可取0可取1,取0继续往下走,取1马上统计出pre_r^pre_l > 1的答案
	}
	//等于pre_r ^ pre_l == k的情况
	res +=cnt[p];
	return res;
}
int a[maxn];
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,k;
	cin>>n>>k;
	a[0] = 0;
	for(int i=1;i>a[i];
	for(int i=1;i