社区讨论

求助,本地正常,OJ CE

P5283[十二省联考 2019] 异或粽子参与者 4已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@m0ffyovv
此快照首次捕获于
2024/08/29 23:30
去年
此快照最后确认于
2025/11/04 22:03
4 个月前
查看原帖
编译信息:
编译失败
g++: 编译器内部错误:File size limit exceeded signal terminated program as 请提交一份完整的错误报告, 如有可能请附上经预处理后的源文件。 参阅 https://gcc.gnu.org/bugs/ 以获取指示。
代码:
CPP
#include <bits/stdc++.h>
#include <iostream>

#ifdef K_LOCAL
#define FIN freopen("input.txt", "r", stdin);
#define FOUT freopen("output.txt", "w", stdout);
#define FILE FIN FOUT
#define dbg(...) do { fprintf(stderr, __VA_ARGS__); fflush(stderr); } while(0);
#else
#define FIN
#define FOUT
#define FILE
#define dbg(...) ((void)0);
#endif

#define cmax(x, y) (x = ::std::max((x), (y)))
#define cmin(x, y) (x = ::std::min((x), (y)))

#define pt(...) (printf(__VA_ARGS__), fflush(stdout))
#define ps putchar(' ')
#define pn putchar('\n')

#define rep(it, st, ed) for(int it = (st); it <= (ed); it++)
#define per(it, st, ed) for(int it = (ed); it >= (st); it--)
#define fors(it, str) for(int it = 1; str[it]; it++)

using ll = long long;
using ul = unsigned long long;
using lf = double;
using ld = long double;

#define lowbit(x) ((x) & (-(x)))

template<class T>
void qr(T& x) {
	x = 0;
	bool s = 0;
	char c;
	while(!isdigit(c = getchar()))
		if(c == '-')
			s = 1;
	do
		x = (x << 3) + (x << 1) + (c ^ 48);
	while(isdigit(c = getchar()));
	if(s)
		x = -x;
}
template<class T>
void qw(T x) {
	static char _buf[100];
	int bp = 0;
	if(!x) {
		putchar('0');
		return;
	}
	while(x)
	{
		_buf[++bp] = x % 10;
		x /= 10;
	}
	per(i, 1, bp)
		putchar(_buf[i] | 48);
}

#define N 500005

int tr[N * 34][2], tp = 0;
int lt[N * 34] = {-114514};
void tr_add(int p, int q, uint32_t x, int id, int bit) {
	if(bit < 0) {
		lt[p] = id;
		return;
	}
	int c = (x >> bit) & 1;
	if(q)
		tr[p][c ^ 1] = tr[q][c ^ 1];
	tr[p][c] = ++tp;
	tr_add(tr[p][c], tr[q][c], x, id, bit - 1);
	lt[p] = ::std::max(lt[tr[p][0]], lt[tr[p][1]]);
}
int tr_ask(int p, int x, int lim, int bit) {
	if(bit < 0)
		return lt[p];
	int c = (x >> bit) & 1;
	if(lt[tr[p][c ^ 1]] >= lim)
		return tr_ask(tr[p][c ^ 1], x, lim, bit - 1);
	return tr_ask(tr[p][c], x, lim, bit - 1);
}

int n, m;
uint32_t s[N];
int rt[N];
struct T {
	int o, l, r, t;
	bool operator < (const T& rhs) const {
		return (s[o] ^ s[t]) < (s[rhs.o] ^ s[rhs.t]);
	}
};

int main() {
	qr(n), qr(m);
	tr_add(rt[0] = ++tp, 0, 0, 0, 32);
	rep(i, 1, n)
	{
		uint32_t x;
		qr(x);
		s[i] = s[i - 1] ^ x;
		tr_add(rt[i] = ++tp, rt[i - 1], s[i], i, 32);
	}
	::std::priority_queue<T> q;
	rep(i, 1, n)
		q.push({i, 0, i - 1, tr_ask(rt[i - 1], s[i], 0, 32)});
	ll ans = 0;
	while(m--)
	{
		T t = q.top();
		q.pop();
		ans += s[t.o] ^ s[t.t];
		if(t.t + 1 <= t.r)
			q.push({t.o, t.t + 1, t.r, tr_ask(rt[t.r], s[t.o], t.t + 1, 32)});
		if(t.t - 1 >= t.l)
			q.push({t.o, t.l, t.t - 1, tr_ask(rt[t.t - 1], s[t.o], t.l, 32)});
	}
	qw(ans), pn;
	return 0;
}

回复

7 条回复,欢迎继续交流。

正在加载回复...