quhengyi11 的博客

quhengyi11 的博客

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

posted on 2019-04-25 21:53:16 | under 题解 |

可持久化$Trie$树+堆

刚开始想着在$Trie$树上二分来降一个$log$来着然后发现自己$sb$了

最开始的前缀和不用说了

然后我们可以用堆维护最大值,然后去扩展其它最大值,具体来讲,我们首先需要建一个可持久化$Trie$,滋磁区间$xor$最值查询,然后记录一个五元组$(l,r,val,ori,pos)$表示在区间$[l,r]$之间的某个数数与$ori$取异或最大为$val$且这个数的位置是$pos$,然后每次从堆里取$val$最大的然后分裂就行。

#include<bits/stdc++.h>
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define eps 1e-4
#define mod 10086
#define lowbit(x) (x & -x)
#define N 500005
#define ls (u << 1)
#define rs (u << 1 | 1)
#define cl(arr) memset(arr, 0, sizeof arr)
#define bset std::bitset<N>
inline void read (int &x)
{
    x = 0;
    Re char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
}
struct trie {
    int rt[N], t[N * 33][2], cnt, sum[N * 33], id[N * 33];
    inline void ins (int &uu, int pu, int val, int idx)
    {
        uu = ++cnt;
        int u = uu;
        sum[u] = sum[pu] + 1;
        fd (i, 31, 0)
        {
            bool now = (val >> i & 1);
            t[u][now] = ++cnt;
            t[u][!now] = t[pu][!now];
            pu = t[pu][now]; u = t[u][now];
            sum[u] = sum[pu] + 1;
        }
        id[u] = idx;
    }
#define pi std::pair<ll, int>
    inline pi query (int u, int pu, int val)
    {
        pi ret = mp(0, 0);
        fd (i, 31, 0)
        {
            bool now = (val >> i & 1);
            if (sum[t[u][!now]] - sum[t[pu][!now]])
            {
                ret.F |= 1ll << i;
                u = t[u][!now];
                pu = t[pu][!now];
            }
            else
            {
                u = t[u][now];
                pu = t[pu][now];
            }
        }
        ret.S = id[u];
        return ret;
    }
} t;
unsigned int a[N];
int n, m;
struct node {
    ll l, r, val, ori, pos;
    friend bool operator < (node x, node y) { return x.val < y.val; }
};
std::priority_queue<node> q;
int main ()
{
    scanf("%d %d", &n, &m);
    fo (i, 1, n) { scanf("%u", &a[i + 1]); a[i + 1] ^= a[i]; }
    ++n;
    fo (i, 1, n) t.ins(t.rt[i], t.rt[i - 1], a[i], i);
    fo (i, 1, n) 
    {
        pi now = t.query(t.rt[i - 1], t.rt[0], a[i]);
        q.push((node) {1, i - 1, now.F, a[i], now.S});
    }
    ll ans = 0;
    while (m--)
    {
        node u = q.top(); q.pop();
        ans += u.val;
        if (u.l < u.pos)
        {
            pi now = t.query(t.rt[u.pos - 1], t.rt[u.l - 1], u.ori);
            q.push((node) {u.l, u.pos - 1, now.F, u.ori, now.S});
        }
        if (u.pos < u.r)
        {
            pi now = t.query(t.rt[u.r], t.rt[u.pos], u.ori);
            q.push((node) {u.pos + 1, u.r, now.F, u.ori, now.S});
        }
    }
    printf("%lld", ans);
    return 0;
}