好可怕，居然不预处理就会渣精度。。

回复 @小一米 :
已修正。
是这样的，一开始忘记给L<R了，然后您说应该是n*(n+1)/2个，我就脑袋一热把题面改了。。实际上应该补上L<R不过没关系，反正答案就差个n嘛（逃

回复 @小一米 :
打乱后题目编号为:4 2 3 1 5
共有10种不同的区间，其中只有[3,5]这个区间不满足要求，因为此时3,4,5形成了3个区间。
所以概率为0.900000000000,在乘n*(n-1)/2后为9

回复 @FoolMike :
考试时候ls和rs数组忘记乘2了。。成功炸成80

回复 @小一米 :
抱歉，再次翻车，这个样例是用旧翻车的标程写的。。
UPD：已经搞好了。。希望这次不要翻车了。《论出题没人验题的危害》

回复 @小一米 :
额，抱歉翻车了！！我数据生成器写的

 printf("%d %d %d\n",x0,a,b,c);

 printf("%d %d %d\n",y0,u,v,w);

等下我修改一下样例和数据。。
UPD:已修正,谢！

提示里面"wys"的意思是希望你使用上一个数据的算法+wys优化通过这一测试点。
放心，我开的标程3倍时限，绝对不卡常，这样做只是鼓励下暴力+卡常玩家而已。。
话说标程用的cin,cout会不会被嫌弃呢？(实际上是因为造数据的电脑视64位机，我却用32dev...)

钢哥好！

把FFT次数减少到3次，效果拔群

回复 @常可神犇2017高���夺魁 :
看这数据范围，您是指LCT是暴力吗？

DP套DP，惊为天人!

难道现在cogs不是linux了？为什么一些10W，20W的题就会爆栈？

本题本机1s就能过的，但这里死活2.5s~3.0s所以开了5s时限，希望写部分分的童鞋不要卡评测鸡。

同没有spj。

这道题从uoj上过了后来这里连着M3次（uoj算得是使用的内存）

用map其实也不慢，而且好写的很。

有两个lyc!! @Sky_miner

回复 @FoolMike :
哇，好强啊！！
跑了下10^14我的算法跑了19999999次，您的只跑了87719次，简直高明到不知道哪里去了！
UPD：又试了几个数据，发现您的计算次数是n^(1/3)级别的（否则怎么可能10^7*cmath::sqrt()跑得过1s呢！

回复 @FoolMike :
预处理是sqrt(n)的，不过应该比计算结果的还快，毕竟cmath::sqrt()不能当成O(1)的

明明我写的也是sqrt(n)的，为什么被卡常了。。