题解

有一个很显然的结论：如果 Bob 对其他地方进行操作一定不优。

所以我们就会发现他们的操作如下：

• Alice 找到一个最优点，并进行增加操作。
• Bob 将这个最优点进行减少操作减回来。
• Alice 继续增加，Bob 继续减少，以此类推。

所以答案只和 $k$ 的奇偶性有关。当 $k$ 为偶数时，答案为原数组最大子段和；当 $k$ 为奇数时，只需考虑 Alice 操作即可。

我们可以枚举每个点进行增加操作后最大子段和为多少，显然可以线段树求。

namespace cjdst{
	template <typename T>
	class Segtree{
		std::vector <T> tr, ls, rs, sum;
		std::vector <int> left, right;
		void push_up(int u){
			tr[u] = tr[u << 1] + tr[u << 1 | 1];
			ls[u] = std::max(ls[u << 1], tr[u << 1] + ls[u << 1 | 1]);
			rs[u] = std::max(rs[u << 1 | 1], tr[u << 1 | 1] + rs[u << 1]);
			sum[u] = std::max(std::max(sum[u << 1], sum[u << 1 | 1]), rs[u << 1] + ls[u << 1 | 1]);
		}
		void build(int u, int l, int r, std::vector <T> &a){
			left[u] = l, right[u] = r;
			if(l == r){
				tr[u] = a[l];
				ls[u] = a[l];
				rs[u] = a[l];
				sum[u] = a[l];
				return;
			}
			int mid = (l + r) >> 1;
			build(u << 1, l, mid, a);
			build(u << 1 | 1, mid + 1, r, a);
			push_up(u);
		}
		void _modify(int u, int idx, T val){
			if(left[u] == right[u]){
				tr[u] += val;
				ls[u] += val;
				rs[u] += val;
				sum[u] += val;
				return;
			}
			if(right[u << 1] >= idx) _modify(u << 1, idx, val);
			else _modify(u << 1 | 1, idx, val);
			push_up(u);
		}

		public:

		Segtree(){}
		Segtree(int n, std::vector <T> a){
			tr.resize(n * 4 + 5, -0x3f3f3f3f3f3f3f3fll);
			ls.resize(n * 4 + 5, -0x3f3f3f3f3f3f3f3fll);
			rs.resize(n * 4 + 5, -0x3f3f3f3f3f3f3f3fll);
			sum.resize(n * 4 + 5, -0x3f3f3f3f3f3f3f3fll);
			left.resize(n * 4 + 5);
			right.resize(n * 4 + 5);
			build(1, 1, n, a);
		}
		void modify(int idx, T val){
			_modify(1, idx, val);
		}
		T query(){
			return sum[1];
		}
	};

	void solve(){
		int n, m;
		std::cin >> n >> m;
		std::vector <ll> a(n + 5, 0), b(n + 5, 0);
		for(int i = 1; i <= n; i++) std::cin >> a[i];
		for(int i = 1; i <= n; i++) std::cin >> b[i];
		Segtree <ll> tr(n, a);
		if(m % 2 == 0){
			std::cout << tr.query() << '\n';
			return;
		}
		ll ans = tr.query();
		for(int i = 1; i <= n; i++){
			tr.modify(i, b[i]);
			ans = std::max(ans, tr.query());
			tr.modify(i, -b[i]);
		}
		std::cout << ans << '\n';
	}
}

时间复杂度：$O(\sum n\log n)$。