P5283 [十二省联考 2019] 异或粽子 题解

根据题目可知，答案是若干个区间异或和的和。若进行异或前缀和，记 则 。于是问题转化为找到 个不重复的二元组 ，满足 ，且 最大。

首先，对于每个右端点 ， 的取值范围是 ，于是可以使用 可持久化 找出使得 最大的 ，并记录下当前选的 是什么， 的取值范围是什么，然后把这些东西扔到堆里面，每次弹出一个 最大的，然后再在 两侧取值范围内找两个最大的，再扔到堆里面，和 超级钢琴 差不多。

然后就做完了。

AC Code:

#include <bits/stdc++.h>
using namespace std;
namespace Slongod{
using uint = unsigned int;
using ll = long long int;
const int N = 5e5+7;

//可持久化tri树
#define ls tree[ro].son[1]
#define rs tree[ro].son[0]
struct TREE{int size , id , son[2];}tree[N*33];
int cnt , head[N];
int copyfrom(int ro){cnt++; tree[cnt] = tree[ro]; return cnt;}
void check(int &ro){ro = (!ro ? ++cnt : copyfrom(ro));}
void update(int ro , uint x , int id , int d=31)
{
    if (d < 0){tree[ro].size++; tree[ro].id = id; return;}
    int c = ((x>>d)&1);
    check(tree[ro].son[c]);
    update(tree[ro].son[c] , x , id , d-1);
    tree[ro].size = tree[ls].size + tree[rs].size;
}
pair<uint,int> query(int lo , int ro , uint x , int d=31)
{
    if (d < 0){return {0,tree[ro].id};}
    int c = ((x>>d)&1);
    if (tree[ro].son[!c] and tree[tree[ro].son[!c]].size - tree[tree[lo].son[!c]].size) {
        auto t = query(tree[lo].son[!c] , tree[ro].son[!c] , x , d-1);
        return {(uint(1)<<d)|(t.first) , t.second};
    } else {
        return query(tree[lo].son[c] , tree[ro].son[c] , x , d-1);
    }
}
#undef ls
#undef rs
struct node
{
    uint val , op; int l , r , c;
    friend bool operator < (node a , node b){return a.val < b.val;}
};

int n , k; uint a[N]; ll ans;
int main()
{
    cin >> n >> k; n++; for (int i = 2; i <= n; i++){cin >> a[i]; a[i] ^= a[i-1];}

    priority_queue <node> q;
    for (int i = 1; i <= n; i++) {
        head[i] = copyfrom(head[i-1]);
        update(head[i] , a[i] , i);
        if (i > 1) {
            auto t = query(head[0] , head[i-1] , a[i]);
            q.push({.val=t.first , .op=a[i] , .l=1 , .r=i-1 , .c=t.second});
        }
    }

    for (int i = 1; i <= k; i++) {
        auto t = q.top(); q.pop();
        ans += t.val;

        if (t.c != t.l) {
            auto tmp = query(head[t.l-1] , head[t.c-1] , t.op);
            q.push({.val=tmp.first , .op=t.op , .l=t.l , .r=t.c-1 , .c=tmp.second});
        }
        if (t.c != t.r) {
            auto tmp = query(head[t.c] , head[t.r] , t.op);
            q.push({.val=tmp.first , .op=t.op , .l=t.c+1 , .r=t.r , .c=tmp.second});
        }
    }
    cout << ans << '\n';
    return 0;
}
}int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.in" , "r" , stdin);
    #endif
    ios :: sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    return Slongod :: main();
}