社区讨论
求助,本地正常,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 条回复,欢迎继续交流。
正在加载回复...