少年游 题解
船酱魔王
·
·
题解
题意回顾
- 交互器有一个长度为 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 $ 次，还是不行。怎么办？
* 注意到卡到上界的条件是翻到最后一个数才最大子段和变大，那么显然从这个数往左往右走时肯定不用往右走，那么不用还原最右面的数，故两步无法同时把次数卡到上界。
* 故我们解决了这一问题。
## 参考实现
```cpp
#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;
}
```