这道题的核心是在区间中排除最大的$k$个元素后，找到剩余元素总和的最大值，关键在于利用$k$的上限（$k \leq 100$）设计高效算法，避免暴力枚举所有区间。

一、问题转化与核心思路

1. 目标公式：对于任意区间$[l, r]$（满足$r-l+1 \geq k$），沃瓦的快乐值 = 区间总和 - 区间内最大$k$个元素的和。
2. 关键约束：$k$最大为100，远小于$n$（$2 \times 10^5$），因此可围绕“固定右边界，向左扩展区间并维护最大$k$个元素”展开，时间复杂度能控制在$O(nk)$，满足数据规模要求。
3. 特殊情况：当$k=0$时，问题退化为经典“最大子数组和”，直接用Kadane算法求解。

二、算法设计

1. 基础工具准备

• 前缀和数组：快速计算任意区间$[l, r]$的总和，公式为sum(l, r) = prefix[r+1] - prefix[l]（前缀和数组prefix[0]=0，prefix[i] = a[0]+a[1]+...+a[i-1]）。
• 双数组维护最大$k$个元素：
  • big数组：存储当前区间内最大的$k$个元素，按升序排列，方便快速替换较小元素。
  • small数组：存储当前区间内剩余元素，按降序排列，方便快速移除被移入big的元素。
  • 两个数组的和分别记为sum_big和sum_small，当前区间沃瓦的快乐值即sum_small。

2. 核心步骤

1. 预处理前缀和数组，计算所有区间的总和。
2. 枚举每个右边界$r$（从$0$到$n-1$，0-based索引）：
   • 将当前元素$a[r]$加入small数组并排序，更新sum_small。
   • 若small的长度超过$k$（即当前区间长度超过$k$），需将small中最大的元素移入big（保证big始终是最大的$k$个元素），并更新两个数组的和。
   • 若当前区间长度$\geq k$，计算sum_small，并更新全局最大值。
3. 输出全局最大值。

三、实现代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);  
    
    int n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    if (k == 0) {
        ll max_sum = a[0];
        ll current_sum = a[0];
        for (int i = 1; i < n; ++i) {
            current_sum = max(a[i], current_sum + a[i]);
            max_sum = max(max_sum, current_sum);
        }
        cout << max_sum << "\n";
        return 0;
    }
    
    ll max_result = -1e18; 
    vector<ll> big;        
    vector<ll> small;     
    ll sum_big = 0;        
    ll sum_small = 0;      
    
    for (int r = 0; r < n; ++r) {
        small.push_back(a[r]);
        sum_small += a[r];
        sort(small.rbegin(), small.rend());  
        
        while (small.size() > k) {
            ll val = small[0]; 
            small.erase(small.begin()); 
            sum_small -= val;
          
            big.push_back(val);
            sum_big += val;
            sort(big.begin(), big.end());  
        }
        if (r + 1 >= k) {
            if (sum_small > max_result) {
                max_result = sum_small;
            }
        }
    }
    
    cout << max_result << "\n";
    return 0;
}

四、复杂度分析

• 时间复杂度：$O(nk)$。枚举右边界$r$需$O(n)$次，每次插入元素后排序的耗时因数组长度最大为$k$，故单次排序为$O(k \log k)$，但实际因每次仅插入1个元素，平均耗时可近似为$O(k)$，整体复杂度满足$n=2 \times 10^5$的要求。
• 空间复杂度：$O(k)$。big数组最大长度为$k$，small数组最大长度为$k$，额外空间仅依赖$k$，非常高效。

五、算法标签

• 单调队列
• 滑动窗口
• 前缀和
• 堆/ 优先队列
• 动态规划
• 双指针

六、关键正确性说明

1. 元素移动逻辑：始终将small中最大的元素移入big，保证big存储的是当前区间内最大的$k$个元素，small存储剩余元素，符合“排除最大$k$个”的需求。
2. 区间覆盖：通过固定右边界$r$、向左扩展区间的方式，覆盖了所有可能的有效区间$[l, r]$（$l \leq r$且$r-l+1 \geq k$），确保不会遗漏最优解。