题意题意
你吃过蘸蔓越莓酱的肉丸吗?科斯嘉简直爱不释手,尤其是在深夜解题时。实际上,他在电脑前吃得太投入:一些蔓越莓酱从罐子里滴出来,弄坏了他的键盘。但他还得继续解题。而且,他可不想像键盘那样被卡住!
科斯嘉使用的代码文件包含 \(n\) 行,编号从 \(1\) 到 \(n\),其中第 \(i\) 行包含 \(s_i\) 个光标位置,从 \((i,1)\) 到 \((i,s_i)\),将第 \(i\) 行第 \(j\) 个位置记作 \((i,j)\)。
在部分按键损坏的情况下进行代码导航有点棘手。幸运的是,科斯嘉的向上和向右箭头仍能使用:
- 向上键 \((\uparrow)\):若光标位于位置 \((i,j)\),如果 \(i=1\),光标保持原位;否则移动到位置 \((i-1, \min(j, s_{i-1}))\),其中 \(s_{i-1}\) 是第 \(i-1\) 行的长度。
- 向右键 \((\rightarrow)\):若光标位于位置 \((i,j)\),如果 \(j<s_i\),光标移动到 \((i,j+1)\);否则移动到 \((i+1,1)\);但在位置 \((n,s_n)\) 时保持不动。
科斯嘉有个特殊技巧:他选择一个初始光标位置,开始执行无限次按键操作:先按 \(u\) 次向上键,接着按 \(r\) 次向右键,如此循环往复。
例如,设 \(n=5, u=2, r=5, s=\{5,2,4,3,1\}\)。从位置 \((4,3)\) 开始,前几次按键操作的光标移动轨迹如下:
\((4,3)\uparrow(3,3)\uparrow(2,2)\rightarrow(3,1)\rightarrow(3,2)\rightarrow(3,3)\rightarrow(3,4)\rightarrow(4,1)\dots\)
如果一个起始位置能通过执行此无限序列,使光标最终抵达第一行,则称该位置是成功的。
你的任务是帮助科斯嘉计算代码文件中存在多少个成功的起始位置。
由于他的代码尚未完成,你还需要处理 \(q\) 次更新。每次更新会给出两个值 \(pos\) 和 \(x\),你需要将 \(s_{pos}\) 重新赋值为 \(x\)。请输出在初始状态及每次更新后的问题答案。
形式化题意
对于一个长度为 \(n\) 的正整数序列 \(\{s\}_{i=1}^{n}\),定义
对于一个 \((x,y)\in S\),定义
再有两个正整数 \(u,r\),定义
令
对于给定序列 \(\{s\}_{i=1}^{n}\),及正整数 \(n,u,r\),令
还有 \(q\) 个正整数对 \(\{(\mathrm{pos}_i,x_i)\}_{i=1}^{q}\),令
给了你 \(n,u,r,s^{(0)}\),你需要对于 \(v=0\dots q\),计算出
solution
结论1:答案具有单调性,即证:
对于 \((x_1,y_1),(x_2,y_2)\in S\),若 \((x_1,y_1) \le (x_2,y_2)\Leftrightarrow x_1<x_2\lor(x_1=x_2 \land y_1\le y_2),(x_2,y_2)\in S_{\text{Good}}\to(x_1,y_1) \in S_{\text{Good}}\)。
证
首先显然 \(\uparrow(x_1,y_1)\le\uparrow(x_2,y_2),\rightarrow(x_1,y_1)\le\rightarrow(x_2,y_2)\)。
于是 \(a_t(x_1,y_1) \le a_t(x_2,y_2)\),又 \(\exists t \in \mathbb{N},a_t(x_2,y_2)\in\{(i,j)\in S:i=1\}\),于是对于某个 \(j\),\(a_t(x_1,y_1) \le (1,j)\),得证。
结论2:\({\exists p \le n,p\in \mathbb{Z}_{+},S_{\text{good}}=\{(i,j)\in S:i \le p\}}\)
证
只需证明 \(\forall i \le n,j_1,j_2 \le s_i,i,j_1,j_2 \in\mathbb{Z}_+,(i,j_1)\in S_{\text{good}}\to (i,j_2)\in S_{\text{good}}\) 即可。
考虑数学