比赛 收心赛 评测结果 AAAAAAAAAAAAAAAAWWWW
题目名称 异或粽子 最终得分 80
用户昵称 xuyuqing 运行时间 7.575 s
代码语言 C++ 内存使用 92.33 MiB
提交时间 2026-02-24 10:57:00
显示代码纯文本

#include <cstdio>
#include <iostream>
#include <queue>
#include <unordered_set>
#include <utility>

using namespace std;

const int N = 514514 + 233233;
const int Node = N * 64;

int n;
int k;
long long nums[N];
int trie[Node][2];
int fa[Node];
int rt[N];
int cc;
priority_queue<pair<long long, long long>> pq;
long long res;

void insert (int id, long long num) {
    cc++;
    rt[id] = cc;
    int now = rt[id];
    int pre = rt[id - 1];
    trie[now][0] = trie[pre][0];
    trie[now][1] = trie[pre][1];
    for (long long i = (1ll << 32); i; i >>= 1) {
        bool flag = (i & num);
        cc++;
        trie[now][flag] = cc;
        
        now = trie[now][flag];
        pre = trie[pre][flag];
        
        trie[now][0] = trie[pre][0];
        trie[now][1] = trie[pre][1];
    }
}

long long find (int id, long long num) {
    int now = rt[id];
    long long t = 0;
    for (long long i = (1ll << 32); i; i >>= 1) {
        bool flag = !(i & num);
        if (trie[now][flag]) {
            now = trie[now][flag];
            t += i * flag;
        }
        else {
            flag = !flag;
            now = trie[now][flag];
            t += i * flag;
        }
    }
    return num ^ t;
}

void del (int id, long long num) {
    cc++;
    int now = cc;
    int pre = rt[id];
    rt[id] = cc;
    trie[now][0] = trie[pre][0];
    trie[now][1] = trie[pre][1];
    for (long long i = (1ll << 32); i; i >>= 1) {
        bool flag = (i & num);
        cc++;
        trie[now][flag] = cc;
        fa[cc] = now;
        
        now = trie[now][flag];
        pre = trie[pre][flag];
        
        trie[now][0] = trie[pre][0];
        trie[now][1] = trie[pre][1];
    }
    
    for (long long i = 1; i <= (1ll << 32); i <<= 1) {
        bool flag = (i & num);
        trie[fa[now]][flag] = 0;
        if (trie[fa[now]][!flag]) {
            break;
        }
        now = fa[now];
    }
}

int main () {

	freopen ("xor.in", "r", stdin);
	freopen ("xor.out", "w", stdout);
	
	cin >> n >> k;
	insert (0, 0);
	for (int i = 1; i <= n; i++) {
	   cin >> nums[i];
	   nums[i] ^= nums[i - 1];
	   insert (i, nums[i]);
    }
    
    for (int i = 1; i <= n; i++) {
        pq.emplace(find (i, nums[i]), i);
    }
    
    for (int i = 1; i <= k; i++) {
        auto t = pq.top();
        pq.pop();
        res += t.first;
        del (t.second, (t.first ^ nums[t.second]));
        pq.emplace(find (t.second, nums[t.second]), t.second);
    }
    
    cout << res << endl;

	return 0;
}