[Ctsc2013]没头脑和不高兴 - Problem

没头脑和不高兴是一对形影不离的好朋友，他们一起上学也一起玩耍。这天，这对好朋友聚在一起玩纸牌游戏。

他们所玩的纸牌总共有N张，每一张上面都有一个1N 的数组，任意两张纸牌上的数字都不相同。根据他们制定的游

戏规则，在每局游戏的开始，所有的牌需要按照从1N 的顺序排好。在开心地完了一局牌之后，他们发现牌的顺序

被弄得乱七八遭，将它们排好序是一件挺麻烦的事情。他们讲凌乱的纸牌在桌面上排成一排，然后开始了排序工

作。不高兴由于在上一局游戏中输了牌，非常不高兴。他只将其中((奇数位置)) 的牌排成了升序，然后把剩下的

任务推给了没头脑。没头脑非常没头脑，他采取了一个有些笨的排序方式。每次，他找到两张相邻并且顺序不对

的牌交换他们，直到整个序列被排好序为止。乐于探究的你，想要研究在初始排列随机的情况下没头脑花在交换

纸牌上的时间。假设没头脑每交换一对纸牌花费的时间为 1，你希望求出他排序时间的期望。此外，为了更好地

分析这个问题，你还希望能够计算出所花时间的方差。更进一步地，如果((被不高兴排好序的位置发生了变化))，

你是否还能求出没头脑用来排序的时间期望呢？

输入文件共 M+1 行。

第一行包含两个正整数 N,M。

接下来M行，每行包含三个整数l,r,v。其中 1 <=_l<= r<= N,?v属于{1,N}

若v=0则表示不高兴不再对l 到r之间的位置排序；反之若v=1则表示被不高兴排序的位置将涵盖 l到r。

输出文件共M+2行。每行输出一个形如p/q的有理数，其中gcd(p,q )=1, q>=1,p,q为整数。

第一行输出在初始条件下没头脑排序时间的期望。

第二行输出在初始条件下没头脑排序时间的方差。

接下来Ｍ行，每行分别输出在对不高兴排序的位置进行了前若干次修改之后没头脑排序时间的期望。

33
230 221 131
2.5

2/3
2/9
3/2
1/1
0/1

N<=100000, M=10^5

黑暗爆炸OJ