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

  • A+
所属分类:未分类

E. Beautiful Subarrays(Trie维护前缀异或和)
思路:看题,不难知道要做前缀和.枚举 r r r,我们需要一种数据结构,得知前缀异或和中有多少 l < r , p r e r ⊕ p r e l − 1 > = k l<r,pre_r\oplus pre_{l-1}>=k l<r,prerprel1>=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} prerprel1 i i i位两个位置都可以取,取0就是继续往Trie树向下走,取1就是立马结算贡献.
当k第i位是1时,显然 p r e r ⊕ p r e l − 1 pre_r\oplus pre_{l-1} prerprel1只能取1。
式子中 p r e r ⊕ p r e l − 1 pre_r\oplus pre_{l-1} prerprel1, p r e r pre_r prer事实上是一个定值,根据需要的,取 p r e l − 1 pre_{l-1} prel1即可,而 p r e l − 1 pre_{l-1} prel1取值决定了怎么继续向Trie向下走.

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector<int> 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<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) a[i]^=a[i-1];
	ll ans = 0;
	for(int i=1;i<=n;i++){
   
		insert(a[i-1]);
		ans+=query(a[i],k);
	}
	cout<<ans;
}
/* 1 1 1 */
w3cjava

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: