34658번 - Kamui 다국어

There is a graph with a total of $2N$ vertices. There are no edges between the $1$st and $N$-th vertices, and there are no edges between the $(N+1)$-th and $2N$-th vertices. That is, the given graph is a bipartite graph.

A sequence of positive integers $a_1, a_2, \cdots, a_N$ is given. For any $(i,j)$ pair with $1 \le i, j \le N$, the necessary and sufficient condition for vertices $i$ and $N+j$ to be connected is that $j \le a_i$.

A total of $Q$ queries are given. Each query is represented by two integers $v$ and $x$, indicating that the value of $a_v$ will be changed to $a_v + x$. It is guaranteed that $x = 1$ or $x = -1$. For each query, you must count the number of cycles of length $4$ in the given graph. Since the count may be large, output the remainder when divided by $998\,244\,353$. Two cycles are considered different if the sets of edges composing them are different.

The first line contains two positive integers $N$ and $Q$, separated by a space.

The second line contains a total of $N$ integers $a_1, a_2, \cdots, a_N$, separated by spaces.

The next $Q$ lines each contain two integers $v$ and $x$ separated by a space. The input on the $i$th line indicates that $a_v$ will be changed to $a_v + x$.

After each query is executed, output the remainder when the number of cycles of length $4$ is divided by $998\,244\,353$ on each line.

• $1 \le N \le 500\,000$, $1\le Q\le 500\,000$
• For each queries, $1 \le v \le N$ and $x \in \left\{ -1, 1 \right\}$.
• After each queries, it is guaranteed that $0\le a_i\le N$ for all $1\le i\le N$.

The set of four edges $\left\{ xy,yz,zw,wx\right\}$ in a graph is considered to be a cycle of length $4$.