English version

Firstly, consider a classical dp to calculate $dp_{u,k}$ as the number of delete $k$ vertices in subtree $u$ without considering deleting vertex $n-i+1$ everyday. This is trivial.

Then, due to the existence of an “automatic deletion” process, we cannot view the selected points within the subtree of $u$ as operations with only relative order, because they may be illegal. However, we consider the final operation sequence, putting the vertex chosen on the $i$ th day in the position $n-i+1$. That is, if we firstly choose $4$, then $3$, then $1$, it will be $0431$. Then, one vertex $u$ must be put in position $u$ or later.

Then, we find that for the subtree of vertex $u$ with DFS order interval $[l,r]$, all vertex can't be put in position before $l$, and always legal to put in position after $r$ if parent-child relations are satisfied.

So we consider a dp $f_{u,i,j,k}$ which represents that the subtree of $u$ leaves position $i$ for ancestors (which means nothing can be placed at position $i$ or before, and if $i=0$, then nothing is left for ancestors), there are $j$ empty spaces (not including the one left for ancestors), and $k$ vertices need to be put into positions after the subtree of $u$. In the $i=0$ case,we merge subtrees,and the subtree with smaller DFS order can put some backward operations into the space of the subtree with bigger DFS order.

Specifically, consider the sons of $u$ enumerated in reverse order of DFS, and the son is $v$.Then enumerate $w$ as how many backward operations from $v$ will fill in space of $u$. The transition is $f_{u,0,j+j1-w,k+k1-w} \leftarrow f_{u,0,j+j1-w,k+k1-w}+f_{u,0,j,k}\times f_{v,0,j1,k1}\times {j \choose w}\times{k+k1-w \choose k}$.

For $f_{v,i,j,k}(i\neq 0)$, it won't interfere the transition with its following siblings. And for $f_{u,i,j,k}$, just consider where to put $u$. The answer for $i$ operations is $f_{1,i,i-2,0}$.

中文版本

对于树上选一个点删去一个子树方案数这个经典问题，一个常见的 dp 是记 $dp_{u,k}$ 为 $u$ 子树选 $k$ 个点方案数，转移时兄弟间用组合数将其合并，然后祖先要选就必须选在它们前面，这一部分 $O(n^2)$。

回到本题，由于存在“自动删点”的过程因此我们不能将 $u$ 子树内选的点看成只有相对顺序的操作，因为其可能不合法。但我们考虑最终的操作序列，没有的位置留空：比如样例 $1$ 中第一次选 $4$，第二次选 $3$，第三次选 $1$，那么操作序列即为 $0 4 3 1$。也就是第 $i$ 次选的点放在 $n-i+1$ 的位置上。这样，我们发现一个点 $u$ 只能填在 $u$ 及以后的位置，那么对于一个点 $u$ 的子树，其 dfs 序区间为 $[l,r]$，那么 $u$ 子树的点填到 $r$ 以后的位置一定合法，而 $u$ 留的空其前面的兄弟和祖先填进去只要没有父子关系干扰一定合法，于是我们考虑 dp。

考虑一个 dp $f_{u,i,j,k}$ 表示 $u$ 子树 $i$ 这个位置留给祖先（也就是说 $i$ 及以前不能放东西，如果 $i=0$ 就不留），有 $j$ 个空（不包含给祖先留的），有 $k$ 个点要填到 $u$ 子树以后的位置。先考虑 $i=0$ 情况。那么合并两个子树的时候就是 dfs 序更小的子树可以选一些向后的操作填到 dfs 序更大子树的空里面。然后两个子树的空合并，向后操作合并。

具体来说，考虑 $u$ 的儿子按 dfs 序倒序枚举，对于一个儿子 $v$，那么合并 $f_{u,0,j,k}$ 和 $f_{v,0,j1,k1}$ 的时候先枚举一个 $w$ 代表选多少个 $v$ 中的向后操作填到 $u$ 的 $v$ 之后的子树，转移即为 $f_{u,0,j+j1-w,k+k1-w}\leftarrow f_{u,0,j+j1-w,k+k1-w}+f_{u,0,j,k}\times f_{v,0,j1,k1}\times {j \choose w}\times{k+k1-w \choose k}$。

再考虑 $f_{v,i,j1,k1}$ ，发现它需要给祖先留空并不影响其和后面兄弟的转移，因此转移同上，只是 $v$ 留的空 $u$ 同样需要留，所以转移到 $f_{u,i,j+j1-w,k+k1-w}$。注意这里需要预处理转移系数（因为 $i$ 取任何值转移系数相同）才能达到 $O(n^5)$。

然后考虑 $f_{u,i,j,k}$ 的转移，即 $v$ 后面的子树已经留了空。那么 $v$ 子树现在不能放任何东西，但是可以用一些向后的操作填 $i$ 后面的空，这里用 $dp_{v,k}$ 去转移即可。

子树转移完后，接下来是 $u$ 自身的操作。$u$ 可以有几种选择：

• 不填，那么会多一个空 $f_{u,i,j,k}\rightarrow f_{u,i,j+1,k}$，如果把这个空留给祖先填，那么 $f_{u,0,j,k}\rightarrow f_{u,dfn_u,j,k}$。
• 填到子树准备的空里面，此时有两种选择：一是不再给祖先留空，那么 $f_{u,i,j,k}\rightarrow f_{u,0,j+1,k}$，一种是在 $i$ 前面重新给祖先留一个空，那么 $f_{u,i,j,k}\rightarrow f_{u,i_1,j+1,k}(i_1 < i)$。
• 填自己，此时不能给上面留空，$f_{u,0,j,k}$ 不变。
• 让自己变为向后操作，那么 $u$ 子树内现在不能填任何东西，但是可以给祖先留空，$f_{u,i,siz_u-2,k}\rightarrow f_{u,i,siz_u-1,k+1},f_{u,0,siz_u-1,k}\rightarrow f_{u,0,siz_u,k+1}$。

最后求答案的时候，对于要求 $k$ 次操作，相当于给 $1$ 在 $n-k+1$ 的位置留了空，同时恰好只有 $n-k$ 个空（那么后面就没有空，就是合法的操作序列），输出即可。

English version

Firstly, consider a classical dp to calculate $dp_{u,k}$ as the number of delete $k$ vertices in subtree $u$ without considering deleting vertex $n-i+1$ everyday. This is trivial.

Then, due to the existence of an “automatic deletion” process, we cannot view the selected points within the subtree of $u$ as operations with only relative order, because they may be illegal. However, we consider the final operation sequence, putting the vertex chosen on the $i$ th day in the position $n-i+1$. That is, if we firstly choose $4$, then $3$, then $1$, it will be $0431$. Then, one vertex $u$ must be put in position $u$ or later.

Then, we find that for the subtree of vertex $u$ with DFS order interval $[l,r]$, all vertex can't be put in position before $l$, and always legal to put in position after $r$ if parent-child relations are satisfied.

So we consider a dp $f_{u,i,j,k}$ which represents that the subtree of $u$ leaves position $i$ for ancestors (which means nothing can be placed at position $i$ or before, and if $i=0$, then nothing is left for ancestors), there are $j$ empty spaces (not including the one left for ancestors), and $k$ vertices need to be put into positions after the subtree of $u$. In the $i=0$ case,we merge subtrees,and the subtree with smaller DFS order can put some backward operations into the space of the subtree with bigger DFS order.

Specifically, consider the sons of $u$ enumerated in reverse order of DFS, and the son is $v$.Then enumerate $w$ as how many backward operations from $v$ will fill in space of $u$. The transition is $f_{u,0,j+j1-w,k+k1-w} \leftarrow f_{u,0,j+j1-w,k+k1-w}+f_{u,0,j,k}\times f_{v,0,j1,k1}\times {j \choose w}\times{k+k1-w \choose k}$.

For $f_{v,i,j,k}(i\neq 0)$, it won't interfere the transition with its following siblings. And for $f_{u,i,j,k}$, just consider where to put $u$. The answer for $i$ operations is $f_{1,i,i-2,0}$.

中文版本

对于树上选一个点删去一个子树方案数这个经典问题，一个常见的 dp 是记 $dp_{u,k}$ 为 $u$ 子树选 $k$ 个点方案数，转移时兄弟间用组合数将其合并，然后祖先要选就必须选在它们前面，这一部分 $O(n^2)$。

回到本题，由于存在“自动删点”的过程因此我们不能将 $u$ 子树内选的点看成只有相对顺序的操作，因为其可能不合法。但我们考虑最终的操作序列，没有的位置留空：比如样例 $1$ 中第一次选 $4$，第二次选 $3$，第三次选 $1$，那么操作序列即为 $0 4 3 1$。也就是第 $i$ 次选的点放在 $n-i+1$ 的位置上。这样，我们发现一个点 $u$ 只能填在 $u$ 及以后的位置，那么对于一个点 $u$ 的子树，其 dfs 序区间为 $[l,r]$，那么 $u$ 子树的点填到 $r$ 以后的位置一定合法，而 $u$ 留的空其前面的兄弟和祖先填进去只要没有父子关系干扰一定合法，于是我们考虑 dp。

考虑一个 dp $f_{u,i,j,k}$ 表示 $u$ 子树 $i$ 这个位置留给祖先（也就是说 $i$ 及以前不能放东西，如果 $i=0$ 就不留），有 $j$ 个空（不包含给祖先留的），有 $k$ 个点要填到 $u$ 子树以后的位置。先考虑 $i=0$ 情况。那么合并两个子树的时候就是 dfs 序更小的子树可以选一些向后的操作填到 dfs 序更大子树的空里面。然后两个子树的空合并，向后操作合并。

具体来说，考虑 $u$ 的儿子按 dfs 序倒序枚举，对于一个儿子 $v$，那么合并 $f_{u,0,j,k}$ 和 $f_{v,0,j1,k1}$ 的时候先枚举一个 $w$ 代表选多少个 $v$ 中的向后操作填到 $u$ 的 $v$ 之后的子树，转移即为 $f_{u,0,j+j1-w,k+k1-w}\leftarrow f_{u,0,j+j1-w,k+k1-w}+f_{u,0,j,k}\times f_{v,0,j1,k1}\times {j \choose w}\times{k+k1-w \choose k}$。

再考虑 $f_{v,i,j1,k1}$ ，发现它需要给祖先留空并不影响其和后面兄弟的转移，因此转移同上，只是 $v$ 留的空 $u$ 同样需要留，所以转移到 $f_{u,i,j+j1-w,k+k1-w}$。注意这里需要预处理转移系数（因为 $i$ 取任何值转移系数相同）才能达到 $O(n^5)$。

然后考虑 $f_{u,i,j,k}$ 的转移，即 $v$ 后面的子树已经留了空。那么 $v$ 子树现在不能放任何东西，但是可以用一些向后的操作填 $i$ 后面的空，这里用 $dp_{v,k}$ 去转移即可。

子树转移完后，接下来是 $u$ 自身的操作。$u$ 可以有几种选择：

• 不填，那么会多一个空 $f_{u,i,j,k}\rightarrow f_{u,i,j+1,k}$，如果把这个空留给祖先填，那么 $f_{u,0,j,k}\rightarrow f_{u,dfn_u,j,k}$。
• 填到子树准备的空里面，此时有两种选择：一是不再给祖先留空，那么 $f_{u,i,j,k}\rightarrow f_{u,0,j+1,k}$，一种是在 $i$ 前面重新给祖先留一个空，那么 $f_{u,i,j,k}\rightarrow f_{u,i_1,j+1,k}(i_1 < i)$。
• 填自己，此时不能给上面留空，$f_{u,0,j,k}$ 不变。
• 让自己变为向后操作，那么 $u$ 子树内现在不能填任何东西，但是可以给祖先留空，$f_{u,i,siz_u-2,k}\rightarrow f_{u,i,siz_u-1,k+1},f_{u,0,siz_u-1,k}\rightarrow f_{u,0,siz_u,k+1}$。

最后求答案的时候，对于要求 $k$ 次操作，相当于给 $1$ 在 $n-k+1$ 的位置留了空，同时恰好只有 $n-k$ 个空（那么后面就没有空，就是合法的操作序列），输出即可。

简要题意

对于三个长度为 $n$ 的 01 字符串 $s_1,s_2,s_3$，称长度为 $n$ 的 01 字符串 $t$ 是好的当且仅当 $\forall 1 \le i,j \le n, \exists k \in \{1,2,3\}, s_{k,i} = t_i, s_{k,j} = t_j$。设 $f(s_1,s_2,s_3)$ 为这样的好的串的数量。

现在我们有三个长度为 $n$ 的随机 01 字符串 $s_1,s_2,s_3$，其中 $s_i (1 \le i \le 3)$ 的第 $j (1 \le j \le n)$ 个字符有 $\frac{p_{i,j}}{9}$ 的概率为 1，$\left(1 - \frac{p_{i,j}}{9}\right)$ 的概率为 0，其中 $p_{i,j}$ 是一个 $0$ 至 $9$ 的整数。所有的随机事件是独立的。你需要求 $f(s_1,s_2,s_3)$ 的期望，对 $998244353$ 取模。

$n \le 3 \times 10^5$

解法

引理：设 $\text{maj}(a,b,c)$ 为 $a,b,c$ 中的众数；对于三个长度为 $n$ 的 01 字符串 $s_1,s_2,s_3$，设 $\text{maj}(s_1,s_2,s_3)$ 为长度为 $n$ 的字符串 $t$，其中 $t_i = \text{maj}(s_{1,i},s_{2,i},s_{3,i})$，则 $f(s_1,s_2,s_3) = |\{s_1,s_2,s_3,\text{maj}(s_1,s_2,s_3)\}|$。

我们首先说明以上四个字符串均满足题设条件。$s_1,s_2,s_3$ 满足条件是显然的。

对于 $t=\text{maj}(s_1,s_2,s_3)$，对于任意 $1 \le i < j \le n$，存在下标 $1 \le a < b \le 3$ 满足 $s_{a,i} = s_{b,i} = t_i$，又存在 $1 \le c < d \le 3$ 满足 $s_{c,j} = s_{d,j} = t_j$。根据抽屉原理 $\{a,b,c,d\}$ 中有两个数相等，对应的下标即是满足题设条件的 $k$。

接下来我们说明不存在其它字符串满足条件。当满足条件的字符串 $t$ 不等于 $\text{maj}(s_1,s_2,s_3)$ 时，设 $t_i \ne \text{maj}(s_1,s_2,s_3)_i$，则 $t_i$ 只在 $s_{1,i},s_{2,i},s_{3,i}$ 中出现恰好一次（不能不出现，否则不可能满足题设条件），不妨假设其为 $s_{1,i}$。此时取任意 $j \ne i$，根据题设条件必然有 $t_j = s_{1,j}$（因为 $k$ 必须取 $1$），因此 $t = s_1$。

进一步地，可以分类讨论得到 $|\{s_1,s_2,s_3,\text{maj}(s_1,s_2,s_3)\}| = 4 - \sum_{i=1}^3 [\text{maj}(s_1,s_2,s_3) = s_i]$：

• $f(s_1,s_2,s_3) = 4$ 时四个字符串两两不同；
• $f(s_1,s_2,s_3) = 3$ 时必然是某个 $s_i = \text{maj}(s_1,s_2,s_3)$ 的情况而不是 $s_i = s_j$ 的情况，因为 $s_i = s_j$ 会直接导致 $\text{maj}(s_1,s_2,s_3) = s_i$；
• $f(s_1,s_2,s_3) = 2$ 时必然是 $s_i = s_j = \text{maj}(s_1,s_2,s_3)$ 且剩余的字符串跟它们不同的情况；
• $f(s_1,s_2,s_3) = 1$ 时必然是四个字符串相等的情况。

由于期望的线性性，只需要计算 $\Pr[\text{maj}(s_1,s_2,s_3) = s_i]$ 即可。由于每一位的随机事件是独立的，所以直接把每一位相等的概率乘起来就行了。

复杂度 $O(n)$。

题外话

• 本题中文名“石墨烯”纯属出题人夹带私货，与题目无关，具体含义不便透露，大家不要过度解读。
• 本题原来只有 $k=0$ 这个版本作为签到，但是因为某些原因需要稍微加强难度，就变成了现在这个版本。

Description

• 给定长为 $n$ 的序列 $a, b$，每轮操作先使每对 $(a_i, b_i)$ 中较小值变为零，较大值变为它们的差，然后使 $a$ 循环右移一位。
• 操作开始前，可以先对 $a$ 进行 $k$ 次 $a_i \leftarrow a_{i-1}$（需保证 $a_i$ 恒非负），问最少几轮操作才能使 $a$ 全变为零？
• $1 \le n, \sum{n} \le 5 \times 10^5$，$1 \le a_i, b_i \le 10^9$。

$k=0$

• 考虑对于每个 $a_i$ 分别求出至少循环右移几次之后会变为零，记之为 $d_i$，则答案即为 $\max_{1≤\le i \le n}{d_i}$。
• 遇到环上问题，首先考虑断环为链（即令 $a_{i+n}=a_i,b_{i+n}=b_i$）。

• 考虑如下转化：记 $s$ 为由 $a_1$ 个左括号，$b_1$ 个右括号，$a_2$ 个左括号，$b_2$ 个右括号，……，$a_{2n}$ 个左括号，$b_{2n}$ 个右括号顺次拼接而成的括号串，则原题中的操作过程就相当于对 $s$ 进行括号匹配的过程，而 $a_i$ 会被哪个 $b_j$ 首次消成零，就取决于 $a_i$ 对应的第一个左括号所匹配的右括号属于哪个 $b_j$ 。

  • “使 $(a_i, b_i)$ 中较小值变为零，较大值变为它们的差” $\rightarrow$ “匹配 $a_i, b_i$ 对应的括号”；
  • “使 $a$ 循环右移一位” $\rightarrow$ “未被匹配的左括号继续向右寻找右括号尝试匹配”。
• 对于括号匹配问题，自然想到利用前缀和转化。
• 令 $c_i=\sum_{j=1}^{i}(a_i-b_j)$，记 $p_i$ 为最小的满足 $p_i > i$ 且 $c_{p_i} \le c_i$ 的下标，则 $d_i$ 即为 $p_i-i$。
• 使用单调栈即可求出所有 $p_i$，时间复杂度为 $O(\sum n)$。

正解

• 加入了 $k$ 的限制后，考虑二分答案 $x$，转而求在 $x$ 轮操作后将 $a$ 全变为零的最少 $-1$ 次数。
• 发现直接在断环为链的 $2n$ 个数上不太好计算贡献（因为可能会重复计算），所以我们进行如下调整：将 $a,b$ 同时循环右移若干位，使得 $a_i-b_i$ 的前缀和 $c_i$ 的最小值在 $c_n$ 处取到。
• 这样调整的好处是，对于调整后的 $a,b$，我们所关心的 $p_i(1 \le i \le n)$ 都不会超过 $n$，也就是说，在实际操作过程中，不会出现 $a_n > 0$ 右移到 $a_1$ 的情况。
• 因此，我们仅通过调整 $a, b$ 就将环上问题转化为了一个长为 $n$ 的链上问题。
• 接下来考虑如何在调整后的 $a,b$ 上计算答案为 $x$ 时的最少 $-1$ 次数。
• 不难想到对 $a$ 从 $n-x$ 到 $0$ 使用贪心，若当前位置 $i$ 对应的 $d_i=p_i-i > x$，即若 $\min_{j=i+1}^{i+x}{c_j} > c_i$，则对 $a_{i+1}$ 进行 $\min_{j=i+1}^{i+x}{c_j} - c_i$ 次 $-1$。
• 整个过程均可通过单调栈维护。
• 时间复杂度为 $O(\sum n \log k)$。

English version

Each operation transform three adjacent characters into one. If the string starts with 11, the answer should be yes since we can first transform the remaining part into a single 0 or 1 and then the value of 11? is always $1$.

If the string ends with 1, only 101 has no solution, otherwise it starts with 11 or 0, or we can transform 10? in the front of the string into a 0. Then transform the rest part of the string into a single character to make the last operation 0?(anything):1 makes 1.

If an operation transformed a string ending with 0 into one ending with 1, it must be 1?1:0 makes 1.

Consider the case where the strings contains 11 as a substring. After transforming the remaining part, ?11?? or ??11? will be derived. The cases are 01100, 00110, 01110, 10110. All other cases start with 11 or end with 1.

All cases of ??11? have a solution:

(0?0:1)?1:0 makes 1.

(0?1:1)?1:0 makes 1.

1?(0?1:1):0 makes 1.

However, 01100 has no solution.

Since 0?0:1 equals 1, before the last 1, any two adjacent 0's with no 1 in between can be eliminated. Thus, if there are two 1's with an even number of 0's in between, and there are an even number of characters in front the former 1, i.e., (..)*1(00)*1(..)*0 in regular expression, the answer should be yes, since after eliminating the 0's in between, the 1's become adjacent. The parity of the characters before the former 1 guarantees that it will not become 01100.

Another case is that the string ends with 0 and every pair of adjacent 1's has an odd number of 0's in between. Since 0(1?0:1)0 makes 000, 1(0?1:0)1 makes 101, 10(1?0:0)01 makes 10001, there is no way to change the parity of the consecutive 0's to make 11 to change the ending 0 into 1.

In the remaining case, there are even 0's between some pair of adjacent 1's, but the number of characters before the first 1 is odd, there must be only one pair. Suppose the string is 1-indexed. It is because the indices of such pair of 1's must be [odd, even]; while the indices in the previous case must be [even, odd]. Thus, if there are two such pairs of this case [odd, even], in the parity sequence [odd, even, ..., odd, even] there must be an [even, odd] as a substring.

Therefore, any other pair of adjacent 1's must have odd 0's in between, i.e., $0(00)^*\color{blue}(10(00)^*)^*\color{red}1\color{black}(00)^*\color{red}1\color{blue}((00)^*01)^*\color{black}(00)^+$ in regular expression. Any operation remains the string in this case, except that the string is $0(00)^*\color{blue}(10(00)^*)^*\color{red}1\color{red}1\color{black}(00)^+$ and the operation is $\color{red}1\color{black}?\color{red}1\color{black}:0$ makes 1. Since it must ends with `00`, it becomes a string ending with `0` and every pair of adjacent 1's has odd 0's in between, which is a case mentioned before that has no solution.

In conclusion, it has a solution if and only of at least one of the two following conditions is met:

• It ends with 1 but it is not 101.
• It has two adjacent 1's such that there are even 0's in between and the number of characters before the former 1 is even.

中文版本

英文题解里描述了做本题的一种思路，以及证明。

如果要直接写做法的话，是下面这样：

假设字符串下标从 $1$ 开始编号。

首先判断是否存在 $i,j$ 使得 $i$ 是奇数，$j$ 是偶数，$s_i$ 和 $s_j$ 都是 1，且这两个字符中间都是 0。

• 如果是，那么先把中间的 0 和 $s_j$ 写成 (0?0:0?0:.....:1)，表达式的值为 1（一定有偶数个 0），然后分三种情况：

  • 如果 $i=1$，那么就直接把 $s_j$ 后面的部分变成一个数，最后变成 (1?1:*) 是 1。

  • 否则考虑把 $s$ 的第 $1\sim i-2$ 位变成一个数，并计算出这个值。

    • 如果值为 0 那么有 ((0?*:1)?1:*) 等于 1。
    • 如果值为 1 那么有 (1?(*?1:1):*) 等于 1。

• 否则，判断是否满足字符串末尾是 1 且本身不等于 101：

  • 如果是，那么字符串一定以 0 或 10 开头，于是第一位或前三位操作后一定是 0，然后留下开头的 0 和结尾的 1，把中间的部分变成一个数，最后 (0?*:1) 结果一定是 1。
  • 否则，无解。

此外，还有一种比较特别的解法：

可以发现构造的过程中需要用到不超过两层括号（不算整个表达式最外面一层）。所以如果你要是猜到了这一点可以直接使用动态规划从右到左扫这个字符串，记录每一层栈中的内容。最多三层栈，每层栈最多两个比特，一共 $6^3+6^2+6=258$ 种状态。大概也能过。

不知道有没有什么奇怪的乱搞可以搜过去。不过我还是欢迎吧。

引言

今年命题会的时候，我们惊奇地发现今年的模拟题还没有着落。

于是我翻出了这个压箱底的 idea，当作一个中模拟。

idea 恰如其分来自在你清食堂的吃饭经历，获得了大家的一致认同。

时限只开 3s 是因为有 100 个点，开太久会更严重地卡评测的。std 跑了 1.6s。出题人试图开 5s 被系统部和赛务部的同学们拦下了

比赛情况

本题的完整版本预期难度是 medium，不过我个人认为是 easy+（？）。

丝路市西套村代表队获得了本题首杀！

本题大约有一半的队伍通过了本题。

同时，不少夺冠热门队伍在本题上获得了大量罚时。

题意简述

食堂餐桌座位分布在第一象限网格每个 $3 \times 3$ 完整格子右上角的 $2 \times 2$ 格子，剩下的部分为走廊。

每次可以从一个走廊格子走到四连通相邻格子。

每次一名顾客从最左下角的格子出发，试图找到最优的一个满足自己容忍条件的空座位。容忍条件形如桌子上坐了几人以及自己因此应该去哪里（请参考原题面）。

此外还会有部分座位突然出现或消失顾客，也即状态翻转。

输出每次顾客坐到了哪里，以及突然变化的顾客是来是去。

操作次数 $q$ 不超过 $5 \times 10^5$。第二类操作值域不超过 $10^4$ 且总是修改在餐桌处。3s/1GB。

思路

本题总体思路比较简单，这里直接给出完整版正解做法。

注意到第一类操作可能遇上的下标范围是 $O(\sqrt{q})$ 级别的，我们不妨考虑做预处理。

观察到其优先顺序是固定的，我们可以预先排序得到各个餐桌格子的优先顺序。这个排序可以通过数学方法或者 bfs 做到线性。

考虑第一类操作，我们可以用 set 或可删堆（对顶堆）存一下每个满足对应条件的位置。

第二类操作对于下标超界的部分也可以单独拿一个 set 存；没超界的部分可以和前面的部分使用同一套方法处理。

不用太多卡常，验题人开了八九个 set 都过了。std 不到 2kb。

本题非常善良，值域只开 $10^4$ 是为了方便压位（记得用 $10001$ 压）。没有特意卡 umap/bitset 之类的东西，应该是可以轻松过的。

总结

• 在这样一场毒瘤的比赛中，
• 这道题目无疑是出题人无私的馈赠，
• 经典的模型、较低的难度和不大的代码量，能帮助你把分数收入囊中
• 出题人相信，这个美妙的题目，可以给拼搏于 XCPC 的追梦之路上的你，提供一个有利的援助。