F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 3148. -- [Ctsc2013]没头脑和不高兴

3148: [Ctsc2013]没头脑和不高兴

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 65  Solved: 39
[Submit][Status][Discuss]

Description

没头脑 和不高兴 是一对形影不离的好朋友,他们一起上学也一起玩耍。这天,这对好朋友聚在一起玩纸牌游戏。
他们所玩的纸牌总共有N张,每一张上面都有一个1N 的数组,任意两张纸牌上的数字都不相同。根据他们制定的游
戏规则,在每局游戏的开始,所有的牌需要按照从1N 的顺序排好。在开心地完了一局牌之后,他们发现牌的顺序
被弄得乱七八遭,将它们排好序是 一件挺麻烦的事情。他们讲凌乱的纸牌在桌面上排成一排,然后开始了排序工
作。不高兴 由于在上一局游戏中输了牌,非常不高兴。他只将其中((奇数位置)) 的牌排成了升序,然后把剩下的
任务推给了没头脑。没头脑 非常没头脑,他采取了一个有些 笨的排序方式。每次,他找到两张相邻并且顺序不对
的牌交换他们,直到整个 序列被排好序为止。乐于探究的你,想要研究在初始排列随机的情况下没头脑 花在交换
纸牌上的时间。假设没头脑 每交换一对纸牌花费的时间为 1,你希望求出他排序时间的期望。此外,为了更好地
分析这个问题,你还希望能够计算出所花时间的方差。更进一步地,如果((被不高兴排好序的位置发生了变化)),
你是否还能求出没头脑 用来排序的时间期望呢?

Input

输入文件共 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为整数。

Output

第一行输出在初始条件下没头脑 排序时间的期望。 
第二行输出在初始条件下没头脑 排序时间的方差。
接下来M行,每行分别输出在对不高兴 排序的位置进行了前若干次修改之 后没头脑 排序时间的期望。

Sample Input

33
230 221 131
2.5

Sample Output

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

HINT


N<=100000, M=10^5

Source

[Submit][Status][Discuss]

HOME Back