~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~
2019寒假集训题
C.Max Sum Plus Plus
题面
Now I think you have got an AC in Ignatius.L’s “Max Sum” problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem.
Given a consecutive number sequence $S_1,S_2,S_3,S_4…S_x,…S_n$. We define a function $sum(i,j)=S_i+…+S_j$($1\leq i\leq j\leq n$).
Now given an integer m ($m > 0$), your task is to find $m$ pairs of $i$ and $j$ which make $sum(i_1,j_1)+sum(i_2,j_2)+…+sum(i_m,j_m)$ maximal ($i_x\leq i_y\leq j_x\ or\ \ i_x\leq j_y\leq j_x$ is not allowed).
But I’m lazy, I don’t want to write a special-judge module, so you don’t have to output $m$ pairs of $i$ and $j$, just output the maximal summation of $sum(i_x,j_x)$($1\leq x\leq m$) instead.
简要翻译
给出一列数$\{a_n\}$ ，从中选出$𝑚$个互不相交的子段，使得和最大，求这个最大值。
Input
对于每组数据，都占一行。
每一行前面有两个整数$m,n$，之后又$n$个整数$S_1,S_2,S_3…S_n$直到文件结束。
Output
每组数据输出一个数表示答案。
Sample Input
1 3 1 2 3
2 6 -1 4 -2 3 -2 3
Sample Output
6
8
Hint
输入数据很大，$scanf$什么的可能会被卡掉哦~
$1\leq m\leq n\leq 1,000,000,-32768\leq S_x\leq32767$
如果正整数的个数小于$m$个，那么只要选取前$m$大的数即可。
我们就能够由这样的思想来想到用线段树维护这个序列，每一次选取整个序列的最大子段，将和累加到答案中。
然后我们把这段正题都$×(-1)$，下次再次选中，那么就去掉原来所选的部分，这样就很巧妙的采用了题意。
我们操作$m$次，如果遇到了负数，那么就已经可以停止了(负数只会使答案更小)，因为此时我们已经得到了答案。
如果正整数的个数大于等于$m$，那么最终选取的段数一定大于$m$，那么我们就能够拆成$m$段。
所以我们就需要维护区间最大、最小值，区间前缀最大、最小值，区间后缀最大、最小值(我们$×(-1)$的操作需要维护最小值)。
总时间复杂度为$O(m\ logn)$。
Code
1 | //我我我…………懒得打………… |