P4425 [HNOI/AHOI2018]转盘

P4425 [HNOI/AHOI2018]转盘

这次算是对楼房重建问题有一个初步理解了。大体就是先处理一个区间对另一个区间的影响，再处理另一个区间的影响。对于这个题：

\[\displaystyle \begin{array}{l} \textbf{def:} \ \text{ask} (node, val) \\ \qquad \textbf{if} \ (node \ \text{is leafy node}) \\ \qquad \qquad \textbf{return} \ [t[node].maxn > val] * inf + val + t[node].l \\ \qquad \textbf{else} \\ \qquad \qquad \textbf{if} \ (t[node << 1 | 1].maxn > val) \\ \qquad \qquad \qquad \textbf{return} \ \min(\text{ask}(node << 1 | 1, val), t[node].tr) \\ \qquad \qquad \textbf{else} \\ \qquad \qquad \qquad \textbf{return} \ \text{ask}(node << 1, val) \\ \qquad \qquad \textbf{endif.} \\ \qquad \textbf{endif.} \\ \textbf{enddef.} \end{array} \]

就是维护一个后缀单调栈。复杂度 \(O(n \log^2n)\)

下面是这个题的推式子。

---

可以发现，这个题就是先在某个地方停一会，然后不停下脚步走一圈。先断开环转化为 \(2N\)。

那么考虑对于一个地方 \(i\) 其出现时间为 \(t_i\)。假定从 \(j\) 出发，在 \(j\) 停下时间至少为 \(t_i - (i - j)\) 那么答案就是 \(\displaystyle \min_{j=1}^N\{ \max_{i=j}^{j+N-1}\{ t_i - i \} + j\} + N - 1\) 。\(N-1\) 是走完这一圈。

考虑 \(t_i = t_{i+N}\) 且 \(i \lt i+N\) 所以 \(t_i - i \gt t_{i+N} - (i+N)\) 。那么转化为 \(\displaystyle \min_{j=1}^N\{ \max_{i=j}^{2N}\{ t_i - i \} + j\} + N - 1\)。

可以发现，对于 \(t_i - i\) 固定，直到前面一个大于它的 \(t_j - j\)，答案永远由他决定，且答案为 \(t_i - i + j + 1\)。所以我们可以考虑单调栈维护 \(t_i - i\)。

假定单调栈元素为 \(st_i\)，设 \(st_0 = 0\)，\(st_{bound-1} \lt N \le st_{bound}\)。

\(\displaystyle ans = \min_{i=1}^{bound}(t_{st_i}- st_i + st_{i-1}) + N\) 这题就维护一下 \(t_i-i\) 的单调栈就好了。

因为 \(i \lt bound\) 时 \(st_{i} \gt N\) 所以，这些最大值就是 \([1, N]\) 里的最大值 \(-N\)。所以只需要维护 \([1, N]\)。最后在 \([1, N]\) 上二分到位置之后加上长度就完了。

/*
    Name:
    Author: Gensokyo_Alice
    Date:
    Description:
*/
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include