在家打的，打的不是很专心，因此结果也没有多好。

赛后做了一下 C 题，难，但是的确没有以往的难，确实感觉整体难度略简单于往年的 NOI D1 。

出的很好，下次继续出QMQ。

A

发现决策单调性直接上分治了QAQ。

题解的凸包做法是真的神仙，确实没有想到QAQ。

都怪分治惯坏我了QAQ。

双指针法和凸包还能这么用，长见识了QAQ。

时间复杂度：$O(n\log{n})$

B

维护一下最小值次小值最大值次大值的位置下标即可。

1操作使用次数：2

2操作使用次数：2n-5

时间复杂度：$O(n)$

C

暂时还不会QAQ。

现在会了。

时间复杂度往大了算很大，但是常数足够小，最后 2ms 通过，这句话为什么这么熟悉？没错，我的做法是数位 DP ，辣个经常出现常数小跑不满这句话的算法。

首先，这道题目用到的 trick 是一个经典 trick 的加强版，有这么一个经典的 trick ，$x$ 的数位和和 $x$ 关于 $9$ 同余，而这道题目的 trick 更强，是 $x$ 从低位到高位每隔 $k$ 个数字划段，然后加起来得到类数位和，这个和与 $x$ 关于 $10^k-1$ 同余 。

所以我们只要求出第 $n$ 个模 $10^k-1$ 等于 $0$ 且十进制表示不包含 $9$ 的数字即可。（注意：为了下面方便讲解以及方便代码好写， $0$ 也算是合法的）

到此为止，这道题目最关键的第一步已经讲完了，但是还有至关重要的第二步QAQ。

显然，我们不可能直接维护模 $10^k-1$ 的值，这个太大，我们维护不了，因此考虑用上面的 $trick$ 分段维护，那么最多会分多少段呢？

可以发现，有 $t$ 段的时候 ，去掉模的限制，合法的数字个数有：$9^{kt}$ ，但是如果加上模的限制呢？我们能不能用最后一段专门来修正模数来让模数等于 $0$ 呢？不行，可以发现还差一点点，因此要用两段，根据计算，如果 $(t-2)k≥19$ 就 100% 能得到结果，因此我们就得到了段数的数量级。

接着考虑，现在就是要求有多少个加起来模 $10^k-1$ 等于 $0$ 的数字，可以发现，由于段数不多，因此，所得到的最终结果也是有限个的，最多 $t+1$ 个（包括 $0$ ，其实可以更小，但是懒得想了），直接暴力枚举结果是哪个即可，现在就不用维护余数了，变成维护和了，难度就小了很多了，直接所有段从低位到高位数位DP转移枚举一下就行了，然后就能在能接受的复杂度内解决个数问题了。

解决个数问题后，直接从高位到低位枚举每一位是啥就行了。

时间复杂度：$O(玄学)$ ，实际表现：$O(神奇)$ 。（其实应该可以算出具体复杂度，但是我懒，保守估计一下上界应该在两亿，是完全能过的，除非常数大，但是常数小）

很有趣的一道数位 DP 题。

还是想了我挺久的，赛时如果有其他题就不要硬啃这道题目了。

很有趣的比赛，下次如果没有意外的话还打QMQ。

PR4 还是保持了以往 PR 一样的高质量，感谢组织方给我们 Oier 带来了多场高质量的比赛，感谢。

但是TM难是真的难，艹，让我又一次意识到了自己的实力不足QAQ