Super Piano's Trick

· · 算法·理论

本文主要记录了由 NOI2010 超级钢琴 所引出的一类技巧的本质；不过我可能更偏向于记录其为 Shopping Plans' Tirck，因为我只在 Shopping Plans 的题解区看到了对于这一类问题最正确的解答（但可能也没有从头到尾和本质地介绍这一 trick，所以有了这篇 Blog），而 Super Piano 的题解区并没有揭示这一点。

下面我们进入正文。

一类问题

先举出一个最平凡的例子：Luogu P1631 序列合并：

给出两个单调不降的序列 \{a_n\},\{b_n\}，求出 a_i+b_j(1\le i,j\le n) 的前 n 小值。

更一般的，我们可能会要求求出前 k 大值，其中 k=\mathcal{O}(n)。

对于这一题，大多给出了如下解答：

你可能会看到题解区里给出了另一种神秘的不需要判断一个 pair 是否出现过的方法，但是我们这里先 skip 这个东西，将会在后面进行讨论。

从 k 短路说起

问题刻画

wait，先别急着学习 k 短路！

事实上我们将要讨论的东西和 【模板】k 短路 半毛钱关系都没有，你只需要假装你会做 k 短路问题即可（而且在这个部分中我们并不 care 复杂度），仅仅只是提出一种可行的方法。

并且事实上在这里和 k 短路又不太相同，我们想要的并不是 s\to t 的第 k 长路径，而想要知道的仅仅只是距离源点前 k 近的点。

批注：

注意！这里我们建出的图不一定有 |V|=\mathcal{O}(n)，而往往是 |V|=\mathcal{O}(\operatorname{poly}(n))，所以直接暴力建出整张图然后跑最短路的做法我们认为是不可以接受的！

考虑上面那个问题：我们将一个 pair (i,j) 看作是图上一个节点，然后连边 (i,j)\to (i+1,j) 和 (i,j)\to (i,j+1)，边权分别是 a_{i+1}-a_i 和 b_{j+1}-b_j，然后跑最短路，即可解决这个问题。

事实上你会惊讶地发现：其实刚才这个算法和我们最开始提出的算法是等价的！

对于任意一条边 u\to v，我们注意到有 dis_u\le dis_v，所以是一个 DAG（我们不考虑由于 dis_u=dis_v 相同导致 u\leftrightarrow v 的情况，因为这时候我们会将节点编号作为第二关键字进行比较）。

批注：

这其实是这张图特殊的部分：建出来的图是一张 DAG（并且是根据 dis 确定拓扑序的 DAG）。

对于一般图，我们根据 Dijkstra 算法取出堆的节点顺序也可以将图定向成一个 DAG（即按 dis 定向），我们称其为 最短路 DAG。

批注：

当然由于他是一个 DAG，所以你可以直接 Toposort 用 \mathcal{O}(|V|) 复杂度（视 |V| 和 |E| 同级）求出所有节点的 dis，不过我们上面提到了 |V|=\mathcal{O}(\operatorname{poly}(n))，所以这并不比我们跑 Dijkstra 然后到达 k 个节点就直接 break 要优秀（因为这样复杂度是 \mathcal{O}(k\log{n})，如果认为出边个数是 \mathcal{O}(1) 的话）。

这样子，我们就将上面这个问题转换成了这一种「k 短路问题」，看样子，我们已经得到了一个通用的做法了！

反例

考虑这样一个问题：

给出 n 个单调不降的序列 \{a_{1,l_1}\},\{a_{2,l_2}\},\cdots,\{a_{n,l_n}\}，你需要在每一个序列中恰好选取一个数，我们定义一种选取方案的价值是选的数之和，求前 k 小的价值。

为啥不行嘞？？

因为你 check 一个节点是否出现过的复杂度爆炸了，并且空间复杂度也爆炸了。

该问题会在 Shopping Plans 部分的 Part 2 部分给出解答。

「神秘的不需要判断一个节点是否出现过的做法」

那个做法大抵是说：我再往 pair 里塞一个 tag f 表示我要记录一下我之前是否移动过 j 指针，如果移动过那么我之和就再也不能移动 i 指针了。（当然我们有 f=[j=1]，所以不需要显性地记录）。

换句话说，我将 a,b 拼到一起去得到一个 2\times n 的矩阵，我会先移动第一行的指针，结束之和我再去移动第二行的。

为啥这样子是对的？？

从两点来说明：

  1. 这样子不会有取出状态的重复 or 遗漏。

    • 因为我们前面有状态重复的原因是我可能先移动了第一行的，又移动了第二行的；或者我先移动了第二行的，又移动了第一行的，而在这里后者情况不会发生，因为第一行操作必然在第二行之前。

    • 或者形式化的，我们也可以考虑构造一个状态 \leftrightarrow 操作序列的双射来说明：（我们认为操作序列是一个 01 序列，满足我移动第一行指针会在尾端加入 0 否则加入 1）

      • 操作序列 \to 状态，按照这个 01 序列的含义从左往右扫一遍模拟即可得到对应状态。

      • 状态 \to 操作序列，如果当前状态为 (i,j)，则操作序列就是前面 i-1 个 0，后面 j-1 个 1。

      • 那么我们这里的状态只可能由一种操作序列生成，并且必然会被生成，所以不会有重复。

  2. 这样子肯定不会落掉前 k 优的任何一个解。

    • 首先根据第一点，我们不会有状态丢失。

    • 在这里我们再重新回过头去看那个 k 短路的刻画方法，注意到其实源点到某个状态的真实距离不会因为图的变化而变化（只要边权和源点到某个点的可达性都是对的，这根据前面的一条说也有明），因为这个值恒为 a_i+b_j。那么如果正确性错误是什么情况呢？

    • 存在负权边。因为我们实质上是在跑一个 Dijkstra，如果有负权边我们就似了。

    • 那么有没有呢？显然是没有的。因为我们仍然有 a_{i+1}-a_i\ge0 和 b_{j+1}-b_j\ge 0。

这样子我们就严谨的说明了这一做法的正确性。

到底进行了什么优化？

在这里我们直接指出这种通用方法的本质：对于一个状态 S，我们需要构造出一个转移函数 \operatorname{trans}(S)（这大概是一个状态集合），我们连边 S\to T(T\in \operatorname{trans}(S))，要求满足：

  1. 构成一棵外向树。

  2. 外向树的根节点是最优状态（即 k=1 的答案）。

  3. 不能存在某个状态不在该树上。

  4. 我们需要有 \operatorname{value}(T)\ge \operatorname{value}(S)（\operatorname{value} 也就是这个状态对应的权值）。

    • 批注：

      需要注意的是：这里的 \ge 不一定是比较大小，而可能是题目要求的一种偏序关系，可能表示成不优于会更为准确。

而我们就是在对这个外向树去跑一个 Dijkstra。

但其实因为这个图有很好的性质，所以我们也不太算是去跑 Dijkstra，而基本上是在从上往下对着这棵树进行了一次遍历。

因为这一个性质，所以我们不需要判断一个节点是否有被重复经过（因为其必然只会被取出一次）（还会有一些其他优点），也就保证了复杂度为 \mathcal{O}(k|\operatorname{trans}(S)|\log{n})。

回顾上面那个做法：

超级钢琴

Solution

Luogu P2048 超级钢琴。

给定一个序列 \{a_n\} 和正整数 k,L,R，我们定义一个区间 [l,r] 的权值为 \sum\limits_{i=l}^r a_i。

称一个区间 [l,r] 是合法的当且仅当 L\le r-l+1\le R。

求权值前 k 小的合法区间。

将一个区间的权值刻画为前缀和：f(l,r)=pre_r-pre_{l-1}。

则对于一个 l 可以和他配对成一个合法区间的 r 需要满足的是 r\in [l+L-1,l+R-1]。

则我们去考虑记录状态为一个二元组：(i,s=[tl,tr]) 表示我考虑了所有 l=i 和 r\in s 的区间。但是其实这个定义有些问题：根据上面提到的这个算法，我需要保证每个状态都有一个「权值」，那这里权值是啥呢？？？

这时候，我们要引入「决策」的定义：

那么我们的一个「状态」就可以视作是若干个「决策」的集合。

在本题中，我们的一个状态 (i,s=[tl,tr]) 就是所有满足 l=i 和 r\in s 的决策构成的集合。

而一个「决策」显然是有明确的权值定义的（在本题中就是 pre_r-pre_{l-1}）。

则我们令一个状态的定义就是其包含的所有决策中的最小权值。

接下来考虑构造 \operatorname{trans}(S)：

实际上我们画出转移树，其实一个外向树森林（每个 (i,[i+L-1,i+R-1]) 都是一棵外向树的根）。

批注：

我们不妨建一个超级源点连向所有外向树的根，超级源点的权值可以视作所有根的最小权值，这样子也就符合上面的理论了。

关于其正确性说明：对应上面的 2,3,4 条件是显然的，考虑条件 1：

那么得到算法流程：

  1. 取出堆中的最优状态 (i,s=[tl,tr])。

  2. 找到其得到其最小权值的取值点 r=p，得到对应决策为 [l,r]=[i,p]，输出该决策的值 pre_p-pre_{i-1}。

  3. 得到两个新的状态 (i,t_1=[tl,p)) 和 (i,t_2=(p,tr])，将其丢入堆中。

由于 |\operatorname{trans}(S)|=\mathcal{O}(1)，所以复杂度为 \mathcal{O}(k\log{n})。

状态？决策？

我们注意到在上面这个问题中我们又引入了一个「决策」的定义，这在我们最开始提出的理论和序列合并的问题当中是不存在的，这是什么原因？？

实际上在序列合并的问题中，我们令一个 (i,j) 表示我们选取了 a_i+b_j 是不合适的，更正确的表达应当是：(i,j) 这个状态表示了所有满足 i'\ge i,j'\ge j 的决策 (i',j') 构成的集合！

而显然在这些决策中 (i',j')=(i,j) 就是最优秀的那个，所以我们直接令 a_i+b_j 为这个决策的权值。

根据这一点，我们需要再将该做法成立的条件加上第 5 条：

  1. 一个状态需要唯一对应一种决策，一种决策也唯一对应一种状态。且该状态对应的决策是其表示的决策集合中权值最小的那一个，我们令该决策的权值为该状态的权值。

另一种判定方法

设状态 S 所包含的决策集合为 A_S，对应的最优决策为 x，则我们应有：

A_S=\left(\bigcup_{T\subseteq \operatorname{trans}(S)} A_T \right)\cup x

并且对于任意 T\subseteq \operatorname{trans}(S) 应不存在 T'\subseteq (\operatorname{trans}(S)\setminus T) 使得 A_T\cap A_{T'}\ne \emptyset。

满足上面两个条件的转移函数 \operatorname{trans}(S) 就是合法的。

Shopping Plans

Luogu P6646 Shopping Plans。

Part 1

给定 n 个物品和两个正整数 m,k，每个物品有一个权值 c_i，我们定义一个集合 S 的权值是 \sum\limits_{x\in S}c_x，称一个集合是合法的当且仅当 |S|=m。

求权值前 k 小的集合，输出其权值。

先将物品按权值从小到大排序。

我们认为一个决策就是题目里一个合法的集合 S'=\{q_m\}，或者我们在本题中会将其看作一个序列满足 \forall i\in[1,n),q_i<q_{i+1}。

则一个状态 S=\{p_m\} 表示的是所有满足 q_1\ge p_1,q_2\ge p_2,\cdots q_m\ge p_m 的决策。

则该状态对应的最优决策显然就是 S'=S。

我们考虑从右往左依次去移动指针。记 (i,p_{i+1\sim m}) 表示的是状态 S=\{1,2,\cdots,i,p_{i+1},\cdots,p_{m}\}。

从这个状态考虑去构造转移函数：\operatorname{trans}(S)=\{(i-1,\operatorname{merge}(x,p_{i+1\sim m})\mid i\le x<p_{i+1}\}。其中 \operatorname{merge} 表示的是令 p_i\gets x 然后得到序列 p_{i\sim m}。

连边 S\to T(T\in \operatorname{trans}(S))，容易说明我们得到是一个外向树并且其于 2,3,4,5 条件同样显然满足要求，这里不再赘述。

进一步地，我们发现其实我们完全没有必要记录 p_{i+1\sim m} 的全部状态，有无我们确定 p_i 取值时只关心 p_{i+1} 的值！所以我们可以之间将状态压缩为 (i,j) 表示 p_{i+1\sim m} 已经确定并且 p_{i+1}=j。

批注：

注意！可能这里叫「压缩」不是很准确！

因为我们不一定只有一个 (i,j)，但是每个 (i,j) 对应的实际状态肯定都是不同的。

或者说可能我在这里仅仅只是在 pair 里面少保存了一些无用信息以优化空间复杂度。

而如果真把这个当作一个全新的状态定义，然后按转移函数连边 (i,j)\to (i-1,x) 然后做 Dijkstra，那就错完了！因为如果真要这样子搞，建出来的图显然不是一棵外向树！

我们仍然是在对最开始的树进行 Dijkstra，只不过是一个节点的信息变少了（正因为他是一棵树我们才可以这样做），而下面也将这个节点（状态）简记成他所要保留的信息。

所以我们取出一个状态 (i,j) 时，我们会丢进去一个 (i-1,x)（需要满足 i\le x<j），而转移边权是 c_x-c_i。

由于 |\operatorname{trans}(S)|=\mathcal{O}(n)，所以复杂度即为 \mathcal{O}(kn\log{n})。

虽然我们得到了 \mathcal{O}(\operatorname{poly}(n)) 复杂度（忽略 \operatorname{polylog} 因子），但是还是太慢了，我们并不满足！

考虑慢在了哪里：|\operatorname{trans}(S)| 太大了！

考虑优化：注意到我们的转移大概是这样子：

我们将所有儿子按权值大小排序，断掉除了最小的儿子到父亲的边，然后再依次将儿子们之间连边，像这样：

显然我们这样子建图后的转移仍然是符合要求的，而这样子我们将 |\operatorname{trans}(S)| 降到了 \mathcal{O}(1) 级别，复杂度也就降到了 \mathcal{O}(k\log{n})。

实际上这就是所谓的「多叉树转二叉树」（或者可能和「前缀优化建图」差不多？）。

在原问题中表现出来就是原来转移是一口气挪到，现在是一步一步挪过去。

形式上，我们改 (i,j) 为 (i,k,j) 表示当前 p_i=k,p_{i+1}=j，我们可以进行如下转移：

Part 1 Extend

给定 n 个物品和两个正整数 l,r,k，每个物品有一个权值 c_i，我们定义一个集合 S 的权值是 \sum\limits_{x\in S}c_x，称一个集合是合法的当且仅当 l\le |S|\le r。

求权值前 k 小的集合，输出其权值。

这也就是说集合的大小是不确定的。

事实上处理是简单的。

一个无脑的方法是我初始时把所有 (i,i,n+1) 给丢进去（l\le i\le r），然后再进行 Part 1 的算法即可；这样子当然没有问题，但是当我们要解决整个 Shopping plans 的问题时是不支持初始时把所有状态全部丢进去的，原因是初始化复杂度爆炸了。

进一步分析，如果我们建一个超级源点连向所有 (i,i,n+1)，那其实本质上就是 |\operatorname{trans}(S)| 太大，我们这里仍然可以套用上面「多叉树转二叉树」的做法来解决这个问题。

具体的，我们认为状态 (i,i,n+1) 可以转移到 (i+1,i+1,n+1)，而最初只有 (l,l,n+1) 被丢进堆中。

复杂度仍然是 \mathcal{O}(k\log{n})。

Part 2

给定 n 个物品，每个物品有种类 a_i 和权值 c_i。

你需要对于每个种类恰好选择一个物品，一种选取方案的权值是选取物品权值之和。

求权值前 k 小的方案，输出其权值。

做法和 Part 1 整体思想大差不差。

将相同种类的物品丢到同一行，将同一行按 c_i 进行排序。然后我们会发现这个问题其实就是我们在 k 短路部分中给出的「反例」。

首先最优状态肯定是每一行都选最小的那个数；考虑转移那么我们就要将每一行的指针向后挪，记 S=(i,p_{1\sim i-1}) 表示的是我当前考虑到第 i 行，前面 i-1 指针的信息是 p_{1\sim i-1}，我们容易给出转移函数：

这里大概意思就是令 p_i\gets k，然后 skip 了第 i+1\sim j-1 这些行（也就是让他们的 p=1 了）。

注意到我们在这里并不关心 p 的信息，所以舍去即可，不进行保存。

这样子 |\operatorname{trans}(S)|=\mathcal{O}(n^2)，所以复杂度是 \mathcal{O}(kn^2\log{n}) 的。

考虑优化，我们对 j,k 分别做「多叉树转二叉树」的优化即可，即可将 |\operatorname{trans}(S)| 降到 \mathcal{O}(1)。

对于 k 的优化和 Part 1 几乎一模一样，这里舍去。

对于 j 的优化其实也差不多，但是请注意：我们做这个优化的前提条件是要按儿子权值排序（在前面没有显示出来的原因是我们将 c 按升序排序，所以不需要额外考虑），但是在这里我们要将所有行按 c_{i,2}-c_{i,1} 排序（具体为什么请读者手推一下以增强印象）。

这里给出最终的转移（我们定义 (i,j) 表示当前考虑到了第 i 行，第 i 行的指针被挪到了第 j 位的权值）。

具体推导留给读者。

这样子我们将这个 Part 做到了 \mathcal{O}(k\log{n})。

Full Solution

有 n 个物品，每个物品有种类 a_i 和权值 c_i。

对于第 i 类物品，必须选取 [l_i,r_i] 个物品。

求出权值前 k 的方案对应的权值。

我们发现：其实 Part 1 Extend 就是 m=1 的情况，Part 2 就是 l_i=r_i=1。

我们基于 Part 1 Extend 和 Part 2 给出该题的完整做法。

我们将第 i 行序列的定义改写为：第 j 个位置是在这一行中选取 [l_i,r_i] 个物品第 j 小权值，即我们令 c_{i,j} 为这个值。这里可以用 Part 1 Extend 的做法解决。

这样子我们会得到一个全新的矩阵，我们对着这个东西做 Part 2 即可。

更具体地，我们将每一行看作一个独立的「问题」，我们对于每个「问题」去封装一个「黑盒」，我喂给这个「黑盒」一个数 k 他就会给我返回关于这个「问题」第 k 小的权值。

我们用 Part 2 的算法去跑这个问题，就是要对于每一行快速获知其第 j 小的权值，我们向这个「黑盒」询问即可。

复杂度均摊是 \mathcal{O}(k\log{n}) 的。

给出代码可能会清晰很多：

#include<bits/stdc++.h>
//#pragma GCC optimize(3,"Ofast","inline")
#define int long long
#define i128 __int128
#define ll long long
#define ull unsigned long long
#define ld double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
//  system("fc .out .ans");
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}
bool M1;
const int N=2e5+5;
struct solve_line {
    struct node {
        int x,y,z,val;
        bool operator < (const node &tmp) const {
            return val>tmp.val;
        }
    };
    priority_queue<node> heap;
    vector<int> vec,ans;
    int l,r,k;
    void ins(int x) {
        vec.push_back(x);
    }
    int get(int p) {
        if(p<(int)ans.size())
            return ans[p];
        while(p>=(int)ans.size()) {
            if(heap.empty())
                return INFLL;
            node tmp=heap.top(); heap.pop();
            int x=tmp.x,y=tmp.y,z=tmp.z,val=tmp.val;        
            ans.push_back(val);
            if(y>=0&&y+1<=z)
                heap.push({x,y+1,z,val+vec[y+1]-vec[y]});
            if(x>=0&&x+1<=y-1)
                heap.push({x-1,x+1,y-1,val+vec[x+1]-vec[x]});
            if(z==(int)vec.size()-1&&x+1==y&&y+1<r)
                heap.push({x+1,y+1,z,val+vec[y+1]});
        }
        return ans[p];
    }
    void init() {
        sort(vec.begin(),vec.end());
        if((int)vec.size()<l) {
            ans.push_back(INFLL);
            return;
        }
        int tot=0;
        rep(i,0,l-1)
            tot+=vec[i];
        chkmin(r,(int)vec.size());
        heap.push({l-2,l-1,(int)vec.size()-1,tot});
    }
}; solve_line a[N];
struct node {
    int val,x,y;
    bool operator < (const node &tmp) const {
        return val>tmp.val;
    }
};
int p[N];
void solve() {
    int n,m,k;
    scanf("%lld%lld%lld",&n,&m,&k);
    while(n--) {
        int x,y;
        scanf("%lld%lld",&x,&y);
        a[x].ins(y);
    }
    int tot=0;
    rep(i,1,m) {
        p[i]=a[i].k=i;
        scanf("%lld%lld",&a[i].l,&a[i].r);
        a[i].init();
        int val=a[i].get(0);
        if(val>=INFLL) {
            while(k--)
                puts("-1");
            return;
        }
        tot+=val;
    }
    printf("%lld\n",tot);
    sort(p+1,p+m+1,[](const int &x,const int &y) {
        return a[x].get(1)-a[x].get(0)<a[y].get(1)-a[y].get(0);
    });
    priority_queue<node> heap;
    heap.push({tot+a[p[1]].get(1)-a[p[1]].get(0),1,1});
    while(--k) {
        node tmp=heap.top(); heap.pop();
        int ans=tmp.val,x=tmp.x,y=tmp.y;
        if(ans>=INFLL) {
            puts("-1");
            continue;
        }
        printf("%lld\n",ans);
        heap.push({ans+a[p[x]].get(y+1)-a[p[x]].get(y),x,y+1});
        if(x+1<=m)
            heap.push({ans+a[p[x+1]].get(1)-a[p[x+1]].get(0),x+1,1});
        if(x+1<=m&&y==1)
            heap.push({ans-(a[p[x]].get(1)-a[p[x]].get(0))+a[p[x+1]].get(1)-a[p[x+1]].get(0),x+1,1});
    }
}
bool M2;
signed main() {
//  file_IO();
    int testcase=1;
    //scanf("%d",&testcase);
    while(testcase--)
        solve();
    fprintf(stderr,"used time = %ldms\n",1000*clock()/CLOCKS_PER_SEC);
    fprintf(stderr,"used memory = %lldMB\n",(&M2-&M1)/1024/1024);
    return 0;
}

需要注意的是，代码一些状态定义可能会和上面说的有一些细小区别（包括一些 corner case 的处理，还有每一行的下标从 0 开始，以及在 Part 1 部分中的一些 < 和 \le 的区别等等），因为当时写这份代码是看 这个题解 的。