2023 CCPC Qinhuangdao
本质不同子序列数的求法 III：Link。
令 $sol(a, b, m_0, m_1)$ 为答案矩阵，其中 $m_0, m_1$ 是 $0$ 和 $1$ 的转移矩阵，那么有
$$
sol(a, b, m_0, m_1)=
\begin{cases}
m_0^a & b = 0\\
sol\left(a, b \bmod a, m_0\cdot m_1^{b/a}, m_1\right) & b\ge a\\
sol\left(a - ((a - 1) / b) \cdot b, b, m_0, m_1\cdot m_0^{(a-1)/b}\right) & a>b\\
\end{cases}
$$
递归解决即得答案。
题意
给定一个长为 $n$ 的序列和整数 $k$，要求支持 $m$ 次操作：
1.将当前最大的数减去 $k$，重复 $t$ 次；
2. 查询当前序列的第 $x$ 大的数。
数据范围：$1\le n,m\le 5\times 10^5$，$1\le a_i,k,t\le 10^{18}$，保证时刻有 $-10^{18}\le a_i\le 10^{18}$。
题解
将每个数 $x$ 转化为一个二元组 $\left(\left\lfloor \dfrac xk\right\rfloor, x\bmod k \right)$，那么修改操作就是在进行最靠右的列的分割与合并，可以用线段树分裂合并维护。
考虑更简单的做法，用一个值域线段树维护最右的列，用指针 $p$ 指向当前最右的列中分裂到哪个位置了，每次修改会将指针向下移动，扫过的元素理应从这颗线段树中删除，不能保证复杂度。考虑把下一列的元素插进这颗线段树，不过每次二分第 $k$ 大要从 $p$ 开始。这样，当 $p$ 行进到底端时线段树上留有的元素就是下一列的元素，只需再把 $p$ 重置即可。