题目
ftiasch 18岁生日的时候，lqp18_31给她看了一个神奇的序列 A1, A2, ..., AN. 她被允许选择不超过 M 个连续的部分作为自己的生日礼物。
自然地，ftiasch想要知道选择元素之和的最大值。你能帮助她吗？
输入格式
第1行，两个整数 N (1 ≤ N ≤ 105) 和 M (0 ≤ M ≤ 105), 序列的长度和可以选择的部分。
第2行， N 个整数 A1, A2, ..., AN (0 ≤ |Ai| ≤ 104), 序列。
输出格式
一个整数，最大的和。
输入样例
5 2
2 -3 2 -1 2
输出样例
5
题解
我们把连续的同号元素合并
得到的序列就是正负交错的序列
加入正数数量<=m，全部选掉就是答案
若正数数量>m，就对于某些数意味着
①不选该正数
②多选一个负数使得相邻正数相连，这样相当于可以少放弃一个正数
我们先将正数总和求出来
然后将所有数的绝对值加入小根堆
每次选出一个减去，然后与邻近的合并【就像选m个不相邻的数和最小一样】
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long int
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
#define ls (u << 1)
#define rs (u << 1 | 1)
#define fa (u >> 1)
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
int pre[maxn],nxt[maxn],val[maxn],n,m,A[maxn],V[maxn],tot,cnt;
struct node{int v,u;}H[2 * maxn];
int hsiz,pos[2 * maxn];
int pd(int u){
int small;
while (true){
small = u;
if (ls <= hsiz && H[ls].v < H[small].v) small = ls;
if (rs <= hsiz && H[rs].v < H[small].v) small = rs;
if (small != u){
pos[H[small].u] = u; pos[H[u].u] = small;
swap(H[small],H[u]);
u = small;
}else break;
}
return u;
}
void pup(int u){
while (u > 1 && H[fa].v > H[u].v){
pos[H[fa].u] = u; pos[H[u].u] = fa;
swap(H[fa],H[u]);
u = fa;
}
}
void ins(int u){
H[++hsiz] = (node){val[u],u}; pos[hsiz] = u;
pup(hsiz);
}
void del(int u){
pos[H[hsiz].u] = u;
swap(H[u],H[hsiz--]);
u = pd(u);
pup(u);
}
int main(){
n = read(); m = read();
REP(i,n){
A[++tot] = read();
if (!A[tot]) tot--;
}
int x = 1;
while (A[x] < 0 && x <= tot) x++;
if (x > tot) {puts("0"); return 0;}
V[n = 1] = A[x];
while (A[tot] < 0 && tot) tot--;
if (!tot) {puts("0"); return 0;}
for (int i = x + 1; i <= tot; i++){
if ((A[i] < 0 && A[i - 1] < 0) || (A[i] > 0 && A[i - 1] > 0))
V[n] += A[i];
else V[++n] = A[i];
}
cnt = n / 2 + 1;
if (cnt <= m){
sort(V + 1,V + 1 + n);
int ans = 0;
for (int i = 0; i < cnt && V[n - i] > 0; i++) ans += V[n - i];
printf("%d\n",ans);
}else {
int ans = 0;
for (int i = 1; i <= n; i++){
if (V[i] > 0) ans += V[i];
val[i] = abs(V[i]);
if (i > 1) pre[i] = i - 1;
if (i < n) nxt[i] = i + 1;
ins(i);
}
int t = cnt - m,x; node u;
while (t--){
u = H[1]; x = u.u;
ans -= u.v;
if (!pre[x]){
del(1); del(pos[nxt[x]]);
pre[nxt[nxt[x]]] = 0;
}else if (!nxt[x]){
del(1); del(pos[pre[x]]);
nxt[pre[pre[x]]] = 0;
}else {
int l = pre[x],r = nxt[x];
del(pos[l]); del(pos[r]);
H[1].v = val[x] = val[l] + val[r] - val[x]; pos[x] = 1;
pd(1);
nxt[pre[x] = pre[l]] = x;
pre[nxt[x] = nxt[r]] = x;
}
}
printf("%d\n",ans);
}
return 0;
}