P16446 [XJTUPC 2026] Shura Index.

You are playing a “multi-character romance simulation game” and are trying to romance $N$ characters at the same time. For the $i$-th character, there are two key values: - $a_i$: her tolerance toward you; - $b_i$: her expectation of you. Initially, the status of all characters is given and **identical**: $a_i = A, b_i = B$ ($1\le i \le N$). Next, you will perform $Q$ actions. Each action is one of the following three types: - $1\ r\ x$: you “mess up collectively” with the first $r$ characters, causing their tolerance to decrease. That is, for all $i$ ($1\leq i\leq r$), $a_{i} \gets \min \{ a_{i}, x \}$. - $2\ l\ x$: you give gifts to the $l$-th through the $N$-th characters, causing their expectations to increase. That is, for all $i$ ($l\leq i \leq N$), $b_{i} \gets \max \{ b_{i}, x \}$. - $3\ l\ r$: query the “Shura Index” of the $l$-th through the $r$-th characters. The “Shura Index” is defined as $\sum_{i=l}^r |a_{i}-b_{i}|$.

The first line contains three integers $N, A$ and $B$ ($1\le N\le 5 \times 10^5, -10^9\le A,B\le 10^9$), separated by a single space, representing the number of characters, the initial tolerance value, and the initial expectation value. The second line contains an integer $Q$ ($1\le Q\le 5 \times 10^5$), indicating the number of actions. The next $Q$ lines each contain three integers separated by a single space. These three integers correspond to one of the following cases, representing one action: - $1\ r\ x$ ($1\le r\le N, -10^9 \le x \le 10^9$), meaning that for all $i$ ($1\leq i\leq r$), $a_{i} \gets \min \{ a_{i}, x \}$. - $2\ l\ x$ ($1\le l\le N, -10^9 \le x \le 10^9$), meaning that for all $i$ ($l\leq i \leq N$), $b_{i} \gets \max \{ b_{i}, x \}$. - $3\ l\ r$ ($1\le l\le r\le N$), meaning to query the “Shura Index” $\sum_{i=l}^r |a_{i}-b_{i}|$ for the $l$-th through the $r$-th characters.

For each action that queries the “Shura Index”, output one line containing one integer, representing the value of the “Shura Index”.

Translated by ChatGPT 5