I am WRONG, where is WHY
查看原帖
I am WRONG, where is WHY
651786
yyc_楼主2023/4/30 17:05
/*YYC is Thinking Here*/
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f3f3f3f3f
#define clz __builtin_clz
#define lg(x) (31 - clz(x))
using namespace std;
const int maxn = 5e5+10,lim = lg(maxn)+1;
int n,k;
struct node{ int s[2],siz; }t[maxn];
int cnt,rt[maxn],a[maxn];
inline void insert(int *u,int x) {
	for(int i = lim-1;~i;--i) {
		t[++cnt] = t[*u], *u = cnt;
		++t[*u].siz;
		const int c = x >> i & 1;
		u = t[*u].s+c;
	}
	t[++cnt] = t[*u], *u = cnt;
	++t[*u].siz;
}
int get(int u,int x,int k) {
	int ans = 0;
	for(int i = lim-1;~i;--i) {
		ans <<= 1;
		const int c = x >> i & 1,less = t[u].s[!c][t].siz;
		if(less >= k) u = t[u].s[!c],ans |= 1;
		else k -= less,u = t[u].s[c];
	} return ans;
}
struct val {
	int p,v,k;
	val(int p,int k):p(p),k(k) { v = get(rt[p],a[p],k); }
	inline bool operator<(const val& t) const { return v < t.v; }
};
priority_queue<val> pq;
signed main() {
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>k;
	insert(rt,0);
	for(int i = 1;i<=n;++i) cin>>a[i],insert(&(rt[i] = rt[i-1]),a[i] ^= a[i-1]);
	for(int i = 1;i<=n;++i) {
		val t(i,1);
		pq.push(t);
	}
	int ans = 0;
	while(k--) {
		const val t = pq.top(),p(t.p,t.k+1);
		pq.pop();
		ans += t.v;
		pq.push(p);
	}
	cout<<ans;
}
2023/4/30 17:05
加载中...