{"problem":{"name":"[WC/CTS2023] 楼梯","description":{"content":"我们首先给出一些关于楼梯的形式定义。 我们称一对正整数组成的二元组 $(x,y)$ 为**格子**，称格子构成的集合 $L$（可以为空）为**楼梯**当且仅当其满足下面两个条件： + 若 $(x,y)\\in L$ 且 $x>1$，则 $(x-1,y)\\in L$。 + 若 $(x,y)\\in L$ 且 $y>1$，则 $(x,y-1)\\in L$。 对于一个楼梯 $L$ 和 $(x,y)\\i","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9073"},"statements":[{"statement_type":"Markdown","content":"我们首先给出一些关于楼梯的形式定义。\n\n我们称一对正整数组成的二元组 $(x,y)$ 为**格子**，称格子构成的集合 $L$（可以为空）为**楼梯**当且仅当其满足下面两个条件：\n\n+ 若 $(x,y)\\in L$ 且 $x>1$，则 $(x-1,y)\\in L$。\n+ 若 $(x,y)\\in L$ 且 $y>1$，则 $(x,y-1)\\in L$。\n\n对于一个楼梯 $L$ 和 $(x,y)\\in L$，我们定义 $(x,y)$ 为**生成格**生成的**子楼梯**为\n\n$$\n\\{(a-x+1, b-y+1) \\mid (a,b) \\in L, a \\ge x, b \\ge y\\}\n$$\n\n容易证明这一集合仍然是一个楼梯。对于一个楼梯 $L$，我们定义**边界格数**为满足 $x=1$ 或 $y=1$ 的 $(x,y) \\in L$ 的数量。\n\n为了方便理解，我们接下来给出直观解释。我们在平面上可以将所有格子按从左到右 $y$ 坐标递增、从上到下 $x$ 坐标递增的顺序排列成网格，因此我们也称 $(x,y)$ 为第 $x$ 行第 $y$ 列的格子。\n\n在这一解释下，若一个格子属于某个楼梯，且它上方和左方不是边界，则对应格子也属于这个楼梯。子楼梯就是生成格右下方区域格子所构成的非空楼梯，一个楼梯的边界格数是上边界或左边界上的总格数。\n\n如下图，$(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(4,1),(5,1)$ 组成了一个合法的楼梯。这一楼梯的边界格数为 $8$，其中以 $(1,3)$ 作为生成格生成的子楼梯的边界格数为 $4$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/88e0br57.png)\n\n长颈鹿看到屏幕上的楼梯后很好奇。他首先计算出了这一楼梯的边界格数 $p$，并给定了 $p$ 的某一**正整数因子** $q$。他想要知道，给定的楼梯是否有子楼梯满足边界格数等于 $q$。如果是，他希望你给出**任一**这样的子楼梯的生成格。\n\n梦境时常变化，因此长颈鹿可能会有许多次这样的询问，楼梯也可能会发生变化。初始楼梯 $L$ 为空，对于 $i \\ge 1$ 记 $s_i$ 为最大的满足 $(i,s_i) \\in L$ 的正整数，若不存在则令其为 $0$，则有若干次三种之一的修改：\n\n- 给定正整数 $a$ 和 $b$，在前 $a$ 行的末尾插入 $b$ 格。形式化地，对于 $i=1, 2, \\dots, a$，将 $(i,s_i+1), (i,s_i+2),\\dots,(i,s_i+b)$ 加入 $L$。\n- 给定正整数 $a$ 和 $b$，在第 $a$ 行后（包含第 $a$ 行）的所有行行末尾删去 $b$ 格，若不足则删空。形式化地，对于 $i=a,a+1,a+2,\\dots,10^{100}$，将 $(i,s_i),(i,s_i−1),\\dots,(i,s_i−b+1)$ 从 $L$ 中移除（不存在的则忽略）。\n- 给定正整数 $u$，撤销之前的 $u$ 次操作，即将楼梯还原为 $u$ 次操作前的状态，**保证这 $u$ 次操作均为询问或在行末尾插入**。具体地，假设该操作为第 $t$ 次操作，我们一定有 $t>u$，且第 $t−1,t−2,\\dots,t−u$ 次操作均为询问或在行末尾插入（即上述的第一种修改）。你只需要将楼梯还原为第 $t−u$ 次操作前的状态即可（当然，你应该保留询问的输出）。\n\n可以证明每次修改之后得到的集合仍然是一个楼梯。\n\n## Input\n\n输入数据第一行包含一个正整数 $m$，表示操作总数。\n\n接下来 $m$ 行每行描述四种之一的操作，详细含义可参见题目描述一节。描述为由空格分隔的一个字符和一到两个正整数，具体地：\n\n- `+ a b`：在前 $a$ 行的末尾插入 $b$ 格。\n- `- a b`：在第 $a$ 行后（包括第 $a$ 行）的所有行行末尾删去 $b$ 格，若不足则删空。\n- `R u`：撤销之前的 $u$ 次操作，即将楼梯还原为 $u$ 次操作前的状态。**保证这 $u$ 次操作存在且均为询问或在行末尾插入**，即该行之前的 $u$ 行均以 `+` 或 `?` 开头。\n- `? q`：询问是否有边界格数等于 $q$ 的子楼梯，若有则给出任意合法生成格。**保证 $q$ 是当前楼梯边界格数的因子**。\n\n## Output\n\n对于每个询问（`?` 操作）输出一行。\n\n如果存在边界格数等于 $q$ 的子楼梯，输出一行两个用空格分隔的正整数 `x y`，表示一个合法生成格是 $(x,y)$。否则输出一行两个用空格分隔的 $-1$。\n\n[samples]\n\n## Background\n\n长颈鹿累了，他开始做梦。\n\n在梦中他下坠。他穿过草地，穿过打着转的羊群。他穿过星海，穿过漫天的火羽。\n\n终于，他站在了一块屏幕前。屏幕上展示着某种类似楼梯的图样。\n\n## Note\n\n**【样例解释 #1】**\n\n每次修改操作之后的楼梯如下图（排列方式同题目描述，省略了各格子的编号）。注意撤销操作实际只撤销了一个 `+` 操作。样例有多个合法解，给出的输出只是一种合法的输出。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/milfbsr1.png)\n\n**【数据范围】**\n\n对于所有测试数据，$1 \\le m \\le 3 \\times 10^5$。\n\n+ 对于 `+` 和 `-` 操作，$1 \\le a, b \\le 10^9$。\n+ 对于 `R` 操作，保证之前紧邻的 $u$ 次操作存在且均为询问或在行末尾插入。\n+ 对于 `?` 操作，$1 \\le q \\le 10^{18}$ 且**保证为当前楼梯边界格数的因子**。\n\n记 $a_{\\max}$ 为所有 `+` 和 `-` 操作中 $a$ 的最大值，$b_{\\max}$ 为所有 `+` 和 `-` 操作中 $b$ 的最大值。\n\n| 测试点 | $m =$ | $a_{\\max} \\leq$ | $b_{\\max} \\leq$ | 特殊性质 |\n| :-: | :-: | :-: | :-: | :-: |\n| $1$ | $200$ | $50$ | $20$ | 无 |\n| $2$ | $400$ | $100$ | $100$ | AB |\n| $3$ | $600$ | $500$ | $500$ | A |\n| $4$ | $800$ | $500$ | $10^6$ | 无 |\n| $5$ | $10^3$ | $10^3$ | $10^6$ | 无 |\n| $6$ | $3000$ | $10^6$ | $10^6$ | B |\n| $7$ | $5000$ | $10^6$ | $10^6$ | AB |\n| $8$ | $10^4$ | $10^9$ | $10^9$ | 无 |\n| $9$ | $3 \\times 10^4$ | $10^9$ | $10^9$ | A |\n| $10$ | $5 \\times 10^4$ | $10^9$ | $10^9$ | 无 |\n| $11$ | $7 \\times 10^4$ | $10^9$ | $10^9$ | 无 |\n| $12$ | $10^5$ | $10^9$ | $10^9$ | B |\n| $13$ | $1.2 \\times 10^5$ | $10^9$ | $10^9$ | 无 |\n| $14$ | $1.4 \\times 10^5$ | $10^6$ | $10^6$ | 无 |\n| $15$ | $1.6 \\times 10^5$ | $10^6$ | $10^6$ | AB |\n| $16$ | $1.8 \\times 10^5$ | $10^9$ | $10^9$ | 无 |\n| $17$ | $2 \\times 10^5$ | $10^6$ | $10^6$ | B |\n| $18$ | $2.5 \\times 10^5$ | $10^6$ | $10^6$ | B |\n| $19$ | $2.7 \\times 10^5$ | $10^9$ | $10^9$ | 无 |\n| $20$ | $3 \\times 10^5$ | $10^9$ | $10^9$ | 无 |\n\n其中附加限制中的特殊性质如下所示：\n\n- 特殊性质 A：`?` 操作在所有 `+` 和 `-` 操作之后。没有 `R` 操作。\n- 特殊性质 B：没有 `-` 操作。\n\n**【提示】**\n\n请注意选用合适的数据类型存储各结果。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9073","tags":["2023","Special Judge","O2优化","杨表","WC","CTSC/CTS"],"sample_group":[["18\n+ 5 1\n+ 2 1\n? 3\n+ 3 2\n? 4\n? 4\n+ 4 1\n? 3\nR 3\n- 2 2\n? 3\n- 1 1\n? 2\n? 4\n- 1 2\n? 1\n- 9 9\n? 1","3 1\n1 3\n2 2\n2 4\n2 1\n1 2\n1 1\n1 1\n1 1"],["见附件中的 stairs2.in","见附件中的 stairs2.ans"],["见附件中的 stairs3.in","见附件中的 stairs3.ans"],["见附件中的 stairs4.in","见附件中的 stairs4.ans"],["见附件中的 stairs5.in","见附件中的 stairs5.ans"],["见附件中的 stairs6.in","见附件中的 stairs6.ans"]],"created_at":"2026-03-03 11:09:25"}}