记录编号	612602	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2019]异或粽子	最终得分	100
用户昵称	终焉折枝	是否通过	通过
代码语言	C++	运行时间	6.927 s
提交时间	2026-02-24 17:03:23	内存使用	40.95 MiB

#include<iostream>
#include<queue>
using namespace std;

#define ll long long
const int MAXN = 5e5 + 5;
const int MAXT = MAXN * 32;

int ch[MAXT][2], cnt[MAXT];
ll s[MAXN], tot = 0, n, k;

struct node{
    int id, rk;
    ll val;
    bool operator<(const node &other)const{
        return val < other.val;
    }
};

void Insert(ll x){
    int now = 0;
    for(int i = 31;i >= 0;i --){
        int op = (x >> i) & 1;
        if(!ch[now][op]) ch[now][op] = ++ tot;
        now = ch[now][op];
        cnt[now] ++;
    }
}

ll query(ll x, int rk){
    int now = 0;
    ll res = 0;
    for(int i = 31;i >= 0;i --){
        int op = (x >> i) & 1;
        op ^= 1;
        if(!ch[now][op]){
            now = ch[now][op ^ 1];
        }
        else if(rk <= cnt[ch[now][op]]){
            res |= (1LL << i);
            now = ch[now][op];
        }
        else{
            rk -= cnt[ch[now][op]];
            now = ch[now][op ^ 1];
        }
    }
    return res;
}

int main(){
    cin.tie(0) -> ios::sync_with_stdio(0);
    cin >> n >> k;
    s[0] = 0;
    Insert(s[0]);
    for(int i = 1;i <= n;i ++){
        ll a; cin >> a;
        s[i] = s[i - 1] ^ a;
        Insert(s[i]);
    }
    
    priority_queue<node> q;
    for(int i = 0;i <= n;i ++){
        ll x = query(s[i], 1);
        q.push({i, 1, x});
    }
    ll ans = 0;
    for(int i = 1;i <= 2 * k;i ++){
        node t = q.top();
        ans += t.val;
        q.pop();
        if(t.rk < n){
            q.push({t.id, t.rk + 1, query(s[t.id], t.rk + 1)});
        }
    }
    cout << ans / 2;
    return 0;
}