CF Round 1100 Div12 C2 - We Be Flipping (Hard Version)

题目大意

给一个长度为 $n$ 的非零整数数组 $a$ 。一次操作可以选择一个当前为正数的位置 $i$ ，然后把前缀 $1..i$ 的所有数全部取相反数。

Hard Version 要求输出不超过 $n$ 次操作，使最终数组的元素和最大。

数据范围：

• $1 \le t \le 10^4$

• $2 \le n \le 2 \cdot 10^5$

• $-10^9 \le a_i \le 10^9, a_i \ne 0$

• 所有测试的 $n$ 之和不超过 $2 \cdot 10^5$

样例里第三组 $[1,-3,2,-1,10]$ 可以操作 $1,3$ ，变成 $[1,3,-2,-1,10]$ ，最终和为 $11$ 。

思路讲解

一句话

先把连续同号段压成块，从左到右消掉能稳定处理的正块；最后那个正块要选一个最小正数 $mnId$ 做收尾，C2 和 C1 的差别其实就在这里：C1 已经会了 $-+ \rightarrow +- \rightarrow --$ ，那 C2 只差最后一瞬间把负号翻回正号。

从 C1 到 C2 的那个小火花

C1 的关键感觉是：遇到相邻的异号结构时，前缀翻转并不是单纯“把前面全部翻掉”，它还会让边界附近的符号发生迁移。

核心观察：如果 C1 已经想明白 $-+ \rightarrow +- \rightarrow --$ ，那么 C2 里“正负号的一刹那”也就出来了。最后我们不只是把前面扫成目标形态，还可以在收尾时让一个负号重新变成正号。

具体落到最后一个正块，取这个块里值最小的位置 $mnId$ 。收尾三步可以看成：

// +-+(mnId)
// --+(mnId)
// ++-(mnId)

也就是说，先借左侧边界把局面推成可控的 $+-+$ ，再让它变成 $--+$ ，最后点到 $mnId$ ，把需要留下来的负号翻回正号。这个 “最后补一刀” 是 Hard Version 相比 Easy Version 最容易漏掉的地方。

为什么要压连续同号块

同号连续的一整段在前缀翻转下总是一起改变符号，真正发生结构变化的是正负块的交界。所以先把数组压成若干块：

• 正块：里面全是正数。

• 负块：里面全是负数。

• 相邻块符号一定相反。

这样操作的对象就从单个数变成了“块边界”。普通正块可以用块尾和前一块边界去处理；最后留下来的正块单独处理，因为它决定最大和时要不要牺牲一个正数。

最后一块怎么选

如果全是负数，没法操作，答案就是 $0$ 次。如果全是正数，和已经最大，也不用操作。

否则我们从最后一个正块往左看。对某个正数 $a_i$ ，它前面已经有一些负数绝对值会被翻成正贡献；如果这些负数的收益足够覆盖牺牲这个正数，就可以把它作为最后收尾的位置。

代码里用 presum 记录前缀负数绝对值之和，判断形如：

if (A[pos] < negative_sum_before_pos) {
    diff = negative_sum_before_pos - A[pos];
}

挑 diff 最大的那个块作为最后一块。直觉上就是：最后牺牲哪个正数最划算，或者说把哪段前缀整理完以后总和最大。

操作怎么输出

对最后一块之前的每个正块：

• 先操作这个正块的块尾。

• 再操作它前一个位置，也就是左侧负块的尾部。

这相当于沿着同号块从左到右做“符号清扫”。

到了最后一块，找块内最小的正数 $mnId$ ：

• 如果 $mnId$ 正好在块首，就直接操作它。

• 否则按刚才那组三步收尾：mnId - 1、block_front - 1、mnId。

这一套操作次数仍然不会超过 $n$ ，因为每个块只贡献常数次操作，而块数不超过元素数。

这题值得记住的点

C2 不是把 C1 推倒重做，而是把 C1 的局部符号变换再多看一眼： $-+ \rightarrow +- \rightarrow --$ 已经说明边界可以被“搬运”，Hard 版只是要求你在最大和目标下，选一个最划算的收尾点。

这个观察特别适合以后复盘：Easy Version 给的是能不能做，Hard Version 要的是在哪里停最赚。

AC 代码

AC 提交链接

源码较长，折叠在下面。

展开完整源码

// teamname: Gospel_rock
/**
 * Problem: C2. We Be Flipping (Hard Version)
 * URL:     https://codeforces.com/contest/2229/problem/C2
 * Limits:  2000 ms / 256 MB
 * Author:  Gospel_rock
 * My blog: https://znzryb.com/
 *
 * Powered by cph-ng (https://github.com/langningchen/cph-ng)
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define fsp(x) fixed << setprecision(x)

using namespace std;

#if 1 && defined(LOCAL)
// clang-format off
// @formatter:off
namespace DBG {
	template<typename T> void debug(T x);
	void debug(bool x);
	void debug(string x);
	template<typename T> void debug(vector<T> v);
	template<typename T, size_t N> void debug(array<T, N> v);
	template<typename T> void debug(set<T> s);
	template<typename T, typename U> void debug(pair<T, U> p);
	template<typename T, typename U> void debug(map<T, U> m);
	template<typename, typename = void> constexpr bool _has_iter_v = false;
	template<typename T> constexpr bool _has_iter_v<T, void_t<decltype(declval<T>().begin()), decltype(declval<T>().end())>> = true;
	template<typename T>
	void debug(T x) { cerr << x; } void debug(bool x) { cerr << (x ? "T" : "F"); } void debug(string x) { cerr << '"' << x << '"'; }
	template<typename T> void debug(vector<T> v) { constexpr bool nested = _has_iter_v<T>; int n = v.size(); cerr << "["; for (int i = 0; i < n; i++) { if constexpr (nested) { if (i) cerr << ","; cerr << "\n  "; } else { if (i) cerr << ", "; } debug(v[i]); } if constexpr (nested) { if (n) cerr << "\n"; } cerr << "]"; }
	template<typename T, size_t N> void debug(array<T, N> v) { constexpr bool nested = _has_iter_v<T>; cerr << "["; for (size_t i = 0; i < N; i++) { if constexpr (nested) { if (i) cerr << ","; cerr << "\n  "; } else { if (i) cerr << ", "; } debug(v[i]); } if constexpr (nested) { if (N) cerr << "\n"; } cerr << "]"; }
	template<typename T> void debug(set<T> s) { cerr << "{"; int f = 0; for (auto x: s) { if (f++) cerr << ", "; debug(x); } cerr << "}"; }
	template<typename T, typename U> void debug(pair<T, U> p) { cerr << "("; debug(p.first); cerr << ", "; debug(p.second); cerr << ")"; }
	template<typename T, typename U> void debug(map<T, U> m) { cerr << "{"; int f = 0; for (auto &[k, v]: m) { if (f++) cerr << ", "; debug(k); cerr << ": "; debug(v); } cerr << "}"; }
	void _dbg() { cerr << endl; }
	template<typename T, typename... A> void _dbg(T x, A... a) { debug(x); if (sizeof...(a)) cerr << ", "; _dbg(a...); }
}
// clang-format on
// @formatter:on
#define dbg(x...) cerr << "[" << setw(7) << #x << "] = ", DBG::_dbg(x)
#define cend cerr << "\n---------------------------------------------------\n"
#define cEnd cerr << "\n***************************************************\n"
#define myAssert(...) assert((__VA_ARGS__))
#else
#define dbg(x...) 11
#define cend 45
#define cEnd 14
#define myAssert(x) 14
#endif

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353;  // (ll)1e9+7;
static constexpr double eps = 1e-8;
// 不用 M_PI: 后者是 POSIX 扩展, glibc <cmath> 严格模式会 undef
const long double PI = acosl(-1.0);

ll lT, testcase;

/*
 *
 */

void Solve() {
	ll N;
	cin >> N;
	vector<ll> A(N);
	for (int i = 0; i < N; ++i) {
		cin >> A[i];
	}
	do {
		bool ok = false;
		for (int i = 0; i < N; ++i) {
			if (A[i] > 0) {
				ok = true;
			}
		}
		if (!ok) {
			cout << 0 << "\n\n";
			return;
		}
	} while (false);
	vector<vector<ll>> block;
	ll lastBt0Id = 0;
	for (int i = 0; i < N; ++i) {
		if (block.empty()) {
			block.push_back({i});
			if (A[i] > 0) {
				lastBt0Id = SZ(block) - 1;
			}
			continue;
		}
		if ((A[block.back().back()] ^ A[i]) >= 0) {
			block.back().push_back(i);
		} else {
			block.push_back({i});
			if (A[i] > 0) {
				lastBt0Id = SZ(block) - 1;
			}
		}
	}
	if (SZ(block) == 1) {
		cout << 0 << "\n\n";
		return;
	}
	vector<ll> presum;
	do {
		presum.resize(N);
		if (A[0] < 0) {
			presum[0] = abs(A[0]);
		}
		for (int i = 1; i < N; ++i) {
			if (A[i] < 0) {
				presum[i] = presum[i - 1] + abs(A[i]);
			} else {
				presum[i] = presum[i - 1];
			}
		}
		ll rec = 0;
		auto get = [&](ll l) -> ll {
			if (l - 1 < 0) {
				return 0;
			}
			return presum[l - 1];
		};
		bool ok = false;
		ll best = -1;
		for (int i = lastBt0Id; i >= 0; i -= 2) {
			dbg(A[block[i].back()]);
			for (int j = 0; j < SZ(block[i]); ++j) {
				if (A[block[i][j]] >= get(block[i][j])) {
					continue;
				} else {
					ll diff = get(block[i][j]) - A[block[i][j]];
					dbg(diff);
					if (diff > best) {
						best = diff;
						rec = i;
						ok = true;
					}
				}
			}
		}
		dbg(best);
		dbg(rec);
		if (!ok) {
			cout << 0 << "\n\n";
			return;
		}
		// dbg(rec);
		lastBt0Id = rec;
	} while (false);
	dbg(lastBt0Id);
	vector<ll> oper;
	for (int i = 0; i <= lastBt0Id; ++i) {
		auto& p = block[i];
		if (A[p.front()] < 0) {
			continue;
		}
		if (i == lastBt0Id) {
			// if (SZ(p) == 1) {
			// 	oper.push_back(p.front());
			// 	continue;
			// }
			ll mnId = block[i].front();
			for (int j = 0; j < SZ(block[i]); ++j) {
				if (A[mnId] > A[block[i][j]]) {
					mnId = block[i][j];
				}
			}
			if (mnId - 1 == p.front() - 1) {
				oper.push_back(mnId);
				continue;
			}
			// +-+(mnId)
			if (mnId - 1 >= 0) {
				oper.push_back(mnId - 1);
			}
			// --+(mnId)
			if (p.front() - 1 >= 0) {
				oper.push_back(p.front() - 1);
			}
			// ++-(mnId)
			oper.push_back(mnId);
		} else {
			oper.push_back(p.back());
			if (p.front() - 1 >= 0) {
				oper.push_back(p.front() - 1);
			}
		}
	}
	cout << SZ(oper) << "\n";
	for (auto& p : oper) {
		cout << p + 1 << " ";
	}
	cout << "\n";
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#ifdef LOCAL
	cout.setf(ios::unitbuf);  // 无缓冲流，方便我们调试
#endif

	cin >> lT;
	for (testcase = 1; testcase <= lT; ++testcase)
		Solve();
	return 0;
}

/*
AC
https://codeforces.com/contest/2229/submission/376325991



ll mnId=block[i].front();
			for(int j=0;j<SZ(block[i]);++j){
				if(A[mnId]>A[block[i][j]]){
					mnId=block[i][j];
				}
			}
			oper.push_back(mnId);
			if(mnId-1>=0 && mnId!=p.front()){
				oper.push_back(mnId - 1);
			}
			if (p.front() - 1 >= 0) {
				oper.push_back(p.front() - 1);
			}
			oper.push_back(p.back());
*/

心路历程（WA，TLE，MLE……）

• 这题最关键的不是代码长，而是把 C1 的局部变换真正吃透。只要意识到 $-+ \rightarrow +- \rightarrow --$ 还能在最后收尾时把负号翻回正号，Hard 的“最大和”就从玄学变成了选点问题。

• 容易漏的点是最后一块不能随便选块尾，要选块内最小的正数 $mnId$ ，否则可能多牺牲了一个本来可以保住的正贡献。

• 另一个坑是全负和全正这两个边界。全负时没有合法操作，全正时已经最大；这两个都应直接输出 $0$ 。

附件

暂无附件。