CF1990B Array Craft 题解

题意回顾

给定三个整数 $n, x, y$（$1 \le y < x \le n$），构造一个长度为 $n$、仅由 $1$ 和 $-1$ 组成的数组 $a$，使得：

• 最大前缀位置等于 $x$：即 $x$ 是满足 $\sum_{j=1}^i a_j = \max\limits_{k=1}^n \sum_{j=1}^k a_j$ 的最小下标 $i$；
• 最大后缀位置等于 $y$：即 $y$ 是满足 $\sum_{j=i}^n a_j = \max\limits_{k=1}^n \sum_{j=k}^n a_j$ 的最大下标 $i$。

构造方法

将数组分为三段：

1. 左段 $[1, y-1]$：从右往左（下标递减）交替填入 $-1, 1, -1, 1, \dots$，即下标与 $y-1$ 同奇偶的位置填 $1$，否则填 $-1$。
2. 中段 $[y, x]$：全部填 $1$。
3. 右段 $[x+1, n]$：从左往右交替填入 $-1, 1, -1, 1, \dots$，即从 $x+1$ 开始奇数位填 $-1$，偶数位填 $1$。

代码中的实现：

for (int i = y - 1; i; --i)          // 左段，从右往左
    cout << (i & 1 ? "-1 " : "1 ");
for (int i = y; i <= x; ++i)         // 中段
    cout << "1 ";
for (int i = 1, tmp = n - x; i <= tmp; ++i) // 右段
    cout << (i & 1 ? "-1 " : "1 ");

正确性证明

1. 最大前缀位置 $= x$

观察前缀和的变化：

• 左段 $[1, y-1]$：交替填 $-1, 1$，使得前缀和在 $1$ 和 $0$ 之间反复震荡（具体取决于 $y-1$ 的奇偶性），但始终保持 $\le 1$。到位置 $y-1$ 时前缀和 $\le 1$。
• 进入中段 $[y, x]$（全 $1$）后，前缀和从位置 $y-1$ 的值开始，每个位置 $+1$，单调递增。
• 位置 $x$ 处前缀和达到全局最大值。因为之后进入右段 $[x+1, n]$，交替填入 $-1, 1$，使得前缀和每隔一步减少 $1$ 或不变，不会再超过 $x$ 处的值。

此外，若存在某个 $i < x$ 使得前缀和也等于最大值，必须保证 $x$ 是最小的这样的下标。由于中段全 $1$，前缀和在 $[y, x]$ 严格单调递增，故 $x$ 之前的任何位置前缀和都严格小于 $x$ 处。左段的前缀和始终小于等于 $1$，不可能达到 $x$ 处的值（中段至少有一个 $1$，所以 $x$ 处前缀和 $\ge$ 前面最大值 $+1$）。因此 $x$ 确实是唯一且最小的最大值位置。

2. 最大后缀位置 $= y$

观察后缀和的变化：

• 右段 $[x+1, n]$：交替填 $-1, 1$，后缀和（从右往左看）在 $0$ 和 $1$ 之间震荡，始终 $\le 1$。
• 中段 $[y, x]$（全 $1$）：从右往左看，后缀和在 $[y, x]$ 区间内严格单调递增（因为每个位置都是 $1$）。
• 左段 $[1, y-1]$：交替填 $-1, 1$，后缀和经历 $-1, 1$ 交替，始终 $\le 1$。

整个后缀和的最大值出现在 $y$ 处。因为从 $n$ 往左扫，后缀和先是 $\le 1$，经过中段 $[y, x]$ 时逐渐增大，在 $y$ 处达到最大；再往左，后缀和因交替填 $-1,1$ 而下降，不会再超过 $y$ 处的值。同时 $y$ 是最大的使得后缀和等于最大值的下标，因为中段 $[y, x]$ 内后缀和严格递减（从左往右看是递增，从右往左是递减），所以 $y$ 之后的位置后缀和都严格小于 $y$ 处。

复杂度

每组数据只需 $O(n)$ 时间输出。所有数据 $n$ 总和 $\le 10^5$，完全可以通过。

参考代码

#include <bits/stdc++.h>
#define I return
#define AK 0
#define IOI ;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int t, n, x, y;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t--) {
        cin >> n >> x >> y;
        for (int i = y - 1; i; --i)
            cout << (i & 1 ? "-1 " : "1 ");
        for (int i = y; i <= x; ++i)
            cout << "1 ";
        for (int i = 1, tmp = n - x; i <= tmp; ++i)
            cout << (i & 1 ? "-1 " : "1 ");
        cout << '\n';
    }
    I AK IOI
}