P11702 [ROIR 2025] 不平衡划分题目背景翻译自 ROIR 2025 D2T2。题目描述给定一个非负整数数组[ a 1 , a 2 , … , a n ] [a_1, a_2, \dots, a_n][a1​,a2​,…,an​]。考虑将该数组划分成k kk个非空的连续子段。我们称划分方案的“不平衡度”为这些子段和中的最大值与最小值之差。你需要求出将该数组划分成k kk个子段时的最大不平衡度。例如如果数组为[ 2 , 1 , 3 , 4 ] [2, 1, 3, 4][2,1,3,4]k 2 k2k2则划分为[ 2 , 1 , 3 ] [ 4 ] [2, 1, 3][4][2,1,3][4]时不平衡度为6 − 4 2 6 - 4 26−42划分为[ 2 , 1 ] [ 3 , 4 ] [2, 1][3, 4][2,1][3,4]时不平衡度为7 − 3 4 7 - 3 47−34划分为[ 2 ] [ 1 , 3 , 4 ] [2][1, 3, 4][2][1,3,4]时不平衡度为8 − 2 6 8 - 2 68−26。其中最后一种情况的不平衡度最大。输入格式第一行输入两个整数n nn和k kk2 ≤ k ≤ n ≤ 300000 2 \le k \le n \le 3000002≤k≤n≤300000分别表示数组的长度和需要划分的子段的数量。第二行包含n nn个整数a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1​,a2​,…,an​0 ≤ a i ≤ 10 9 0 \le a_i \le 10^90≤ai​≤109。输出格式输出一个整数即将该数组划分为k kk个子段时的最大不平衡度。输入输出样例 #1输入 #14 2 2 1 3 4输出 #16输入输出样例 #2输入 #25 4 2 1 3 4 1输出 #26说明/提示在样例二中最优划分方案是[ 2 ] [ 1 ] [ 3 , 4 ] [ 1 ] [2][1][3, 4][1][2][1][3,4][1]。其中最大子段和为3 4 7 3 4 7347最小子段和为1 11因此不平衡度为7 − 1 6 7 - 1 67−16。本题使用 Subtask 捆绑测试。数据中 Subtask 0 是样例。子任务分数特殊性质1 1111 1111n ≤ 15 n \le 15n≤152 2211 1111k 2 k 2k23 3321 2121k 3 k 3k34 4415 1515n ≤ 300 n \le 300n≤3005 5521 2121n ≤ 3000 n \le 3000n≤30006 66$ 21 $无C实现#includebits/stdc.husingnamespacestd;typedeflonglongll;constintN3e510;intn,m,k,lg[N];ll a[N],pre[N],lst[N],ans,tmp;ll st[N][20];voidbd_st(){for(inti1;im;i)st[i][0]pre[ik-1]-pre[i-1];intllg[m];for(intj1;jl;j){for(inti1;im-(1j)1;i){st[i][j]max(st[i][j-1],st[i(1(j-1))][j-1]);}}}llgt_ma(intl,intr){rr-k1;intLlg[r-l1];returnmax(st[l][L],st[r-(1L)1][L]);}intmain(){ios::sync_with_stdio(0);cin.tie(0);cinnk;if(k2){for(inti1;in;i){cina[i];tmpa[i];}coutmax(abs(tmp-2*a[1]),abs(tmp-2*a[n]));return0;}kn-k1;mn-k1;for(inti2;im;i)lg[i]lg[i-1](i(1(lg[i-1]1)));for(inti1;in;i)cina[i];for(inti1;in;i)pre[i]pre[i-1]a[i];for(intin;im;i--)lst[i]lst[i1]a[i];bd_st();for(inti1;in;i){tmp0;if(ik)tmpmax(tmp,pre[i-1]);elsetmpmax(tmp,gt_ma(1,i-1));if(im)tmpmax(tmp,lst[i1]);elsetmpmax(tmp,gt_ma(i1,n));tmp-a[i];ansmax(ans,tmp);}coutans;return0;}