我一开始还在想我是不是看错题了= =

谨以此题纪念我们的WC2017
本题是对WC2017的T2的继承（和发扬？），所以请大家不要裱我，要裱就裱wys！
UPD:感谢驴蛋蛋，为我提供了一个更好的优化方法，使得标称速度提高了4倍左右，由于原时限没有改，所以现在我可以骄傲地说：
我开了[size=50]5倍时限![/size]
题解如下：
这就是一个模拟，但需要优化时间和空间（是不是像极了WC2017_T2呢？）
关于时间的优化，你需要完成一些基于CPU性能的程序底层优化,如：数组下标访问的连续性。具体详见WC2017某松同学的论文+机智的驴蛋蛋。
关于空间的优化，考虑到膜数最大为61,61+61=122<128,所以我们可以用char数组来存储DP数组，这样就可以把内存开销最大的东西一下子降到1/4.

啊，堆的常数有毛病

回复 @FoolMike :
出这道题的学长已经退役了。

数据有误，请您手算一下第一组数据，正确的答案应该是4
方案如下：
将9号点的权值改为-1e9，将2号点的权值改为1e9，将7号点的权值改为1e9，将4号点的权值改为16
这个方案是合法的，修改次数为4，而数据中答案为6，请您修正！

本题数据与题目说的不符！！
A只有10分，也就是说写了A和B加上C的50%并不能得到那“精神80分”，而是70分！
好了，自己弱怨不得造数据的人，毕竟这个题数据不是很好造。

方案数mod 1004535809(479 * 2 ^ 21 + 1)

你们真是卡的一手好常...

来一发线段树吧
虽说我并没有用

一颗普通的线段树
评测的时候差点以为T掉了

这个有nlogn的多项式求逆做法

回复 @TenderRun : @TenderRun
能解释一下您代码中的v1,v2,u1,u2,Mx,sum的含义吗？
顺道说一下下面代码的含义。
谢谢。

for(int i=1;i<=top;i++){

 sum+=b[i-1];

 u1[i]=max(u1[i-1],sum+dis[stack[i]]);

 v1[i]=max(v1[i-1],sum+dis[stack[i]]+Mx);

 Mx=max(Mx,dis[stack[i]]-sum);

 }

 

700题留念，感谢神犇Itachi的悉心教导！

居然还挂了几次

贪心233

用堆水过了，虽然代码长，不过不用几何了。。。
合并重复+堆+并查集

回复 @FoolMike :
并不知道为什么……反正打表观察运算次数和实测都表明复杂度大概是$O(n\log\log n)$……

mdzz，B数据的过了，A数据的暴力却不对！！而且又是玄学问题，本机能过，交上去就WA。。

回复 @AntiLeaf :
质数的个数是O(n/logn)的，然后每个质数p需要O(n/p)的时间处理，我怎么觉得是O(nlogn)的复杂度啊