求助这么写为什么不对
查看原帖
求助这么写为什么不对
280999
_fairytale_楼主2024/1/21 21:25

RT,用的 01trie,query 函数和题解实现的不一样,查询的是有多少个数异或上 num>=knum>=k,但是 WA on #6,求大佬帮忙看看。

#include<bits/stdc++.h>
#define re register
#define il inline
#define ll long long
//define int long long
#define pii pair<int,int>
#define ls ((p)<<1)
#define rs (((p)<<1)|1)
#define mid ((l+r)>>1)
#define lowbit(x) ((x)&(-(x)))
#define printc cerr<<"-------------------------\n"
#define yon(x) (x?cout<<"Yes\n":cout<<"No\n")
#define YoN(x) (x?cout<<"YES\n":cout<<"NO\n")
#define rep(x,a,b) for(re int (x)=(a);(x)<=(b);++(x))
#define per(x,a,b) for(re int (x)=(a);(x)>=(b);--(x))
#define dbg(x) cerr<<#x<<":"<<x<<" "
#define cend cerr<<'\n'
#define fsp(x) fixed<<setprecision(x)
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define inf 0x3f3f3f3f
#define maxn 1001010
#define mod 0
constexpr int D=30;
int n,k;
int a[maxn],pre[maxn];
int tot=1;
struct trie{
	struct tree{
		int son[2];
		int cnt;
	}t[maxn<<5];
	void insert(int num){
		int now=1;
		per(i,D,0){
			int bit=(num>>i)&1;
			if(!t[now].son[bit])t[now].son[bit]=++tot;
			now=t[now].son[bit];
			++t[now].cnt;
		}
	}
	int query(int num){
		int now=1,res=0;
		per(i,D,0){
			int bit=(num>>i)&1;
			if((num|(1<<i))<k)return res;
			res+=t[t[now].son[bit^1]].cnt;
			num^=(bit<<i);
			now=t[now].son[bit];
		}
		return res;
	}
}T;
ll ans;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
    cin>>n>>k;
	T.insert(0);
	rep(i,1,n){
		cin>>a[i];
		pre[i]=pre[i-1]^a[i];
		T.insert(pre[i]);
		ans+=T.query(pre[i]);
	}
	cout<<ans;
	return 0;
}
/*
input:

output:


*/





2024/1/21 21:25
加载中...