25120번 - Counting Rectangles 서브태스크다국어

For two arrays of integers $A$ of size $N$ and $B$ of size $M$, we define a grid $G(A, B)$ of size $N \times M$, where cell $(i,\, j)$ is colored black if $0 \le A_i + B_j$ and white otherwise.

We also define $F(A, B)$ as the number of black rectangles inside $G(A, B)$, where each cell of $G(A, B)$ is either entirely included in or disjoint with the rectangle.

In other words, $F(A, B)$ is equal to the number of tuples $(l_1,\, r_1,\, l_2,\, r_2)$ such that $1 \le l_1 \le r_1 \le N$, $1 \le l_2 \le r_2 \le M$ and each cell $(i,\,  j)$ in $G(A, B)$ is colored black for all $i$, $j$ such that $l_1 \le i \le r_1$, $l_2 \le j \le r_2$.

Initially, only $A_1$ and $B_1$ are given.

Then, you should process following $Q$ queries:

• 0 $v$: append $v$ to current array $A$.
• 1 $v$: append $v$ to current array $A$. Then, print $F(A, B)\bmod 998\,244\,353$.
• 2 $v$: append $v$ to current array $B$.
• 3 $v$: append $v$ to current array $B$. Then, print $F(A, B)\bmod 998\,244\,353$.

The first line contains one integer $Q$.

The second line contains two space-separated integers, $A_1$ and $B_1$.

Each of the following $Q$ lines contains two space-separated integers denoting the queries in the described form.

For each query of types 1 and 3, output a single integer denoting the answer to that query. Each answer should go on its own line.

Let $N$ be the size of array $A$ after processing all queries, and $M$ be the size of array $B$ after processing all queries.

• $1 \le N \le 250\,000$
• $1 \le M \le 250\,000$
• $1 \le Q = N + M - 2$
• $-10^9 \le A_{i} \le 10^9$ $(1 \le i \le N)$
• $-10^9 \le B_{i} \le 10^9$ $(1 \le i \le M)$
• The last query has a type of 1 or 3.

This subtask has additional constraints:

• $N \le 2\,500$
• $M \le 2\,500$

This subtask has an additional constraint:

• Every query except the last one has type of 0 or 2.

This subtask has no additional constraints.