趣味转置原理

给定长 $n$ 数列 $a_1,\dots,a_n$，你需要维护 $b_i$，初始为 $\max_{1\le j\le i}a_j$，支持两种操作：

1. 给定 $l,r,x$ 将 $a_l\sim a_r$ 加上 $x$；
2. 给定 $x$ 求 $b_x$。

每次操作后将每个 $b_i$ 改为 $\min\Big(b_i,\max_{1\le j\le i}a_j\Big)$，数据范围 $n,q\le5\times10^5$，**强制在线**。

相信大家很熟悉 $+,\times$ 矩阵的转置原理，这个题我们考虑 $\min,+$ 矩阵的转置原理。

设第 $i$ 次询问的答案为 $c_i$，将问题转述为：输入一维向量 $x$，输出 $q$ 维向量 $c_i+x$，这个问题的矩阵形式是

$$\begin{bmatrix}c_1\\c_2\\\vdots\\c_q\end{bmatrix}\begin{bmatrix}x\end{bmatrix}=\begin{bmatrix}c_1+x\\c_2+x\\\vdots\\c_q+x\end{bmatrix}$$

考虑其转置问题，输入 $w_1,w_2,\dots,w_q$，输出：

$$\begin{bmatrix}c_1&c_2&\cdots&c_q\end{bmatrix}\begin{bmatrix}w_1\\w_2\\\vdots\\w_q\end{bmatrix}=\min\{c_1+w_1,c_2+w_2,\dots,c_q+w_q\}$$

设 $a_{t,i}$ 为 $t$ 次操作后 $a_i$ 的值，设第 $i$ 次查询的参数是 $t_k$ 时间 $x_k$ 位置，则我们要求出：

$$\min_{1\le k\le q}\left\{w_k+\min_{0\le i\le t_k}\max_{1\le j\le x_k}a_{i,j}\right\}$$

我们交换顺序：

$$\min_{0\le i\le m}\min_{1\le k\le q,t_k\ge i}w_k+\max_{1\le j\le x_k}a_{i,j}$$

再次交换顺序：

$$\min_{0\le i\le m}\left(\min_{1\le x\le n}\left(\min_{1\le k\le q,t_k\ge i,x_k=x}w_k+\max_{1\le j\le x}a_{i,j}\right)\right)$$

倒着扫描 $i$，维护 $y_x=\min_{1\le k\le q,t_k\ge i,x_k=x}w_k$，只需要查询 $y_x+\max_{1\le j\le x}a_{i,j}$ 的最小值，需要支持对 $y$ 单点加，对 $a$ 区间加，单侧递归线段树即可做到 $O((n+m)\log^2n)$，可以通过此题。

欸等等，这题不是要强制在线吗？$i$ 从 $m$ 到 $0$ 咋办呢。

不要紧我们把这个算法转置一下，现在 $i$ 变成从 $0$ 到 $m$ 了 [续标识]