【悬赏 一关注】 60pts代码求调
查看原帖
【悬赏 一关注】 60pts代码求调
360780
Qerrj楼主2023/11/15 20:06
#include<cstdio>
#include<queue>
using namespace std;
const int N = 5e5 + 10;
const int Maxbit = 33; 
typedef long long lint;
int n, m;
lint a[N], sum[N];
struct Trie{
	int tot, rt[N], ch[N * Maxbit][2], sum[N * Maxbit], id[N * Maxbit];
	inline int insert(int x, lint val, int _id) {
		int y, o; y = o = ++tot;
		for (int i = Maxbit; i >= 0; i--) {
			ch[y][0] = ch[x][0];
			ch[y][1] = ch[x][1];
			sum[y] = sum[x] + 1;
			int c = (val & (1ll << i)) >> i;
			ch[y][c] = ++tot;
			y = ch[y][c];
			x = ch[x][c];
		}
		id[y] = _id;
		sum[y] = sum[x] + 1;
		return o;
	}
	inline int query(int l, int r, lint val) {
//		lint ans = 0;
		for (int i = Maxbit; i >= 0; i--) {
			int c = (val & (1ll << i)) >> i; 
			if (sum[ch[r][c ^ 1]] - sum[ch[l][c ^ 1]]) {
//				ans += (1ll << i);
				l = ch[l][c ^ 1];
				r = ch[r][c ^ 1];
			}
			else {
				l = ch[l][c];
				r = ch[r][c];
			}
		}
		return id[r];
	}
}t;
struct Node{
	int l, r, k, rr; lint val;
	bool operator < (const Node &x) const {
		return val < x.val;
	}
};
priority_queue<Node> q; 
lint ans;
int main() {
//	lint x = 1ll; printf("%lld", x);
	scanf("%d%d", &n, &m);
//	t.rt[0] = t.insert(0, 0, 0);
//	printf("%d\n", t.id[35]);
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] ^ a[i];
	for (int i = 1; i <= n; i++) {
//		sum[i] = sum[i - 1] ^ a[i];
//		if (i == 0) t.rt[i] = t.insert(0, 0, 0);
		t.rt[i] = t.insert(t.rt[i - 1], sum[i - 1], i);
		int k = t.query(t.rt[0], t.rt[i], sum[i]);
		q.push((Node){1, i, k, i, sum[i] ^ sum[k - 1]});
	}
//	printf("%d\n", t.id[35]);
//	for (int i = 1; i <= 100; i++) {
//		printf("%d %d\n", i, t.id[i]);
//	}
//	printf("%d\n", t.id[34]);
//	for (int i = 1; i <= n; i++) {
//		printf("%lld ", sum[i]);
//	}
//	q.push((Node){0, 0, 0, 0, 20});
//	q.push((Node){0, 0, 0, 0, 30});
//	q.push((Node){0, 0, 0, 0, 40});
//	printf("%lld\n", q.top().val);
	while(m--) {
		Node top = q.top(); q.pop();
		int l = top.l, r = top.r, k = top.k, rr = top.rr; lint val = top.val;
//		printf("%d", )
		ans += val;
		int kk;
		if (k > l) {
//			l == 0 ? kk = t.query(0, t.rt[k - 1], sum[rr]) : kk = t.query(t.rt[l - 1], t.rt[k - 1], sum[rr]);
			int kk = t.query(t.rt[l - 1], t.rt[k - 1], sum[rr]);
			q.push((Node){l, k - 1, kk, rr, sum[rr] ^ sum[kk - 1]});
		}
		if (k < r) {
			kk = t.query(t.rt[k], t.rt[r], sum[rr]);
			q.push((Node){k + 1, r, kk, rr, sum[rr] ^ sum[kk - 1]});
		}
	}
	printf("%lld", ans); 
	return 0;
}
2023/11/15 20:06
加载中...