题目大意：

交互题，你可以询问一个区间的最大子段和，要求在 $2n$ 的询问次数内给出一个和原数组的最大子段和处处相等的数组。

我的做法

首先第一步是花 $n$ 步的次数，问出所有点的正负，这样我们能知道所有的正值，和所有的非负值的位置。

现在要在 $n$ 的次数问出所有非负值的位置。

先把所有连通的正值放在一起，而连通的负值可以等价的认为只有一个，所以原问题可以转化为：+-+-…+，问所有负值的数值。

考虑这么一个询问：+-+ ，假如最终得到的结果等于左右两个 $+$ 值的其中一个，说明 $-$ 起码小于等于两个 $+$ 中最小值的负值。

又可以发现：如果 -+- 且 -+ 和 +- 的和都是 $\le 0$ 的，那么最大子段和一定要么同时包含 -+- ，要么不包含，因此可以将 -+- 合并起来。

因此做法就出来了：每次找到最小的 + ，然后询问其和临近 + 的最大子段和，如果有更大的最大子段和，将这个 + 和临近的 + 合并（此时能够确定中间的 - 值），否则和临近的 - 合并，这样至多两次少一个 + 。

当只剩下一个 + 时，得到的数组就是一个合法的答案，显然，询问次数不超过 $2n-1$ 次。

时间复杂度：$O(n^2)$ 。

可以优化到 $O(n\log{n})$ ，同时这也是这个做法的下界，因为这个做法要找最小值，可以构造：$a_1,-inf,a_2,…,a_m$ ，这样该做法等价于排序 $a_1,…,a_m$ ，因此这个做法的时间复杂度下界就是 $O(n\log{n})$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL inf = 1e15;
const int N = 2e3 + 5;
int n;
int cnt = 0;
LL query(int l, int r){
    cnt++;
    assert(cnt <= n + n);
    cout << "? " << l << ' ' << r << '\n';
    fflush(stdout);
    static LL c;
    cin >> c;
    return c;
}
LL ans[N];
bool v[N];
LL querysum(int l, int r){
    LL now = 0;
    for(int i = l; i <= r; i++) now += ans[i];
    return now;
}
int findpos(int l, int r){
    for(int i = l; i <= r; i++){
        if(!v[i]) return i;
    }
    assert(false);
    return 0;
}
void add(int l, int r, LL c, int type){
    
    LL x = querysum(l, r);
    x = c - x;
    if(!type) x = min(0ll, x);
    int pos = findpos(l, r);
    ans[pos] += x;
    if(type){
        for(int i = l; i <= r; i++) v[i] = 1;
    }
}
struct node{
    int l, r;
    LL c;
};
int main(){
    int T;
    cin >> T;
    while(T--){
        cnt = 0;

        cin >> n;
        for(int i = 1; i <= n; i++) v[i] = 0, ans[i] = 0ll;
        vector<node> a;
        for(int i = 1; i <= n; i++) a.push_back({i, i - 1, 0ll});
        a.push_back({n + 1, n, 0ll});
        while(a.size() > 1){
            int minpos = 0;
            LL c = a[0].c;
            for(int i = 1; i < a.size(); i++){
                if(a[i].c < c){
                    c = a[i].c;
                    minpos = i;
                }
            }
            auto [l, r, tmp] = a[minpos];
            if(minpos){
                auto& [ll, rr, cc] = a[minpos - 1];
                LL val = query(ll, r);
                if(val <= cc) add(rr + 1, l - 1, -c, 0);
                else{
                    rr = r;
                    add(ll, rr, val, 1);
                    cc = val;
                    a.erase(a.begin() + minpos);
                    continue;
                }
            }
            if(minpos + 1 < a.size()){
                auto& [ll, rr, cc] = a[minpos + 1];
                LL val = query(l, rr);
                if(val <= cc) add(r + 1, ll - 1, -c, 0);
                else{
                    ll = l;
                    add(ll, rr, val, 1);
                    cc = val;
                    a.erase(a.begin() + minpos);
                    continue;
                }
            }
            a.erase(a.begin() + minpos);
        }
        cout << "!";
        for(int i = 1; i <= n; i++) cout << ' ' << ans[i] ;
        cout << '\n';
    }
    return 0;
}

这个做法的灵感是这样子的：

对于任意一个最大子段和，可以发现，一定存在一个前缀和一个后缀仍然是最大子段和。

也就是说，我们可以这么想象这么一个过程，就好像是一开始所有的 + 值都想要合并出最大的子段和，然后不断吞并中间的 - 值和周围的 + 值合并的过程，而上面就是一个比较良好的合并过程。

正确性分析：

可以发现，上面的过程都是选择相邻的三个数字，合并，或者是一开始相邻两个正数合并或者非负数合并。

因此只需要证明，一个合法的合并后的数组，在合并前也是合法的。

这个证明也不难，只需要小小讨论一下就行了，在此不再赘述。

更加正确的分析

在看了题解后感受颇深，感觉自己之前的证明可能伪了，但后面看了下，确实可以这么证明，就没有删除原来的证明。

最后决定将这更加详细的证明新开一个板块，保留以前写的东西，同时这个板块我认为是更加重要的，新开一个板块来讲我认为很合适。

定义一个子段为可能最大子段和，当且仅当其大于其任何真子段和（不是自己的子段）。

充要条件：这个子段的任何前缀和后缀都 $>0$ 。

性质 1 ：这个子段的任意一个前缀的最大子段和是其的前缀，这个子段的任意一个后缀的最大子段和是其后缀。

性质 2 ：对于可能最大子段和 $[l_1,r_1],[l_2,r_2]$ ，如果 $l_1\le l_2,r_1\le r_2,l_2\ge r_1$ ，那么 $[l_2,r_1]$ 也是可能最大子段和。

性质 3 ：如果知道了所有的最大子段和，显然能知道哪些段是可能的最大子段和。

性质 4 ：如果 $[l1,r1],[l2,r2]$ 是可能最大子段和，且满足：$l1\le l2 - 1\le r1\le r2$ ，那么 $[l1,r2]$ 也是可能最大子段和。

现在，回顾一下我之前的灵感中的最大子段和合并的过程，可以发现，里面提到的最大子段和就是可能最大子段和，当时提到了一个词：合并，但是这个合并到达是什么意思呢？

总不能就是感觉上的抽象的合并吧？就两个可能最大子段和合并成一个的过程吧？

接下来我将详细的、具体的描述这个过程：

假设我们知道了 $[l,r]$ 的和，且也有一了一个 $[l,r]$ 的数组满足 $[l,r]$ 内部要求的 $mss$ ，那么我们能不能将 $[l,r]$ 看成一个数字去研究接下来的问题呢？

可以发现，我的做法中，一开始合并两个正数，以及后面的 $+-+$ 的合并都属于这个类型。

这个问题可以这么说：假设我将 $[l,r]$ 看成一个数字，忽略与 $[l,r]$ 有交集但不包含的 $mss$ ，得到了一个合法的数组后，能够在将 $[l,r]$ 展开后，仍然满足所有的 $mss$ 。

又可以这么说：将 $[l,r]$ 看成一个数字，在忽略掉与 $[l,r]$ 有交集但不包含的 $mss$ ，能否唯一决定与 $[l,r]$ 有交集但不包含的 $mss$ 。

而事实上，如果 $[l,r]$ 的数组的得到过程只依赖于 $[l,r]$ 内部的 $mss$ 数组，那么这个问题又可以这么说：能否利用与 $[l,r]$ 有交集但不包含的 $mss$ 以外的 $mss$ 唯一决定这一部分的 $mss$ 。

现在给一个定理：如果 $[l,r]$ 是一个可能的最大子段和，那么上述问题成立。

证明：

考虑计算 $[l’,r’]$ 的 $mss$ ，不妨认为：$l’<l,l\le l’\le r$ ，那么 $mss(l’,r’)=max(mss(l’,l-1),mss(l,r’),K)$ 。

其中 $K$ 表示什么，设最小的 $i$ 满足：$l’\le i < l:[i,r]$ 是可能最大子段和。（没有则 $K=-\infty$）

则 $K=mss(i,r)-mss(l,r)+mss(l,r’)$ ，这一段成立的原因是，如果 $x,y$ 是可能最大子段和，则 $[x,r]$ 也是。

然后显然最大贡献需要挑其中最大的，就是 $[i,r]$ ，然后考虑其的贡献一定是 $sum(i,l-1)$ 加上最大的前缀在 $[l,r’]$ ，显然这个就为 $mss(l,r’)$ 。

因此是可以计算的，证毕。

因此，$[l,r]$ 实际上可以看成一个数字，内部和外部分隔开来，忽略到多余的 $mss$ 不会影响整个 $mss$ 的合法性，我认为这就是上面说的那个合并过程的具体表述。

不过事实上从最终做法也可以看出，决定所有 $mss$ 所需要的 $mss$ 只需要 $O(n)$ 就行了。

区间包含单调性：$mss(l_1,r_1)\ge mss(l_2,r_2),l_1\le l_2,r_1\ge r_2$ 。

四边形不等式：$mss(l_1,r_1)+mss(l_2,r_2)\le mss(l_1,r_2)+mss(l_2,r_1)$ ，$l1\le l_2\le r_2\le r_1$ 。

证明

只需要证明 $mss(l-1,r+1)-mss(l-1,r)\le mss(l,r+1)-mss(l,r)$ 。

考虑 $p(l,r)$ 表示 $\max\limits_{l\le i\le r} sum(i,r)$ ，显然如果 $mss(l,r+1)>mss(l,r)$ ，那么 $mss(l,r+1)=a_{i}+p(l,r)$ ，因此只需要证明：$mss(l-1,r)-p(l-1,r)\ge mss(l,r)-p(l,r)$ 。

设 $[l_1,r_1]$ 为 $mss(l-1,r)$ 的区间， $[l_2,r]$ 为 $p(l-1,r)$ 的区间，$[l_3,r_3]$ 为 $mss(l,r)$ 的区间，$[l_4,r]$ 为 $p(l,r)$ 的区间。

那么显然可以有 $l_1\le l_2, l_3 \le l_4$ ，若有 $l_2\ge l-1$ ，则 $l_2=l_4$ ，则显然成立，所以不妨认为：$l_1 = l_2 = l - 1$ ，此时显然可以有 $r_1<l_3$。

故 $mss(l_1,r)-p(l-1,r)-mss(l,r)+p(l,r)=-sum(r_1+1,l_4-1)\ge 0$ 。

证毕。

最大子段和还有很多其他性质，等待补充。

遇到一道疑似有关这个概念的题目，但是苦于没有提交链接，故先放在这里吃灰：

meta camp 2022 T5 最大子段和，出现链接：https://www.zhihu.com/question/546431239 。

官方题解

看懂了做法，迷迷糊糊的明白了为什么是对的，但是感觉我不太能很好的说明其为什么是对的。（题解看的也不太懂）

我从我的角度去阐述这个做法：

还是跟之前做法一样，先全问一遍，然后合并，变成 $+-+-+-…$ 的形式。

考虑用增量法，即考虑维护一个正确的前缀。

注意到在假如在新添加字符后，我们肯定想知道哪个后缀成为了可能最大子段和。

假设前面的数字是 $a_1,…,a_{t-1}$ ，一个简单粗暴的想法是找到 $l$ ，满足：$mss(l,t) > max(mss(l,t-1), mss(l+1,t))$ ，这样就可以将 $[t,l]$ 合并为一个数字，但是这样子要问 $O(n^2)$ 次，考虑优化。

注意到如果 $[l,t]$ 如果是可能最大子段和的话，那么 $mss(k,t) > mss(k,t-1)(l\le k\le t-1)$ ，因此如果这一条不满足的话，就可以直接退出，但是这样子并没有优化最坏时间复杂度，悲。

接着思考，考虑如果 $mss(k,t)>mss(k,t-1)$ 且 $mss(k,t)=mss(k+1,t)$ ，那究竟意味着什么？如果 $a_{k}\le 0$ 那么显然满足，但是如果 $a_{k}>0$ 时呢？考虑一种简单情况，也就是：$+-+$ ，这个时候也就说明中间 $-$ 的绝对值大于左边的 $+$ 。

注意到，我们有可能永远不可能知道中间 $-$ 的值，因为我们要知道这个 $-$ 的充要条件是有一个可能最大子段和包含它且其余值我们都知道，但是前缀已经写成了 $+-+-+-$ 的形式，且 $-$ 值都不知道，因此这个充要条件感觉上不太可能成立。

这启示我们能不能贪心的给这个位置赋值，也就是给中间的 $-$ 赋值上左边正值的负数（能赋的值中的最大值，显然右边的 $+$ 大于左边的 $+$ 值）。

这样就能利用上每一次询问，根据这个想法，就可以得到题解的做法。

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

具体过程感兴趣的话看代码吧，感觉不太能讲明白。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e3 + 5;
std::mt19937 rnd(time(0));
int n, cnt;
LL mss(int l, int r){
    cout << "? " << l << " " << r << "\n";
    fflush(stdout);
    LL res;
    cin >> res;
    cnt++;
    assert(cnt <= n + n && l >= 1 && r <= n);
    return res;
}

struct node{
    int l, r, p;
    LL preval;
}sta[N]; int top;
LL a[N];

struct Seg{
    int l, mid, r;
    LL sum = 0ll;
}s[N]; int m;
int main(){
    int T;
    cin >> T;
    while(T--){
    // while(1){
        top = cnt = 0;
        cin >> n;
        // generater();
        for(int i = 1; i <= n; i++) a[i] = mss(i, i);
        // for(int i = 1; i <= n; i++) a[i] = mss(i, i, b);
        m = 0;
        for(int l = 1; l <= n; l++){
            int mid = l - 1;
            LL sum = 0ll;
            while(mid < n && a[mid + 1] > 0) mid++, sum += a[mid];
            int r = mid;
            while(r < n && a[r + 1] == 0) r++;
            s[++m] = {l, mid, r, sum};
            l = r;
        }
        for(int i = 1; i <= m; i++){
            if(s[i].mid == 0) continue;
            LL val = s[i].sum;
            int p = s[i].l;
            LL preval = s[i].sum;
            while(top){
                val = mss(sta[top].p, s[i].mid);
                // val = mss(sta[top].p, s[i].mid, b);
                if(val > sta[top].preval){
                    a[sta[top].r] = val - sta[top].preval - preval;
                    if(val > preval) p = sta[top].p, preval = val;
                    top--;
                }
                else break;
            }
            int l = sta[top].l + 1;
            sta[++top] = {l, s[i].r, p, preval};
        }
        for(int i = 1; i <= top; i++){
            if(!a[sta[i].r]) a[sta[i].r] = -1e15;
        }
        cout << "!";
        for(int i = 1; i <= n; i++) cout << " " << a[i];
        cout << "\n";
    }
    return 0;
}

正确性可以感受一下，在每个 $-$ 值处放上能放的最大值，就可以在出现可能最大子段和的时候，使得放下的最后那个决定性的 $-$ 值是合法的，反之，如果在之前的 $-$ 值放下 $-inf$，那么在出现最大子段和时甚至可能在 $-$ 的位置放下正数，这显然是不合法的，这类似一种贪心思想。

再放一个东西：

对于一个 $+-+-+-…+$ 的序列 $a_1,..,a_n$ ，满足 $mss(1,n)=sum(1,n),mss(l,r)=\max\limits_{l\le i\le r}(0,a_{i})([l,r]\ne[1,n])$ ，则一定有以下结论：

$a_1,a_n$ 是 $a$ 序列中的最大值和次大值。

$mss(1,n)\le a_1+a_n-\max\limits_{2\le i \le n - 1}a_i$ 。

证明

反证法：$\exists i: 2\le i \le n - 1:a_{i}>a_1$（存在多个就找最小的 $i$ ），则 $mss(1,n)+mss(i,i)\le mss(1,i)+mss(i,n)$ ，推出：$mss(1,n)=mss(i,n)$ ，与定义矛盾，第一条证毕。

$mss(1,n)+mss(i,i)\le mss(1,i)+mss(i,n)=a_{1}+a_{n}$ ，整理一下可以得到第二条，证毕。

这个性质可以用于证明最后放下的那个负数的合法性。

但我感觉题解肯定不是这个意思，至少正确性应该不是这么丑陋的证明，肯定有更加高深的东西我没看懂，至于是啥，读者只能自行体会或者去看题解了，博主水平有限了。