好厉害！
首先使用贪心策略，从左往右扫，能填 \(0\) 就填 \(0\)，问题变为判定性问题。
首先我们先观察性质。
- 性质：\(P\) 中的前缀最大值一定有 \(1\) 的贡献，其他元素的贡献可以为 \(0\)，一定条件下可以为 \(1\)。
然后就不会了，个人只会 \(O(n^2)\) 的 DP。
考虑猜结论。
- 结论：把 \(P_{i+1 ... n}\) 分配给两个序列，存在一种最优方案，满足其中一个序列中的贡献都是 \(P\) 的前缀最大值。
证明：假设两个序列有两个非前缀最大值的贡献 \(x,y\)，那么交换 \(x,y\) 的分配，两个贡献都会去掉。
所以我们只需要分讨一下这个序列是 \(A\) 还是 \(B\)，假设为 \(A\)。
设 \(c_A,c_B\) 分别为 \(A,B\) 中 \(P_{1...i}\) 的贡献，那么 \(P_{i+1...n}\) 的分配需要满足 \(A\) 的贡献减去 \(B\) 的贡献等于 \(c_B-c_A\)。
设 \(D = c_A - c_B\)，\(S\) 为 \(P_{i+1...n}\) 在原排列的前缀最大值个数，\(T\) 为分配给 \(B\) 的前缀最大值，\(E\) 为剩余可贡献的数量。
那么 \(A\) 的剩余贡献为 \(S-T\)，\(B\) 的剩余贡献为 \(T+[0,E]\)，关系式为 \((S-T)-(T+E) = D \Leftrightarrow 2T+[0,E] = S-D\)。
我们解读一下这个式子，相当于在 \(P_{i+1...n}\) 中选择一个上升子序列，前缀最大值的贡献为 \(2\)，其他数贡献为 \(1\)，满足总贡献为 \(S-D\)，问是否存在这样的方案。
- trick：注意到如果我们确定了一个方案，贡献为 \(v\)，那么 \(v-2\) 也是可行的。
所以我们分奇偶两种，dp 算最大贡献。
使用线段树，时间复杂度 \(O(n\log n)\)。
点击查看代码
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define fi first
#define se second
#define pir pair <ll, ll>
#define mkp make_pair
#define pb push_back
using namespace std;
const ll maxn = 2e5 + 10, inf = 1e17;
ll n, a[maxn], b[maxn], f[maxn][2], sum[maxn];
struct SGT {
ll mx[maxn << 2];
void modify(ll p, ll l, ll r, ll x, ll v) {
if(l == r) {mx[p] = v; return;}
ll mid = l + r >> 1;
if(x <= mid) modify(p << 1, l, mid, x, v);
else modify(p << 1|1, mid + 1, r, x, v);
mx[p] = max(mx[p << 1], mx[p << 1|1]);
}
ll query(ll p, ll l, ll r, ll ql) {
if(ql <= l) return mx[p];
if(r < ql) return -inf;
ll mid = l + r >> 1;
return max(query(p << 1, l, mid, ql), query(p << 1|1, mid + 1, r, ql));
}
} T[2];
ll mx1, mx2, c1, c2, pos[maxn];
bool chk(ll i) {
ll D = c1 - c2, t = (sum[i + 1] + D + 10000000) & 1;
if(sum[i + 1] >= D && T[t].query(1, 1, n + 1, mx1) >= sum[i + 1] - D) return 1;
if(sum[i + 1] >= -D && T[t].query(1, 1, n + 1, mx2) >= sum[i + 1] + D) return 1;
return 0;
}
int main() {
scanf("%lld", &n);
for(ll i = 1, mx = 0; i <= n; i++) {
scanf("%lld", a + i);
pos[a[i]] = i;
if(a[i] > mx) {
b[i] = 1;
mx = a[i];
}
T[0].modify(1, 1, n + 1, i, -inf);
T[1].modify(1, 1, n + 1, i, -inf);
}
T[1].modify(1, 1, n + 1, n + 1, -inf);
for(ll i = n; i; i--) {
sum[i] = sum[i + 1] + b[i];
f[i][0] = T[b[i] ^ 1].query(1, 1, n + 1, a[i]) + 1 + b[i];
f[i][1] = T[b[i]].query(1, 1, n + 1, a[i]) + 1 + b[i];
T[0].modify(1, 1, n + 1, a[i], f[i][0]);
T[1].modify(1, 1, n + 1, a[i], f[i][1]);
}
if(!chk(0)) {puts("-1"); return 0;}
for(ll i = 1; i <= n; i++) {
ll tmpmx = mx1, tmpc = c1;
mx1 = max(mx1, a[i]), c1 += (mx1 == a[i]);
T[0].modify(1, 1, n + 1, a[i], -inf);
T[1].modify(1, 1, n + 1, a[i], -inf);
if(!chk(i)) {
mx1 = tmpmx, c1 = tmpc;
mx2 = max(mx2, a[i]), c2 += (mx2 == a[i]);
putchar('1');
} else putchar('0');
}
return 0;
}