战绩：
100+100+20+54 = 374
T1
据lxl说是为了成绩好看加的题，难度大概cspjT1
T2
朴素dp然后树状数组优化一下
T3
赛时脑抽链，写了个dp，一直想优化dp，其实贪心就好了，过程更加简洁，优化很显然
先将区间剖分成两段端点\(s_i=s_j\)相同的多条线段
将区间每个点吸附到离他右边最近的一个线段端点
用倍增快速处理出从每个点跳\(2^k\)个区间能碰到的最小的左端点（贪心
对于每个询问倍增跳区间即可
时间复杂度：\(O(m\log n)\)
T4
T3卡太久了，最后看出来和 NOIPT4比赛 差不多，没时间细想了，只写了\(O(n^2)\)
考虑暴力时我们枚举的是断点位置，求的是断点左边，右端点在i上的所有区间最大前缀和的和，右边则是左端点在i上的同理。
考虑单独先去求出对于每种断点时，对左边我们想知道的东西（上文提到的）
假设绿色是已对于断点i-1我们已经确定的最大前缀和，红色则是到i-1时后面部分的总和
对于每个左端点不同的区间，当红色部分和>0时，我们就可以将它接到绿色上成为最大前缀和的一部分，同时维护一下总和就可以了
对于右边的部分同理
用堆打全局标时间复杂度\(O(n\log n)\)
听说还有线性做法用单调栈，不会
标签：前缀,7.25,优化,day2,端点,区间,断点,dp From： https://www.cnblogs.com/Linnyx/p/17580262.html