Shopping Plans Trick

stripe_python · 2025-10-29 15:35:47 · 算法·理论

Shopping Plans Trick 的名称来源为 P6646 [CCO 2020] Shopping Plans，指的是用堆解决一类前 k 优解的问题。

这种 trick 的核心是构造一个状态 S，然后用一个堆来维护转移，一般可以做到 O(n \log n+k\log k) 的复杂度。

由于笔者写的可能不是特别深入，因此推荐扩展阅读，能够让你更深入了解 Shopping Plans Trick 的本质。

1. 原理

Shopping Plans Trick 的名称来源为 P6646 [CCO 2020] Shopping Plans，指的是用堆解决一类前 k 优解的问题。

这种 trick 的核心是构造一个状态 S，然后用一个堆来维护转移，一般可以做到 O(n \log n+k\log k) 的复杂度。

1.1 算法流程

设状态 S 的答案为 f(S)。

初始时，将初始状态 S_0 入堆。（或者将若干初始状态 \{S_0\} 入堆）

重复执行 k 次操作：

• 取出堆顶状态 S。设 \operatorname{trans}(S) 表示 S 的后继状态集合。
• 输出 f(S)。

实际上，这里的复杂度应该是 O(k |\operatorname{trans}(S)| \log k) 的。在实际问题中，|\operatorname{trans}(S)| 往往是 O(1) 的。

1.2 要求

• 唯一性：不存在一个 S 使得当 S_1 \ne S_2 时 S \in \operatorname{trans}(S_1) 且 S \in \operatorname{trans}(S_2)。
• 覆盖性：对于任何合法的状态 S，都存在一条路径使得 S 由 S_0 经若干次转移而来。
• 最优性：以 k 小值为例，\forall S' \in \operatorname{trans}(S), w(S') \ge w(S)。

根据唯一性和覆盖性，如果对于所有 S' \in \operatorname{trans}(S)，连一条 S \to S' 的有向边，则会构成一棵以 S_0 为根的外向树。根据最优性，树上深度越深的节点答案越劣。

1.3 正确性

注意到，这个 trick 的本质是在外向树上跑了一个 Dijkstra。

覆盖性保证了全部状态可达、最优性保证了边权非负，从而满足 Dijkstra 的贪心证明。

如果我们建出这棵树，复杂度就会变成 O(m \log m)，其中 m 是 S 的种类数。在许多题目中，m=O(\operatorname{poly}(n))，这是不可接受的。

而唯一性使得我们直接对这棵树层序遍历即可，不需要判断一个节点是否出现过。这样复杂度才是 O(n \log n+k\log k)。

1.4 做题方法

和 DP 一样，Shopping Plans Trick 也有一些要素：

1. 设计状态。状态的选择要注意空间，同时尽量保证唯一性。
2. 设计转移。这里还会用到分步转移、撤销等 trick。
3. 验证三条性质。

2. 例题

2.1 Multiset

2.1.1 Shopping Plans on Multiset 1

给你一个大小为 n 的可重集 S，求大小为 p 的前 k 小子集和。

:::::success[题解] 先对 S 排序，则 S_0 为选择前 p 项。

一个思想是用 p 元组作为状态，表示我们选了第几个数。转移直接用一个数替换另一个数，但它不满足唯一性。我们采用这样的转移方法：

• 将最左的可右移元素右移若干位，且不跨过已选择的数字。

借用一下 command_block 大佬做的图：

容易证明这种方法同时满足最优性、唯一性、覆盖性。然而转移是 O(n) 的。

这里用到一个重要思想：分步转移。对于每个元素我们只让它后移一位，这样也满足覆盖性。

于是用三元组 S=(i,j,k) 表示选择前 i 个数，目前考虑第 j 个数，第 j 个数后面第一个选择的数位置为 k，k 及以后的数的选择方案是确定的。根据上述分析有转移：

1. 若 j<k，可以不选 j 考虑下一位，有 S_1=(i,j+1,k)。
2. 从 [1,x] 中选出一个作为当前考虑的数，将 j 扔到后面不再考虑，即向前扩展一位，有 S_2=(i-1,i+1,j)。

可以发现 S_0=(p,n+1,n+1)。复杂度 O(n \log n+k \log k)。

实现时，注意判断转移的合法性。在状态内再加一维来表示 w(S)。

::::info[代码]

const int N = 3e5 + 5;
int n, k, p, a[N];
struct node {
    int i, j, k; long long w;
    node(int a = 0, int b = 0, int c = 0, long long d = 0) : i(a), j(b), k(c), w(d) {}
    bool operator< (const node& a) const {return w > a.w;}
};
priority_queue<node> q;

void _main() {
    cin >> n >> k >> p;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);

    long long sum = 0;
    for (int i = 1; i <= p; i++) sum += a[i];
    q.emplace(p, n + 1, n + 1, sum);
    while (k--) {
        int i = q.top().i, j = q.top().j, k = q.top().k;
        long long w = q.top().w; q.pop();
        cout << w << '\n';
        if (j + 1 < k) q.emplace(i, j + 1, k, w - a[j] + a[j + 1]);
        if (i >= 1 && i + 1 < j) q.emplace(i - 1, i + 1, j, w - a[i] + a[i + 1]);
    }
}

:::: :::::

2.1.2 Shopping Plans on Multiset 2

给你一个大小为 n 的可重集 S，求大小在 [l,r] 之间的前 k 小子集和。

:::::success[题解] 套用 Shopping Plans on Multiset 1 的做法，但是这里的 S_0 是特殊的。对于 i \in [l,r]，将 (i,n+1,n+1) 入堆。复杂度 O(n \log n+k\log k)。 :::::

2.1.3 Shopping Plans on Multiset 3

给你一个大小为 n 的可重集 S，求前 k 小子集和，可以为空。

原题链接：51Nod 3046 子集和的元素和。

:::::success[解法 1] 直接用 Shopping Plans on Multiset 2 的做法，令 l=0,r=n 即可，复杂度 O(n \log n+k\log k)。 :::::

:::::success[解法 2] 还是先排序，用 S=(i,w) 表示考虑前 i 个数，当前答案为 w 的状态。转移就是 (i+1,w) 和 (i+1,w+a_i)。

但是当 S 中有负数时不满足最优性。我们将所有负数先取反，用答案减去负数的和。这样对于负数 x，若选 |x| 就与负数和中的 x 抵消了；若没选 x，减去以后相当于选了 x。

复杂度 O(n \log n+k\log k)，常数更优。 :::::

2.2 Arrays

2.2.1 Shopping Plans on Arrays 1

有两个长度为 n 的序列 a,b，在 a,b 中各取一个数相加可以得到 n^2 个和，求这 n^2 个和中最小的 k 个。

原题链接：P1631 序列合并。

:::::success[解法 1] 先将 a,b 排序。有结论：当 i \times j > k 时 a_i+b_j 一定不是前 k 小的数。

证明：若 x \le i,y\le j，则 a_x+b_y \le a_i+b_j，所以至少有 i \times j 个数小于 a_i+b_j。当 i \times j>k 时有多于 k 个数小于 a_i+b_j，故 a_i+b_j 一定不是前 k 小的数。

按这个结论直接枚举，排序输出即可。复杂度 O(n \log n \log k)。

::::info[代码]

const int N = 1e5 + 5;
int n, k, a[N], b[N];
vector<int> vec;

void _main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    sort(a + 1, a + n + 1), sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n && 1LL * i * j <= k; j++) vec.emplace_back(a[i] + b[j]);
    }
    sort(vec.begin(), vec.end());
    for (int i = 1; i <= k; i++) cout << vec[i - 1] << '\n';
}

:::: :::::

:::::success[解法 2] 先将 a,b 排序。用状态 S=(i,j) 表示选择了 a_i+b_j 的方案，显然 S_0=(1,1)。对于 S=(i,j)，容易得到 \operatorname{trans}(S)=\{(i+1,j),(i,j+1)\}。

但是 \operatorname{trans}(S) 不满足唯一性。由于状态只有 k 个，用哈希判重，复杂度不超过 O(k \log k)。总复杂度 O(n\log n+k\log k)。

原题链接：P6646 [CCO 2020] Shopping Plans，这个系列的名称来源。

:::::success[题解] 仔细想想 Shopping Plans on Arrays 2 的做法，我们排序这 n 个数组的目的就是快速获取数组内的第 k 大值。

所以我们用 Arrays 2 套 Multiset 2 的做法，外层按 Arrays 2 的方法跑，再开 n 个结构体，内部跑 Multiset 2。复杂度 O(n\log k + k\log^2 k)。

::::info[代码] 放的 P6646 的代码。

const int N = 2e5 + 5;
const long long null = 0x3f3f3f3f3f3f3f3f;

int n, m, k, t, c;
struct box {  // Shopping Plans on Multiset 2
    struct node {
        int i, j, k; long long w;
        node(int a = 0, int b = 0, int c = 0, long long d = 0) : i(a), j(b), k(c), w(d) {}
        bool operator< (const node& a) const {return w > a.w;}
    };
    priority_queue<node> q;

    vector<int> a;
    vector<long long> ans;
    int l, r;
    void add(int x) {a.emplace_back(x);}

    void init() {
        int n = a.size();
        if (l > r || l > n) return;  // 注意特判 
        sort(a.begin(), a.end());
        long long sum = 0;
        for (int i = 1; i < l; i++) sum += a[i - 1];
        if (l == 0) q.emplace(0, n + 1, n + 1, 0), l++;  // 特判l=0
        for (int i = l; i <= min(r, n); i++) sum += a[i - 1], q.emplace(i, n + 1, n + 1, sum);
        next(), next();
    }
    long long next() {
        if (q.empty()) return null;
        int i = q.top().i, j = q.top().j, k = q.top().k;
        long long w = q.top().w; q.pop();
        ans.emplace_back(w);
        if (j + 1 < k) q.emplace(i, j + 1, k, w - a[j - 1] + a[j]);
        if (i >= 1 && i + 1 < j) q.emplace(i - 1, i + 1, j, w - a[i - 1] + a[i]);
        return ans.back();
    }
    long long key() const {
        return ans.size() >= 2 ? ans[1] - ans[0] : null;
    }
} a[N];

struct node {
    int x, y; long long val;
    node(int a = 0, int b = 0, long long c = 0) : x(a), y(b), val(c) {}
    bool operator< (const node& a) const {return val > a.val;}
};
priority_queue<node> q;

long long A(int i, int k) {
    while ((int) a[i].ans.size() < k) {
        if (a[i].next() == null) return null;
    }
    return (int) a[i].ans.size() >= k ? a[i].ans[k - 1] : null;
}

void _main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> t >> c, a[t].add(c);
    for (int i = 1; i <= m; i++) cin >> a[i].l >> a[i].r, a[i].init();
    // Shopping Plans on Arrays 2
    sort(a + 1, a + m + 1, [](box& a, box& b) -> bool {
        return a.key() < b.key();
    });
    long long res = 0;
    for (int i = 1; i <= m; i++) {
        if (A(i, 1) == null) {   // 注意特判
            while (k--) cout << -1 << '\n';
            return;
        }
        res += A(i, 1);
    }
    cout << res << '\n';
    if (A(1, 2) != null) q.emplace(1, 2, res - A(1, 1) + A(1, 2)); 
    int cnt = 1;
    while (!q.empty()) {
        int x = q.top().x, y = q.top().y; long long v = q.top().val; q.pop();
        cout << v << '\n';
        if (++cnt >= k) break;
        if (A(x, y + 1) != null) q.emplace(x, y + 1, v - A(x, y) + A(x, y + 1));
        if (A(x + 1, 2) != null && x < n) q.emplace(x + 1, 2, v - A(x + 1, 1) + A(x + 1, 2));
        if (A(x, 2) != null && A(x + 1, 2) != null && x < n && y == 2) q.emplace(x + 1, 2, v - A(x + 1, 1) - A(x, 2) + A(x + 1, 2) + A(x, 1));  
    } 
    while (cnt++ < k) cout << -1 << '\n';
}

:::: :::::

2.4 Graph

2.4.1 Shopping Plans on Graph 1 & 2

给你一个 n 个点，m 条边的有向图，求从 s 到 t 的前 k 短路边权和。

对于 Graph 1，n,m,k \le 10^3。

对于 Graph 2，n,m,k \le 3 \times 10^5。

原题链接：Graph 1 是 P2901 [USACO08MAR] Cow Jogging G，Graph 2 类似 P2483 【模板】k 短路 / [SDOI2010] 魔法猪学院。

:::::success[题解] Graph 1 可以用 A* 做，这里就不展开了。我们来讲 Graph 1 & 2 的堆做法。

众所周知，在 Dijkstra 过程中有一个松弛操作：

if (dis[v] > dis[u] + w) {
  dis[v] = dis[u] + w;
}

在不含零环的图上，如果把发生了松弛的边单独拿出来，就会构成一个 DAG，这个图就叫最短路图。而如果给一个更强的条件，比如从源点到每个点的最短路唯一，建出来就是一棵树，叫做最短路树。

在最短路不唯一的图上，我们也可以建最短路树，但这时建立的最短路树不唯一。使用二叉堆优化的 Dijkstra 建最短路图 / 树，复杂度为 O(m \log n)。

在此题中，我们在反图上以 t 为源点跑 Dijkstra 建立最短路树。则一条从 s 到 t 的路径必然由若干树边和非树边组成。可以证明，一个非树边集合对应一条唯一的路径，于是我们就可以用非树边集合作为状态。

记状态为 S=\{e_1,e_2,e_3,\cdots,e_k\}，满足 e_i 的终点在最短路树上为 e_{i+1} 起点的祖先，则 w(S)=dis_{s,t}+\sum{\Delta w(e_i)}，其中 dis_{s,t} 为原最短路长度。考虑转移

1. 增加一条边 e_{k+1}，则 S_1=\{e_1,e_2,e_3,\cdots,e_k,e_{k+1}\}。
2. 设 e_{k-1} 的终点为 v，将 e_k 替换为边权更大的一条边 {e_k}'，保证最优性。同时为了保证唯一性，我们要求 {e_k}' 的起点是 v 的祖先所连的非树边中边权是 e_k 的后继的边。转移为 S_2=\{e_1,e_2,e_3,\cdots,{e_k}'\}。

当然还是优化掉空间。直接用 v 来表示状态即可，再开一维表示 w(S)。现在问题只剩下求非树边的后继边。

使用一个可持久化的堆，支持 Push & Pop，这里用可持久化左偏树。堆上每个节点左儿子维护自身边，右儿子维护祖先边。那么 S_1 就是加入编号为 v 的小根堆中堆顶对应边，S_2 就是把 v 替换成其在堆中所有儿子所对应的边。

最终，我们在 O(m \log n+k\log k) 的复杂度下解决了单源单汇 k 短路问题。

::::info[代码]

const int N = 3e5 + 5;
int n, m, k, u, v, s, t, p[N]; 
long long w;

int tot = 0, head[N];
struct Edge {
    int next, to; long long dis;
} edge[N << 1];
inline void add_edge(int u, int v, long long w) {
    edge[++tot].next = head[u], edge[tot].to = v, edge[tot].dis = w, head[u] = tot;
}

namespace T {
    int cnt = 0;
    struct node {
        int l, r, dis, fa;
        long long val;
    } tr[N << 5];
    int create(int fa, long long val) {
        return tr[++cnt] = {0, 0, 0, fa, val}, cnt;
    }
    int copy(int x) {
        return tr[++cnt] = {tr[x].l, tr[x].r, tr[x].dis, tr[x].fa, tr[x].val}, cnt;
    }
    int merge(int a, int b) {
        if (!a || !b) return a ? a : b;
        if (tr[a].val > tr[b].val) swap(a, b);
        int nw = copy(a);  // 可持久化
        tr[nw].r = merge(tr[nw].r, b);
        if (tr[tr[nw].l].dis <= tr[tr[nw].r].dis) swap(tr[nw].l, tr[nw].r);
        tr[nw].dis = tr[nw].r ? tr[tr[nw].r].dis + 1 : 0;
        return nw;
    }
    int rt[N];
}

namespace D {
    int tot = 0, head[N];
    struct Edge {
        int next, to; long long dis;
    } edge[N << 1];
    inline void add_edge(int u, int v, long long w) {
        edge[++tot].next = head[u], edge[tot].to = v, edge[tot].dis = w, head[u] = tot;
    }

    struct node {
        int to; long long dis;
        node(int x = 0, long long y = 0.0) : to(x), dis(y) {}
        bool operator< (const node& other) const {return dis > other.dis;}
    };

    int fa[N];
    long long dis[N];
    priority_queue<node> q;
    void dijkstra(int s) {
        memset(dis, 0x3f, sizeof(dis));
        dis[s] = 0, q.emplace(s, 0.0);
        while (!q.empty()) {
            int u = q.top().to; long long d = q.top().dis; q.pop();
            if (d != dis[u]) continue;
            for (int j = head[u]; j != 0; j = edge[j].next) {
                int v = edge[j].to; long long w = edge[j].dis;
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w, fa[v] = j;
                    q.emplace(v, dis[v]);
                }
            }
        }
    }
}

void _main() {
    cin >> n >> m >> k >> s >> t;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        if (u != t) add_edge(u, v, w), D::add_edge(v, u, w);
    }
    D::dijkstra(t);
    if (D::dis[s] >= 0x3f3f3f3f3f3f3f3f) {
        while (k--) cout << -1 << '\n';
        return;
    }
    iota(p + 1, p + n + 1, 1);
    sort(p + 1, p + n + 1, [&](int a, int b) -> bool {
        return D::dis[a] < D::dis[b];
    });
    for (int i = 1; i <= n; i++) {
        int u = p[i];
        for (int j = head[u]; j != 0; j = edge[j].next) {
            if (j == D::fa[u]) continue;
            int v = edge[j].to; long long w = edge[j].dis;
            T::rt[u] = T::merge(T::rt[u], T::create(v, D::dis[v] + w - D::dis[u]));
        }
        int from = edge[D::fa[u]].to;
        T::rt[u] = T::merge(T::rt[u], T::rt[from]);
    }
    cout << D::dis[s] << '\n';
    int cnt = 1;
    if (k == 1) return;
    priority_queue<D::node> q;
    q.emplace(T::rt[s], T::tr[T::rt[s]].val);
    while (!q.empty()) {
        int u = q.top().to; long long d = q.top().dis; q.pop();
        cout << d + D::dis[s] << '\n';
        if (++cnt >= k) break;
        int ls = T::tr[u].l, rs = T::tr[u].r, fa = T::tr[u].fa;
        if (ls) q.emplace(ls, d - T::tr[u].val + T::tr[ls].val);
        if (rs) q.emplace(rs, d - T::tr[u].val + T::tr[rs].val);
        if (T::rt[fa]) q.emplace(T::rt[fa], d + T::tr[T::rt[fa]].val);
    }
    while (cnt++ < k) cout << -1 << '\n';
}

:::: :::::

3. Masonpop Trick

本来到这里，这篇文章就该进入练习题了。但是笔者来翻洛谷博客的时候看到了一位大佬的 Blog。于是这里写一下另外一个做法是怎么做的。

本文里先叫它 Masonpop Trick 吧。

3.1 原理

对值域二分。问题转化为：求有多少 w(S) \le mid。

求出 S 是困难的。masonpop 大佬指出：直接爆搜！假如我们的搜索次数是 O(k) 的，那么复杂度显然是正确的 O(k \log V)。

具体地，我们的搜索算法需要满足一个限制：

• 每次搜索一定会使得 S 的数目至少加一。

所以我们需要设计一个好的搜索方案，这样即解决第 k 小问题。

如果求的是前 k 小，将搜索到的方案输出即可。

由于本文讲的不是这个，因此学习这个 trick 推荐直接看大佬的博客。这个 trick 可以解决上面提到的 Multiset(s)、Arrays 的题目。

4. 练习

[NOI2010] 超级钢琴

给定长为 n 的序列 a 及整数 l,r，求前 k 大的长度在 [l,r] 之间的子段和。

::::success[题解] 先把 a 变成前缀和。

用四元组 (x,low,high,w) 表示状态，x 为右端点，[low,high] 为左端点的范围，w 为当前最大子段和。这满足了覆盖性。

答案式子大概是 a_{x}-a_{l'}，其中 l' \in [low,high]，需找到在一段区间中的 a 的最大值，使用 ST 表维护，设 a 最大值的下标为 f(l,r)。于是初始时将 (i,i-r,i-l,f(i-r,i-l)) 入堆即可。

考虑类似区间 DP 地分裂区间进行转移。取出 S 并找到 m=f(low,high)，从 m 处将区间分裂为 [low,m) 和 (m,high]。可以发现这样转移满足唯一性和最优性。复杂度 O(n \log n+k \log k)。

:::info[代码]

#define int long long
const int N = 5e5 + 5;

int n, k, l, r, a[N], st[lg(N) + 1][N];
int f(int x, int y) {return a[x] < a[y] ? x : y;}
struct node {
    int r, low, high, w;
    node(int a = 0, int b = 0, int c = 0, int d = 0) : r(a), low(b), high(c), w(d) {}
    bool operator< (const node& a) const {return w < a.w;}
};
priority_queue<node> q;
void prework() {
    for (int i = 1; i <= lg(n); i++) {
        for (int j = 0; j + (1 << (i - 1)) <= n; j++) st[i][j] = f(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
    }
}
int ask(int l, int r) {
    int k = lg(r - l + 1);
    return f(st[k][l], st[k][r - (1 << k) + 1]);
}

void _main() {
    cin >> n >> k >> l >> r;
    for (int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1];
    iota(st[0] + 1, st[0] + n + 1, 1);
    prework();
    for (int i = l; i <= n; i++) {
        int low = max<int>(0, i - r), high = i - l;
        q.emplace(i, low, high, a[i] - a[ask(low, high)]);
    }
    int res = 0;
    while (k--) {
        int to = q.top().r, low = q.top().low, high = q.top().high, w = q.top().w; q.pop();
        res += w;
        int mid = ask(low, high), x = 0;
        if (low < mid) x = ask(low, mid - 1), q.emplace(to, low, mid - 1, a[to] - a[x]);
        if (high > mid) x = ask(mid + 1, high), q.emplace(to, mid + 1, high, a[to] - a[x]);
    } cout << res;
}

::: ::::

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

给定长为 n 的序列 a，求前 k 大的子段异或和。

::::success[题解] 把 a_i 变成前缀异或，那么 [l,r] 的区间异或就是 a_r \oplus a_{l-1}，问题转化为求前 k 大的异或对 (a_i,a_j)，其中 0 \le i<j\le n。

用三元组 (l,r,x) 表示左端点在 [l,r] 之间，右端点在 x 位置时的最大值，使用 P4735 的可持久化 01-Trie 可以求出这个值。

类似超级钢琴，我们分裂区间进行转移。在第 l-1,r 棵 01-Trie 上同步二分，找到 a_x \oplus a_p 最大的 p \in [l,r]。这样将区间分裂为 [l,p) 和 (p,r]，可以保证最优性。复杂度 O(n \log n+k \log k)，常数较大。

:::info[代码]

const int N = 5e5 + 5;
long long n, k, a[N];

int cnt, rt[N], idx[N * 65], ch[2][N * 65], val[N * 65];
void insert(int rt, int last, int x, int id) {
    for (int i = 31; i >= 0; i--) {
        val[rt] = val[last] + 1;
        if (x >> i & 1) {
            if (!ch[1][rt]) ch[1][rt] = ++cnt;
            ch[0][rt] = ch[0][last], rt = ch[1][rt], last = ch[1][last];
        } else {
            if (!ch[0][rt]) ch[0][rt] = ++cnt;
            ch[1][rt] = ch[1][last], rt = ch[0][rt], last = ch[0][last];
        }
    } val[rt] = val[last] + 1, idx[rt] = id;
}
int ask(int rt1, int rt2, int x) {
    for (int i = 31; i >= 0; i--) {
        int d = x >> i & 1;
        if (val[ch[d ^ 1][rt1]] - val[ch[d ^ 1][rt2]]) {
            rt1 = ch[d ^ 1][rt1], rt2 = ch[d ^ 1][rt2];
        } else {
            rt1 = ch[d][rt1], rt2 = ch[d][rt2];
        }
    } return idx[rt2];
}

struct node {
    int l, r, x, p;
    node(int _l = 0, int _r = 0, int _x = 0) : l(_l), r(_r), x(_x) {
        p = ask(rt[l - 1], rt[r], a[x]);
    }
    bool operator< (const node& h) const {return (a[x] ^ a[p - 1]) < (a[h.x] ^ a[h.p - 1]);}
};
priority_queue<node> q;

void _main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i], a[i] ^= a[i - 1];
    for (int i = 1; i <= n; i++) rt[i] = ++cnt, insert(rt[i], rt[i - 1], a[i - 1], i);
    for (int i = 1; i <= n; i++) q.emplace(1, i, i);
    long long res = 0;
    while (k--) {
        int l = q.top().l, r = q.top().r, x = q.top().x, p = q.top().p;
        q.pop(), res += (a[x] ^ a[p - 1]);
        if (l < p) q.emplace(l, p - 1, x);
        if (p < r) q.emplace(p + 1, r, x);
    } cout << res;
}

:::

::::