{"problem":{"name":"「SvR-1」Five of Pentacles","description":{"content":"**请仔细阅读数据范围和时间限制。** 有一个长度为 $m$ 的数轴，一开始，处于 $1$ 时刻的**开始**，小 Z 处于 $1$ 号点，此时数轴上每个点都有一个障碍。 每个时刻，若小 Z 处于 $i$ 号点，小 Z 可以指定一个 $d \\geq 0$，然后移动到 $i + d$ 号点，并且会越过 $[i, i + d]$ 的每一个障碍。 当然，一切都是在变化的，一共会有 $k$ 次变化，","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8413"},"statements":[{"statement_type":"Markdown","content":"**请仔细阅读数据范围和时间限制。**\n\n有一个长度为 $m$ 的数轴，一开始，处于 $1$ 时刻的**开始**，小 Z 处于 $1$ 号点，此时数轴上每个点都有一个障碍。\n\n每个时刻，若小 Z 处于 $i$ 号点，小 Z 可以指定一个 $d \\geq 0$，然后移动到 $i + d$ 号点，并且会越过 $[i, i + d]$ 的每一个障碍。\n\n当然，一切都是在变化的，一共会有 $k$ 次变化，第 $i$ 次会发生如下变化：\n\n- $t_i$ 时刻内 $x_i$ 号点上的障碍将会消失。\n- **请注意，此变化仅作用于 $t_i$ 时刻**\n\n保证变化是**随时间倒序发生的**，也就是说 $t_i$ **单调不升**。\n\n现在，对于每个 $1\\le i\\le k$，你都需要输出**在前 $i$ 个变化发生的条件下**、在保证第 $n$ 个时刻结束时小 Z 恰好处于 $m$ 号点的基础上，小 Z 越过的最小障碍数。\n\n## Input\n\n**本题强制在线，同时请注意在线形式。**\n\n第一行，三个整数 $n,m,k$。\n\n接下来 $k$ 行，其中第 $i$ 行有两个数字 $t_i, p$。其中 $p$ 用于生成 $x_i$，即：$x_i = \\min(x_{i - 1} + p \\oplus (lastans \\bmod 15) + 1, m)$，其中 $lastans$ 表示上次变化的答案。\n\n**特别地，第一次变化之前 $lastans = 0$，$x_0 = 0$，且当 $x_{i - 1} = m$ 时，将 $x_{i - 1}$ 视作 $0$（注意这不会真的改变 $x_{i - 1}$ 的值）。**\n\n## Output\n\n$k$ 行，每行一个整数，表示所求的值。\n\n[samples]\n\n## Background\n\nUPD on 2023.2.5 by 出题人： 原题强制在线方式有问题，会使得一些依赖强制在线的方式通过，这并不是正解~~但是不想改了~~。\n\n## Note\n\n#### 样例解释\n\n样例解密后：\n\n```plain\n2 3 2\n2 1\n2 2\n```\n\n- 第一次变化后：小 Z 第一秒选择 $d = 0$，跨过一个障碍。第二秒选择 $d = 2$，原本跨过了 $3$ 个障碍，但是第 $2$ 秒第一个点没有障碍，所以只跨过了 $2$ 个障碍。一共 $1 + 2 = 3$ 个障碍。\n- 第二次变化后：小 Z 第一秒选择 $d = 0$，跨过一个障碍。第二秒只有第三个位置有障碍，选择 $d = 2$，所以只跨过了一个障碍。一共 $1 + 1 = 2$ 个障碍。\n\n#### 数据规模与约定\n\n**本题自动开启捆绑测试和 O2 优化。**\n\n$$\n\\newcommand{\\arraystretch}{1.5}\n\\begin{array}{c|c|c}\\hline\\hline\n\\textbf{Subtask} & \\bm{n,m,k\\le} & \\textbf{分值} \\\\\\hline\n\\textsf{1} & 100 & 15 \\\\\\hline\n\\textsf{2} & 2\\times10^3 & 20 \\\\\\hline\n\\textsf{3} & 5\\times10^4 & 20 \\\\\\hline\n\\textsf{4} & 10^6 & 20 \\\\\\hline\n\\textsf{5} & \\text{无特殊限制} & 25 \\\\\\hline\\hline\n\\end{array}\n$$\n\n对于 $100\\%$ 的数据（解密后），$1 \\leq n, m, k \\leq 2 \\times 10^6$，$1 \\leq t_i \\leq n$，$0 \\leq p \\leq 15$，$t_i$ **单调不升**，若 $t_i$ 相同，按 $x_i$ **升序**，且 $\\forall 1 \\leq i < j \\leq k$，$(t_i, x_i)$ 和 $(t_j, x_j)$ 不同。\n\n本题提供读入优化方式。\n\n使用 `read(x);` 读入一个任意的整型 `x` 等价于 `scanf(\"%d\", &x);`其中可以将 `%d` 自动识别为对应类型。\n\n```cpp\n#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)\nchar buf[1<<21],*p1=buf,*p2=buf;\ntemplate <typename T>\ninline void read(T& r) {\n\tr=0;bool w=0; char ch=getchar();\n\twhile(ch<'0'||ch>'9') w=ch=='-'?1:0,ch=getchar();\n\twhile(ch>='0'&&ch<='9') r=r*10+(ch^48), ch=getchar();\n\tr=w?-r:r;\n}\n```","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8413","tags":["动态规划 DP","线段树","树状数组","2022","洛谷原创","O2优化","洛谷月赛"],"sample_group":[["2 3 2\n2 0\n2 3","3\n2"]],"created_at":"2026-03-03 11:09:25"}}