P5883 [CTSC2013] Not Thinking and Unhappy

Not Thinking and Unhappy are a pair of inseparable good friends. They go to school together and play together. One day, they got together to play a card game. There are a total of $N$ cards, and each card has a number from $1-N$ on it. The numbers on any two cards are different. According to the rules they made, at the start of each round, all cards must be arranged in order from $1-N$. After happily finishing a round, they found that the order of the cards had become a complete mess, and sorting them back is quite troublesome. They laid the messy cards in a row on the table and began sorting. Unhappy, having lost in the last round, was very unhappy. He only sorted the cards in the **odd positions** into increasing order, and then pushed the remaining work to Not Thinking. Not Thinking was really not thinking: he used a somewhat clumsy sorting method. Each time, he finds two adjacent cards that are in the wrong order and swaps them, until the whole sequence is sorted. You, who enjoy exploring, want to study how much time Not Thinking spends swapping cards when the initial permutation is random. Assume each swap costs time $1$. You want to find the expected value of his sorting time. In addition, to analyze this better, you also want to compute the variance of the time spent. Furthermore, if **the positions sorted by Unhappy change**, can you still find the expected sorting time of Not Thinking?

- The input file has $M+1$ lines. - The first line contains two positive integers $N$, $M$. - The next $M$ lines each contain three integers $l$, $r$, $v$. Here $1 \le l \le r \le n$, $v\in\{0,1\}$. If $v=0$, it means Unhappy will no longer sort positions from $l$ to $r$; otherwise, if $v=1$, it means the positions sorted by Unhappy will include $l$ to $r$.

- The output file has $M+2$ lines. Each line outputs a rational number in the form `p/q`, where $\gcd(p,q)=1$, $q \ge 1$, $p,q \in Z$. - The first line outputs the expected sorting time of Not Thinking under the initial condition. - The second line outputs the variance of Not Thinking's sorting time under the initial condition. - The next $M$ lines output, respectively, the expected sorting time of Not Thinking after the first several modifications to the positions sorted by Unhappy.

**Sample Explanation** Under the initial condition, Unhappy will sort the cards at positions $1$ and $3$. For permutations $(1,2,3)$ and $(3,2,1)$, he will make them into $(1,2,3)$, so Not Thinking does not need to do anything. For permutations $(1,3,2)$ and $(2,3,1)$, he will make them into $(1,3,2)$, and Not Thinking needs one swap. For permutations $(2,1,3)$ and $(3,1,2)$, he will make them into $(2,1,3)$, and Not Thinking needs one swap. Therefore, the expected time Not Thinking spends is $\frac{0 \times 2+1 \times 2+1\times 2}{6}=\frac{2}{3}$; the variance is $\frac{ (0-\frac{2}{3})^2 \times 2 + (1-\frac{2}{3})^2 \times 2+(1-\frac{2}{3})^2 \times 2 }{6}=\frac{2}{9}$. After the first modification, Unhappy will only sort position $1$, which is the same as not sorting at all. After the second modification, he will sort positions $1$, $2$. After the last modification, he will sort positions $1$, $2$, $3$, so Not Thinking does not need to participate in sorting at all. Based on this, you can compute the expected sorting time of Not Thinking in the corresponding cases. **Scoring** - If the first two lines are correct but the remaining lines are wrong, you can get $40\%$ of the score. - If the first two lines are wrong but the remaining lines are correct, you can get $50\%$ of the score. - If all output lines are completely correct, you can get $100\%$ of the score. - In all other cases, you get no score. **Constraints** | Test Point ID | Value of $N$ | Value of $M$ | | :----------: | :----------: | :----------: | | $1$ | $4$ | $10$ | | $2$ | $11$ | $100$ | | $3$ | $100$ | $10^3$ | | $4$ | $1001$ | $10^4$ | | $5$ | $78590$ | $10^5$ | | $6$ | $87933$ | $10^5$ | | $7$ | $95000$ | $10^5$ | | $8$ | $99445$ | $10^5$ | | $9$ | $99999$ | $10^5$ | | $10$ | $100000$ | $10^5$ | Translated by ChatGPT 5