P8493 [IOI 2022] Digital Circuit

**Due to technical limitations, please do not use C++ 14 (GCC 9) to submit this problem.** This is an interactive problem. You only need to implement the functions required in the code. Your code does not need to include any extra header files, and you do not need to implement the `main` function. Since this problem has too many test points, considering the current Luogu judging implementation, this problem will not be scored by the subtasks given in the statement.

There is a digital circuit consisting of $N + M$ **gates** numbered from $0$ to $N + M - 1$. Gates $0$ to $N - 1$ are **threshold gates**, and gates $N$ to $N + M - 1$ are **input gates**. Every gate except gate $0$ is an **input** of exactly one threshold gate. Specifically, for each $i$ with $1 \le i \le N + M - 1$, gate $i$ is an input of gate $P[i]$, where $0 \le P[i] \le N - 1$. Importantly, it is guaranteed that $P[i] \lt i$. Also, assume $P[0] = -1$. Each threshold gate has one or more inputs. Input gates have no inputs. Each gate has a **state**, either $0$ or $1$. The initial states of input gates are given by an array $A$ of $M$ integers. That is, for each $j$ with $0 \le j \le M - 1$, the initial state of input gate $N + j$ is $A[j]$. The state of each threshold gate depends on the states of its inputs as follows. First, each threshold gate is assigned a threshold **parameter**. For a threshold gate with $c$ inputs, the assigned parameter must be an integer between $1$ and $c$ (inclusive). Then, for a threshold gate with parameter $p$, if at least $p$ of its input gates have state $1$, the threshold gate’s current state is $1$; otherwise, its state is $0$. For example, suppose $N = 3$ threshold gates and $M = 4$ input gates. Gate $0$ has inputs gates $1$ and $6$, gate $1$ has inputs gates $2$, $4$, and $5$, and gate $2$ has only one input gate $3$. An illustration of this example is shown in the figure below.  Assume input gates $3$ and $5$ have state $1$, while gates $4$ and $6$ have state $0$. Suppose threshold gates $2$, $1$, $0$ are assigned parameters $1$, $2$, $2$, respectively. In this case, gate $2$ has state $1$, gate $1$ has state $1$, and gate $0$ has state $0$. The following figure shows the parameter assignment and the resulting states. Gates with state $1$ are colored black.  The states of input gates will go through $Q$ updates. Each update is described by two integers $L$ and $R$ ($N \le L \le R \le N + M - 1$), meaning to flip the states of all input gates with indices between $L$ and $R$ (inclusive). That is, for all $i$ with $L \le i \le R$, if input gate $i$ has state $0$ it will be flipped to $1$; if it has state $1$ it will be flipped to $0$. After being flipped, each gate stays in the new state until it is flipped again in some later update. Your goal is to compute, after each update, how many assignments of threshold-gate parameters make gate $0$ have state $1$. Two parameter assignments are considered different if at least one threshold gate has a different parameter. Since the number of assignments can be large, you need to output it modulo $1\;000\;002\;022$. Note that in the example above, there are $6$ different assignments of threshold-gate parameters in total, because gates $0$, $1$, $2$ have $2$, $3$, $1$ inputs, respectively. Among these $6$ assignments, there are $2$ assignments that make gate $0$ have state $1$.

Your task is to implement the following two functions. ```go void init(int N, int M, int[] P, int[] A) ``` - $N$: the number of threshold gates. - $M$: the number of input gates. - $P$: an array of length $N + M$, describing the inputs of threshold gates. - $A$: an array of length $M$, giving the initial states of input gates. - This function is called exactly once, and it is called before any calls to `count_ways`. ```go int count_ways(int L, int R) ``` - $L$, $R$: the states of input gates with indices between $L$ and $R$ will be flipped. - This function should first perform the required update, then return the number of parameter assignments that make gate $0$ have state $1$, modulo $1\;000\;002\;022$. - This function will be called exactly $Q$ times.

Consider the following sequence of function calls: ```go init(3, 4, [-1, 0, 1, 2, 1, 1, 0], [1, 0, 1, 0]) ``` The statement has already explained this example. ```go count_ways(3, 4) ``` This call flips the states of gates $3$ and $4$, meaning gate $3$ becomes $0$ and gate $4$ becomes $1$. The following shows two valid parameter assignments that can make gate $0$ have state $1$. | Assignment $1$ | Assignment $2$ | | :------------------------------------: | :------------------------------------: | |  |  | In all other parameter assignments, gate $0$ has state $0$. Therefore, the function should return $2$. ```go count_ways(4, 5) ``` This call flips the states of gates $4$ and $5$. As a result, all input gates have state $0$, and for every parameter assignment, gate $0$ has state $0$. Therefore, the function should return $0$. ```go count_ways(3, 6) ``` This call sets all input gates to state $1$. As a result, for every parameter assignment, gate $0$ has state $1$. Therefore, the function should return $6$.

### Constraints - $1 \le N, M \le 10^5$. - $1 \le Q \le 10^5$. - $P[0] = -1$. - $0 \le P[i] \lt i$ and $P[i] \le N - 1$ (for all $i$ with $1 \le i \le N + M - 1$). - Each threshold gate has at least one input (for every $i$ with $0 \le i \le N - 1$, there exists an index $x$ such that $i \lt x \le N + M - 1$ and $P[x] = i$). - $0 \le A[j] \le 1$ (for all $j$ with $0 \le j \le M - 1$). - $N \le L \le R \le N + M - 1$. ### Subtasks 1. (2 points) $N = 1$, $M \le 1000$, $Q \le 5$. 2. (7 points) $N, M \le 1000$, $Q \le 5$, each threshold gate has exactly two inputs. 3. (9 points) $N, M \le 1000$, $Q \le 5$. 4. (4 points) $M = N + 1$, $M = 2^z$ (for some positive integer $z$), $P[i] = \lfloor\frac{i - 1}{2}\rfloor$ (for all $i$ with $1 \le i \le N + M - 1$), $L = R$. 5. (12 points) $M = N + 1$, $M = 2^z$ (for some positive integer $z$), $P[i] = \lfloor\frac{i - 1}{2}\rfloor$ (for all $i$ with $1 \le i \le N + M - 1$). 6. (27 points) Each threshold gate has exactly two inputs. 7. (28 points) $N, M \le 5000$. 8. (11 points) No additional constraints. ### Sample Grader The sample grader reads input in the following format: - Line $1$: $N \; M \; Q$. - Line $2$: $P[0] \; P[1] \; \ldots \; P[N + M - 1]$. - Line $3$: $A[0] \; A[1] \; \ldots \; A[M - 1]$. - Line $4 + k$ ($0 \le k \le Q - 1$): $L \; R$ for the $k$-th update. The sample grader prints your answers in the following format: - Line $1 + k$ ($0 \le k \le Q - 1$): the return value of `count_ways` for the $k$-th update. ### Conventions When giving function interfaces, the statement uses generic type names `void`, `bool`, `int`, `int[]` (array), and `union(bool, int[])`. In C++, the grader will use suitable data types or implementations as shown in the table below: | `void ` | `bool` | `int` | `int[]` | | ------- | ------ | ------| ------------------ | | `void ` | `bool` | `int` | `std::vector` | | `union(bool, int[])` | Length of array `a` | | -------------------------------------- | ------------------- | | `std::variant` | `a.size()` | In C++, `std::variant` is defined in the header ``. A function with return type `std::variant` can return either a `bool` or a `std::vector`. The following sample code shows three functions that return `std::variant`, and all of them work correctly: ```cpp std::variant foo(int N) { return N % 2 == 0; } std::variant goo(int N) { return std::vector(N, 0); } std::variant hoo(int N) { if (N % 2 == 0) { return false; } return std::vector(N, 0); } ``` Translated by ChatGPT 5