P8150 再会 | Sayounara
题目背景
「过去的都已经无所谓了吗？」
“还没有达到那种地步。”
「想做的事都已经完成了吗？」
“如今的自己，也好像只能在取舍中前行。”
「道过再会了吗？」
“… 还没有，但我正尝试着。”
> I have
>
> 我仍有
>
> plenty want to say
>
> 无数未道尽的言语
>
> Before
>
> 在离开之前
>
> I leave this world
>
> 在再会之前
题目描述
「这是…？」
“啊… 我自己写的日记管理程序。”
「噗… ‘正常人谁写日记啊’，平时的你应该会这样说吧？」
“… 别拿我说笑。”
「好吧好吧。不过看上去你不记得密码了呢？」
“…… 我自有手段。”
「咦…？这什么，恢复软件吗？」
“嗯… 密码可以被表示为一个长为 $n$ 的非负整数序列，**其中每个元素都互不相同** 。这个软件可以执行两种操作：一是，询问一个连续区间的总和减去这个区间最小值的结果；二是，询问一个位置的值。现在我需要找回密码的话…”
「欸？为什么不直接用 $n$ 次第二种操作呢？」
“这是试用版… 所以第二种操作只有两次使用的体验权限… 而且第一种操作似乎也有一定的限制，所以…”
「这… 话说为什么恢复个密码这么麻烦啊？不应该会有‘找回密码’之类方便的机制吗？」
“… 多半还是那个人的安排吧。”
### 简要题意
有一个元素互不相同的非负整数序列 $a$，其长度为 $n$。你可以多次进行以下两种询问之一：
- 给出 $l,r$，得到 $\left(\sum_{k=l}^r a_k\right)-\left(\min_{k=l}^r a_k\right)$。
- 给出 $k$，得到 $a_k$ 的值。这种询问最多只能进行两次。
你需要在尽可能少的询问次数内推断出该序列的内容。
**本题询问均以 $1$ 为初始下标，但你返回答案时需要返回以 $0$ 为初始下标的 `vector`，请留意。**
### 交互说明
本题仅限 C++11 / C++17 提交。你需要实现以下的函数：
```cpp
#include
#include
std::vector recover(int n);
```
该函数接收密码长度 $n$，返回还原的密码（返回值应该是一个大小为 $n$ 的 `vector`）。你可以使用以下两个函数
```cpp
#include
uint64_t query(int l, int r);
uint32_t get(int x);
```
其中 `query` 对应题目中的第一种操作，`get` 对应题目中的第二种操作。
下面是一个示例程序（仅演示交互库操作）：
```cpp
#include
#include
uint64_t query(int l, int r);
uint32_t get(int x);
std::vector recover(int n) {
std::vector ans(n);
int what = query(1, n), hey = get(1);
for (int i = 0; i < n; ++i) ans[i] = i + 1;
return ans;
}
```
题目提供了示例交互库 `lib.cpp`（并非交互库真实实现）。你可以在本地使用命令 `g++ -o code code.cpp lib.cpp` 来编译运行。
输入格式
无
输出格式
无
说明/提示
### 得分细则
本题没有子任务。所有测试点保证 $n=10^6$。
如果你在任何一个测试点中答案错误或超出询问限制，则本题你会得到 0 分的好成绩。
如果你成功通过了所有测试点，记你在所有数据中调用操作一最多一次的次数为 $x$，则你本题的分数为：
$$
\begin{cases}
\frac{60}{e^7-1}\left(e^{10-\max\left\{\frac{x-10^6}{100},3\right\}}-1\right)+40,&x\le 1001000\\
25,&\mathrm{otherwise.}
\end{cases}
$$