2020-2021:teams:intrepidsword:ru-winter-camp-2015-saratov-su
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:intrepidsword:ru-winter-camp-2015-saratov-su [2020/07/24 16:23] chielo [A. Three Servers] |
2020-2021:teams:intrepidsword:ru-winter-camp-2015-saratov-su [2020/07/24 16:35] (当前版本) chielo [I. Archaeological Research] |
||
|---|---|---|---|
| 行 137: | 行 137: | ||
| ===== I. Archaeological Research ===== | ===== I. Archaeological Research ===== | ||
| - | **题目大意**： | + | **题目大意**：现在有一个长度为 $n$ 的序列，知道从某个位置开始，到另外某个位置上会出现一个新的值。要你恢复出来字典序最小的序列。 |
| **题解**： | **题解**： | ||
| + | |||
| + | 不考虑字典序最小，$1, 2, 3, \ldots$ 就是符合条件的答案，因此绝对有解。 | ||
| + | |||
| + | 显然，对于第 $i$ 个元素，如果表示它是从 $l_j$ 开始的一个新的值，那么它取没有出现在这些值中的最小值即可。（我一开始想成最大的，表示 max，队友听，mex，好呀） | ||
| + | |||
| + | 离线没修改的区间 mex，记当前我们处理到了第 $i$ 个元素，记录一下元素值为 $key$，在 $i$ 之前、离 $i$ 最近的出现的位置 $value$。想求的是 $l_j$ 到 $i$ 之间，没有出现过的最小的元素值，考虑从小到大枚举这个元素值，一旦遇到一个元素值最近出现的位置比 $l_j$ 小，那就是它了。 | ||
| + | |||
| + | 所以用线段树维护一下元素值在相应区间中，最近出现的位置的最小值即可。查询的过程也就是看左子树是不是有符合条件、即区间内没有出现过的元素值，没有就走右子树。 | ||
| ===== J. Sockets ===== | ===== J. Sockets ===== | ||
2020-2021/teams/intrepidsword/ru-winter-camp-2015-saratov-su.1595579027.txt.gz · 最后更改: 2020/07/24 16:23 由 chielo
