LOJ-3048

题意

给一个长度为 nn 序列 aa，让你求前 kk 大区间异或和 的和，这 kk 个区间 [li,ri][l_i,r_i] 要满足 1≤l≤r≤n1\le l\le r\le n 且没有区间相同。

1≤n≤5×105,1≤k≤min⁡{n(n−1)2,2×105},0≤ai<2321\le n\le 5\times 10^5 ,1\le k\le \min\left\{\tfrac{n(n-1)}{2},2\times 10^5 \right\},0\le a_i\lt 2^{32}

题解

类似于 [NOI2010]超级钢琴 （那道题求区间和），先处理出异或前缀和 sn=⨁i=1nais_n=\bigoplus_{i=1}^n a_i，对于一个右端点 rr ，我们首先要找到使 sr⊕sls_r\oplus s_l 最大的 l,(l∈[0,r])l,(l\in[0,r]) ，处理异或和最大可以用 01tire 解决，这里有区间的限制要 可持久化，类似于主席树的操作，假设查询区间 [L,R][L,R] 则 root[R],root[L−1]root[R],root[L-1] 同时搜，root[R]root[R] 记录的个数减去 root[L−1]root[L-1] 记录的个数即为 [L,R][L,R] 区间的信息。

这样我们能得到对于每个右端点，使异或和最大的左端点，假设为 psps，进一步，此时我们求出 ps∈[L,R]ps\in[L,R] 使 sr⊕spss_r\oplus s_{ps} 最大，那么对于 ps1∈[L,ps−1],ps2∈[ps+1,R]ps_1\in[L,ps-1],ps_2\in[ps+1,R] ，必然 sr⊕sps1,sr⊕sps2≤sr⊕spss_r\oplus s_{ps_1},s_r\oplus s_{ps_2}\le s_r\oplus s_{ps} 。也就是说更新完 psps 后才可能更新 ps1,ps2ps_1,ps_2 。

具体做法：

1.考虑开一个大根堆，以异或和大小为序，枚举一遍 rr ，找出 psps 和 valval（val=max⁡sr⊕sp,  ps∈[0,r]val=\max s_r\oplus s_p,\;ps\in [0,r] ）（可持久化01trie解决） 把 (val,ps,L,R,r)(val,ps,L,R,r) 这样的五元组插入堆中。L,RL,R 表示 psps 的范围（这里 L=0,R=rL=0,R=r）

2.每次从堆顶取出元素 (val,ps,L,R,r)(val,ps,L,R,r) ，然后 ans+=valans+=val ，分别在 [L,ps−1],[ps+1,R][L,ps-1],[ps+1,R] 中找 ps1,ps2ps_1,ps_2 使 sr⊕sps1/2s_r\oplus s_{ps_{1/2}} 最大，再向堆中插入 (val1,ps1,L,ps−1,r),(val2,ps2,ps+1,R,r)(val_1,ps_1,L,ps-1,r),(val_2,ps_2,ps+1,R,r) 。

3.重复 2 步骤直到取出元素 =k=k

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>
#define ls(p) t[p].ch[0]
#define rs(p) t[p].ch[1]
#define s(p,d) t[p].ch[d]
using namespace std;
typedef unsigned int ui;
typedef long long ll;
template<typename T>
inline void red(T &x) {
    x=0;bool fg=0;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') fg^=1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(T)(ch^48),ch=getchar();
    if(fg) x=-x;
}
const int N = 500010;
struct node{int ch[2],siz,pos;}t[N*33];
struct rec{
    int id,L,R,ps;ui val;
    rec(int _id,int _L,int _R,int _ps,ui _val) {id=_id,L=_L,R=_R,ps=_ps,val=_val;} 
    bool operator<(const rec a) const {return val<a.val;}
};
int root[N],n,K,tot;
ui a[N];
int newnode(int _ps) {
    tot++;ls(tot)=rs(tot)=0;t[tot].pos=_ps;
    return tot;
}
// base on p , insert at q
void insert(int p,int q,ui num,int _ps) {
    bool d;
    t[q].siz=t[p].siz+1;
    for(int i=31;i>=0;--i) {
        d=(num>>i)&1;
        t[q].ch[d]=newnode(_ps);
        t[q].ch[d^1]=t[p].ch[d^1];
        p=t[p].ch[d];q=t[q].ch[d];
        t[q].siz=t[p].siz+1;
    }
}
void build() {
    root[0]=newnode(0);
    int p=root[0];
    t[p].siz=1;
    for(int i=0;i<=31;++i) {
        ls(p)=newnode(0);
        p=ls(p);
        t[p].siz=1;
    }
}
// in [L,R] find the pos that max {a[pos]^k} 
ui query(int L,int R,ui k,int &ps) {
    int p=(L==0)?0:root[L-1],q=root[R];
    bool d;ui ret=0;
    for(int i=31;i>=0;--i) {
        d=(k>>i)&1;
        if(t[s(q,d^1)].siz-t[s(p,d^1)].siz>0) {
            ret|=(1u<<i);
            p=s(p,d^1);q=s(q,d^1);
        }else {
            p=s(p,d);q=s(q,d);
        }
    }
    ps=t[q].pos;
    return ret;
}
// void pt(int i) {
//     int p=root[i];
//     for(int i=31;i>=0;i--) {
//         if(t[ls(p)].pos==t[p].pos) p=ls(p);
//         else p=rs(p);
//     }
// }
int main() {
    red(n);red(K);   
    build();
    // pt(0);
    for(int i=1;i<=n;i++) {
        red(a[i]);
        a[i]^=a[i-1];
        insert(root[i-1],root[i]=newnode(i),a[i],i);
        // pt(i);
    }
    priority_queue<rec> q;
    for(int i=1;i<=n;i++) {
        int ps;
        ui tmp=query(0,i,a[i],ps);
        q.push(rec(i,0,i,ps,tmp));
    }
    ll ans=0;
    while(K--) {
        rec now=q.top();q.pop();
        ans+=(ll)now.val;
        int ps;ui tmp;
        if(now.L<now.ps) {
            tmp=query(now.L,now.ps-1,a[now.id],ps);
            q.push(rec(now.id,now.L,now.ps-1,ps,tmp));
        }
        if(now.ps<now.R) {
            tmp=query(now.ps+1,now.R,a[now.id],ps);
            q.push(rec(now.id,now.ps+1,now.R,ps,tmp));
        }
    }
    printf("%lld\n",ans);
    return 0;
}