[Ctsc2013]没头脑和不高兴

题目描述

没头脑 和不高兴 是一对形影不离的好朋友，他们一起上学也一起玩耍。
这天，这对好朋友聚在一起玩纸牌游戏。他们所玩的纸牌总共有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

---

题目来源

没有写明来源