不看评论还真不知道哪错了。。。

R和r打反，调了俩小时。。

心疼一波yzh

double大法好，二分答案好，人在做，诚在看，STL留祸患，边界爆炸天地灭，实数运算保平安，诚心诚念double好，相加除2大法平安保，众生都为AC来，现世险恶忘前缘，OI弟子说真相，教你写题莫拒绝

Update忘把lazy赋成-1，WA死了

全是0或1的RE了一次，真是要长记性了

区间全是1和区间全是0的把我E了4个点。。

用splay代替线段树的作死失败...

重写第四遍终于A了......mdzz好激动......
还有......rank1这样抄我代码完了再打表是会掉人品的

可以直接Ctrl+C的样例：
6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3
5

这是省选吗？这道题不是经典题目吗？不敢相信……

回复 @liu_runda :
所以我觉得上当了= =

回复 @叶子の宿敌 :
省选重测后sort暴力也是80

官方题解用的是二分答案。
设二分的答案为$a$，将整个序列中>=$a$的值变为1，<$a$的变成0，对于每次部分排序，可以通过线段树的区间更新实现，若为升序则把区间内0全部排在前边，1排在后边，反之亦然。全部部分排序结束后检查p上的值是1还是0，从而继续调整下一次二分。
总时间复杂度:$O(mlog^2n)$.
ps:真的是$log^2n$,不是$log_2n$......
pss:其实当时想到了线段树，然而没有二分答案线段树根本无从谈起，最后用的$O(nm)$的桶排暴力，数据过鶸成功骗到80分