P8936 [JRKSJ R7] Moonlit Dazzle.

 The light and lively music strengthens your determination to solve an easy problem. (The background image comes from a Phigros song illustration. If there is any infringement, please inform the problem setter.)

You have a sequence $a$ of length $n$, with all initial values equal to $0$. You have an operation sequence of length $m$. The $i$-th operation has three parameters $l_i, r_i, x_i$, meaning that for all $j \in [l_i, r_i]$, set $a_j \gets \max(a_j, x_i)$. Let $\text{sol}(l,r)$ denote the sequence $a$ after applying operations $l$ through $r$ in order. You need to answer how many pairs $(l,r)$ satisfy $1 \le l \le r \le m$ and $\text{sol}(l,r) = \text{sol}(1,m)$. Let $f_i$ be the number of $k$ with $i \le k \le m$ such that $\text{sol}(i,k) = \text{sol}(1,m)$. You also need to output the values of $\displaystyle\bigoplus_{i=1}^m f_i \times i$ and $\displaystyle\sum_{i=1}^m f_i \times i$. All answers should be output modulo $2^{32}$.

The first line contains two integers $n, m$. The next $m$ lines each contain three integers $l_i, r_i, x_i$, describing the $i$-th operation.

Output three integers in one line, representing the answers modulo $2^{32}$.

Idea: cyffff, Solution: Ntokisq / abruce, Code: cyffff, Data: cyffff. **Moonlit Dazzle - Tsukimi Shizuka vs. LUNARiUM (Insane14.8)** **The input and output files for this problem are large, so please use appropriate I/O methods.** ### Sample Explanation For sample $2$, the final sequence $a$ is $\{2,2,3\}$. It is easy to see that applying the operations in $[1,4]$, $[1,5]$, $[2,5]$, $[3,5]$, and $[4,5]$ can all make $a$ the same as the sequence after applying all operations. The answer is $5$. The sequence $f$ is $\{2,1,1,1,0\}$. ### Constraints This problem uses bundled testdata. ::cute-table | $\text{Subtask}$ | $n,m\le$ | Special Constraints | $\text{Score}$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $100$ | None | $10$ | | $2$ | $10^4$ | ^ | $20$ | | $3$ | $3\times10^5$ | Guaranteed $l_i=r_i$ | $10$ | | $4$ | ^ | Guaranteed $x_i=1$ | $10$ | | $5$ | ^ | None | $20$ | | $6$ | $10^6$ | ^ | $30$ | For $100\%$ of the testdata, $1 \le n,m \le 10^6$, $1 \le l_i \le r_i \le n$, $1 \le x_i \le m$. ### Special Scoring This problem enables subtask dependencies, as follows. - For subtask $i \in \{1,3,4\}$, you only need to solve subtask $i$ correctly to get the score of subtask $i$. - For subtask $i \in \{2,5,6\}$, you need to solve all subtasks $j \in [1,i]$ correctly to get the score of subtask $i$. Translated by ChatGPT 5