P9073 [WC/CTS2023] Staircase

The giraffe is tired, and he begins to dream. In the dream, he is falling. He passes through grasslands, through spinning flocks of sheep. He passes through a sea of stars, through flames of feathers filling the sky. Finally, he stands in front of a screen. On the screen is a pattern that looks like a staircase.

First, we give some formal definitions of a staircase. We call an ordered pair $(x,y)$ of positive integers a **cell**. We call a set $L$ (possibly empty) consisting of cells a **staircase** if and only if it satisfies the following two conditions: + If $(x,y)\in L$ and $x>1$, then $(x-1,y)\in L$. + If $(x,y)\in L$ and $y>1$, then $(x,y-1)\in L$. For a staircase $L$ and a cell $(x,y)\in L$, we define the **sub-staircase** generated by the **generator cell** $(x,y)$ as $$ \{(a-x+1, b-y+1) \mid (a,b) \in L, a \ge x, b \ge y\} $$ It is easy to prove that this set is still a staircase. For a staircase $L$, we define the **number of boundary cells** as the number of cells $(x,y)\in L$ that satisfy $x=1$ or $y=1$. To make it easier to understand, we give an intuitive explanation. On the plane, we can arrange all cells into a grid in the order of increasing $y$ coordinate from left to right, and increasing $x$ coordinate from top to bottom. Therefore, we also call $(x,y)$ the cell in row $x$, column $y$. Under this interpretation, if a cell belongs to a staircase, and its upper and left neighbors are not beyond the boundary, then the corresponding cells also belong to this staircase. A sub-staircase is the non-empty staircase formed by the cells in the region to the lower right of the generator cell. The number of boundary cells of a staircase is the total number of cells on the top boundary or the left boundary. As in the figure below, $(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)$ form a valid staircase. The number of boundary cells of this staircase is $8$. Among them, the sub-staircase generated with $(1,3)$ as the generator cell has $4$ boundary cells.  After seeing the staircase on the screen, the giraffe is very curious. He first computes the number of boundary cells $p$ of this staircase, and is given a **positive integer factor** $q$ of $p$. He wants to know whether the given staircase has a sub-staircase whose number of boundary cells equals $q$. If yes, he wants you to output the generator cell of **any** such sub-staircase. Dreams often change, so the giraffe may have many such queries, and the staircase may also change. The initial staircase $L$ is empty. For $i \ge 1$, let $s_i$ be the largest positive integer such that $(i,s_i)\in L$; if it does not exist, let it be $0$. Then there are several modifications of one of the following three types: - Given positive integers $a$ and $b$, insert $b$ cells at the end of each of the first $a$ rows. Formally, for $i=1,2,\dots,a$, add $(i,s_i+1),(i,s_i+2),\dots,(i,s_i+b)$ into $L$. - Given positive integers $a$ and $b$, delete $b$ cells from the end of every row after row $a$ (including row $a$). If there are fewer than $b$ cells, delete all of them. Formally, for $i=a,a+1,a+2,\dots,10^{100}$, remove $(i,s_i),(i,s_i-1),\dots,(i,s_i-b+1)$ from $L$ (ignore those that do not exist). - Given a positive integer $u$, undo the previous $u$ operations, i.e., restore the staircase to the state before those $u$ operations. It is **guaranteed** that these $u$ operations are all queries or “insert at row end”. Specifically, suppose this is the $t$-th operation. We must have $t>u$, and operations $t-1,t-2,\dots,t-u$ are all queries or the first type of modification above. You only need to restore the staircase to the state before the $(t-u)$-th operation (of course, you should keep the outputs of the queries). It can be proven that after each modification, the resulting set is still a staircase.

The first line of the input contains a positive integer $m$, denoting the total number of operations. The next $m$ lines each describe one of four types of operations. The detailed meaning can be found in the Description section. Each line consists of a character and one or two positive integers separated by spaces. Specifically: - `+ a b`: Insert $b$ cells at the end of each of the first $a$ rows. - `- a b`: Delete $b$ cells from the end of every row after row $a$ (including row $a$). If there are fewer than $b$ cells, delete all of them. - `R u`: Undo the previous $u$ operations, i.e., restore the staircase to the state before those $u$ operations. It is **guaranteed** that these $u$ operations exist and are all queries or “insert at row end”, i.e., the previous $u$ lines before this one all start with `+` or `?`. - `? q`: Ask whether there exists a sub-staircase whose number of boundary cells equals $q$. If yes, output any valid generator cell. It is **guaranteed** that $q$ is a factor of the current staircase’s number of boundary cells.

For each query (`?` operation), output one line. If there exists a sub-staircase whose number of boundary cells equals $q$, output two positive integers `x y` separated by a space, indicating a valid generator cell $(x,y)$. Otherwise, output `-1 -1`.

**Sample Explanation #1** The staircase after each modification is shown in the figure below (the arrangement is the same as in the Description section, and the indices of cells are omitted). Note that the undo operation actually only undoes one `+` operation. There are multiple valid answers for the sample; the given output is just one valid output.  **Constraints** For all testdata, $1 \le m \le 3 \times 10^5$. + For `+` and `-` operations, $1 \le a, b \le 10^9$. + For `R` operations, it is guaranteed that the previous consecutive $u$ operations exist and are all queries or “insert at row end”. + For `?` operations, $1 \le q \le 10^{18}$ and it is **guaranteed to be a factor of the current staircase’s number of boundary cells**. Let $a_{\max}$ be the maximum $a$ among all `+` and `-` operations, and let $b_{\max}$ be the maximum $b$ among all `+` and `-` operations. | Test Point | $m =$ | $a_{\max} \leq$ | $b_{\max} \leq$ | Special Properties | | :-: | :-: | :-: | :-: | :-: | | $1$ | $200$ | $50$ | $20$ | None | | $2$ | $400$ | $100$ | $100$ | AB | | $3$ | $600$ | $500$ | $500$ | A | | $4$ | $800$ | $500$ | $10^6$ | None | | $5$ | $10^3$ | $10^3$ | $10^6$ | None | | $6$ | $3000$ | $10^6$ | $10^6$ | B | | $7$ | $5000$ | $10^6$ | $10^6$ | AB | | $8$ | $10^4$ | $10^9$ | $10^9$ | None | | $9$ | $3 \times 10^4$ | $10^9$ | $10^9$ | A | | $10$ | $5 \times 10^4$ | $10^9$ | $10^9$ | None | | $11$ | $7 \times 10^4$ | $10^9$ | $10^9$ | None | | $12$ | $10^5$ | $10^9$ | $10^9$ | B | | $13$ | $1.2 \times 10^5$ | $10^9$ | $10^9$ | None | | $14$ | $1.4 \times 10^5$ | $10^6$ | $10^6$ | None | | $15$ | $1.6 \times 10^5$ | $10^6$ | $10^6$ | AB | | $16$ | $1.8 \times 10^5$ | $10^9$ | $10^9$ | None | | $17$ | $2 \times 10^5$ | $10^6$ | $10^6$ | B | | $18$ | $2.5 \times 10^5$ | $10^6$ | $10^6$ | B | | $19$ | $2.7 \times 10^5$ | $10^9$ | $10^9$ | None | | $20$ | $3 \times 10^5$ | $10^9$ | $10^9$ | None | The special properties in the additional constraints are as follows: - Special Property A: All `?` operations occur after all `+` and `-` operations. There are no `R` operations. - Special Property B: There are no `-` operations. **Hint** Please make sure to use appropriate data types to store all results. Translated by ChatGPT 5