少年游 题解

题意回顾

• 交互器有一个长度为 $n$ 的整数序列，初始时已经确定；
• 每次可以选择将一段区间乘 $-1$，交互器输出当前序列的全局最大可以为空的子段和；
• 请用一些操作得到序列每个位置的初始值。

分析

• 约定：反转操作意为区间符号反转（乘 $-1$），返回值全称为「全局最大可以为空的子段和的返回值」。
• 注意到对于一个位置连续反转两次相当于不变，因此反转操作具有偶数次抵消性。
• 考虑本题的最简情况：初始时所有数都是正数或负数：
  • 当初始时全为非正时，当且仅当反转两次全局后返回 $0$，那么第一次反转全局的返回值就是整个序列的绝对值和。考虑反转从 $a_2$ 开始的后缀，也就是相当于在所有数为非负（第一次全局反转后）的情况基础上，反转了 $a_1$，显然此时最大子段和为 $a_2$ 开始的后缀的绝对值和，两次返回值的差就是 $a_1$ 的值，之后从 $a_2$ 开始依次单独反转，相邻两次的返回值差就是每个数的绝对值。
  • 当初始时全为非负时（反转一次全局后返回 $0$），直接用类似的方法即可。此时发现一个性质：若我们将序列所有值转为非负，那么此时的返回值被记录后，可以用来 $n-1$ 次操作求出每个位置的值。
• 记录初始状态（两次反转后）返回值 $Q_0$，此时我们已经询问了 $2$ 次。此时序列中存在至少一个正数和一个负数。
• 从左到右依次尝试反转每个数（后复原），若在反转一个数 $a_p$ 后，返回值大于 $Q_0$，说明：对于这个序列的最大子段和的任意组成区间，均包含 $a_p$ 这个元素。
  • 证明：若存在一个区间，其和为序列的最大子段和，不包含 $a_p$ 元素，那么它所涉及到的元素均未被修改，为初始状态，则在初始状态下选取这个区间仍能得到大于 $Q_0$ 的子段和，这是违背前提条件（$Q_0$ 为初始状态下的最大子段和）的。
  • 考虑优化找到 $a_p$ 的过程，可以在反转这个位置时顺便反转（即为复原）上一个位置。而注意找到的 $a_p$ 不需要复原。
  • 证明一定存在这样的 $a_p$：该序列中存在正数，因此一定存在一个非空区间和为序列的最大子段和。若把这个区间考虑从左右拓展，然后把遇到的第一个负数变为正数，得到的最大子段和一定大于 $Q_0$，否则说明这个序列中不存在负数。
  • 这步我们消耗了最多 $n$ 次找到 $a_p$ 的查询次数。
• 考虑从 $a_p$ 开始往左走，按照在 $a_{p-1}$ 开始从右到左的顺序尝试反转每个元素：
  • 如果反转后返回值变小 / 变大，足以说明这个数的正负。注意当反转后变为负数需要还原（用类似于前文的方法优化次数）。
  • 如果反转后返回值不变，而此时它一定处于或与最大子段和区间相邻，那么考虑：如果这个数非 $0$，那么在为正数时计入这个值一定会让返回值更大；如果两种情况（正负）都计入最大子段和区间，由最大子段和的局部最优性，它左面的区间长度一定一样，那么返回值也会改变。因此这个数必然为 $0$。
  • 从 $a_{p+1}$ 开始向右的操作反之亦然。
  • 这步我们消耗了最多 $n-1+1+1=n+1$（$n-1$ 个元素要被反转，两边的元素可能要额外一次还原）次操作。
• 此时，序列中所有元素非负，用 $n-1$ 次操作处理完即可。
• 操作次数上限为 $2+n+n+1+n-1=3n+2$ 次，还是不行。怎么办？
  • 注意到卡到上界的条件是翻到最后一个数才最大子段和变大，那么显然从这个数往左往右走时肯定不用往右走，那么不用还原最右面的数，故两步无法同时把次数卡到上界。
  • 故我们解决了这一问题。

参考实现

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1005;
int T;
int n, qmax;
int sgn[N];
int a[N];
int ask(int l, int r, int chan = 0) {
	cout << "? " << l << " " << r << endl;
	if(!chan) {
		for(int i = l; i <= r; i++) sgn[i] = -sgn[i];
	}
	cin >> l;
	return l;
}
void easy(int x) {
	for(int i = 1; i <= n - 1; i++) {
		int tu = ask(i, i, 1);
		a[i] = x - tu;
		x = tu;
	}
	a[n] = x;
	cout << "! ";
	for(int i = 1; i <= n; i++) {
		cout << a[i] * sgn[i];
		if(i < n) cout << " ";
		else cout << endl;
	}
}
int main() {
	cin >> T;
	for(int ti = 1; ti <= T; ti++) {
		cin >> n >> qmax;
		for(int i = 1; i <= n; i++) sgn[i] = 1;
		int t1 = ask(1, n);
		int t2 = ask(1, n);
		if(t1 == 0 || t2 == 0) {
			if(t2 == 0) ask(1, n);
			easy(max(t1, t2));
			continue;
		}
		int qt = t2;
		int p = 0;
		for(int i = 1; i <= n; i++) {
			int tp = ask(max(i - 1, 1), i);
			if(tp > qt) {
				p = i;
				qt = tp;
				break;
			}
		}
		if(!p) {
			cout << "! I AK IOI" << endl;
			continue;
		}
		int oq = 0;
		for(int i = p - 1; i >= 1; i--) {
			int tp = ask(i, i + oq);
			if(tp >= qt) qt = tp, oq = 0;
			else oq = 1;
		}
		if(oq) qt = ask(1, 1);
		oq = 0;
		for(int i = p + 1; i <= n; i++) {
			int tp = ask(i - oq, i);
			if(tp >= qt) qt = tp, oq = 0;
			else oq = 1;
		}
		if(oq) qt = ask(n, n);
		easy(qt);
	}
	return 0;
}