题解：CF1322E Median Mountain Range
nansn
·
·
题解
首先想到转化成 $01$ 序列的问题，只有 $010,101$ 会变成 $101,010$。其他情况不变，故找到最长的 $01$ 交替序列的长度 $len$，答案为 $\lfloor\frac{len}{2}\rfloor$。考虑回原序列，也就是要找一个 $x$ 以及最长的区间 $[l, r]$ 使得区间内任意相邻的两数 $a_i,a_{i+1}$ 一个 $\le x$ 一个 $> x$。故设 $l_i=\min(h_i,h_{i+1}),r_i = \max(h_i,h_{i+1})$。区间 $[L, R]$ 是 $01$ 交替的当且仅当 $\max\limits_{i\in[l,r]} l_i < \min\limits_{i\in[l,r]}r_i$。固定 $R$，只要求出每个 $R$ 对应的最小的 $L$ 即可。枚举 $R$，开一个指针 $L$ 表示最小的 $L$，用两个单调队列维护最大的 $l_j$ 和最小的 $r_j$，如果加入 $l_R,r_R$ 后不合法就不断增加 $L$，保证单调队列里的下标都 $\ge L$ 即可。
再考虑每个位置 $i$ 最终的值，找到最大的 $d_i$ 满足 $A =\max\limits_{j\in[i-d_i,i+d_i)} l_j,B= \min\limits_{j\in[i-d_i,i+d_i)} r_j,A < B$ 。可以根据 $h_i$ 与相邻的数的大小以及 $d_i$ 的奇偶性讨论最终值是 $A$ 还是 $B$。如果 $h_i > h_{i-1},h_{i+1}$ 且 $d_i$ 是奇数取 $A$，$d_i$ 是偶数 $B$；否则 $h_i <h_{i-1},h_{i+1}$ 且 $d_i$ 是奇数取 $B$，偶数取 $A$。求 $d_i$ 可以预处理 ST 表加二分。发现如果知道 $d_{i-1}$ 那么区间 $[i-1-d_{i-1},i-1+d_{i-1}-1]$ 合法，$[i-2-d_{i-1},i-1+d_{i-1}]$ 就不合法，由此推出 $d_i\in [d_{i-1}-1,d_{i-1}+1]$ 。于是可以开两个双端单调队列维护 $l_j,r_j$ 解决这个问题，先尝试 $d_i=d_{i-1}+1$，后尝试 $d_{i-1}$，最后试 $d_{i-1}-1$。
于是总复杂度是 $O(n)$ 的。
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 5e5 + 50, inf = 1e9;
int n, h[maxn], l[maxn], r[maxn], q1[maxn], h1 = 1, t1 = 0, q2[maxn], h2 = 1, t2 = 0, d[maxn], A[maxn], B[maxn];
void Add(int x){
while(h1 <= t1 && l[q1[t1]] <= l[x]) t1--;
q1[++t1] = x;
while(h2 <= t2 && r[q2[t2]] >= r[x]) t2--;
q2[++t2] = x;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> h[i];
for(int i = 1; i < n; i++) {
l[i] = min(h[i], h[i + 1]);
r[i] = max(h[i], h[i + 1]);
}
int ans1 = 0;
q1[++t1] = 1, q2[++t2] = 1;
for(int i = 2, L = 1; i < n; i++) {
Add(i);
while(h1 <= t1 && h2 <= t2 && l[q1[h1]] >= r[q2[h2]]) {
if(q1[h1] == L) h1++;
if(q2[h2] == L) h2++;
L++;
}
if(h1 <= t1 && h2 <= t2) ans1 = max(ans1, i - L + 1);
}
cout << ans1 / 2 << '\n';
h1 = h2 = 1, t1 = t2 = 0;
for(int i = 2; i < n; i++) {
int D = d[i - 1], L = i - D - 1, R = i + D - 2, lim = min(i - 1, n - i);
bool ok = false;
if(D + 1 <= lim) {
int x = R + 1, y = R + 2,mx = -inf, mn = inf;
if(h1 <= t1) mx = l[q1[h1]];
if(h2 <= t2) mn = r[q2[h2]];
mx = max({mx, l[x], l[y]});
mn = min({mn, r[x], r[y]});
if(mx < mn){
Add(x), Add(y);
d[i] = D + 1, A[i] = l[q1[h1]], B[i] = r[q2[h2]];
ok = true;
}
}
if(ok) continue;
if(D > lim){
int newL = L + 2;
while(h1 <= t1 && q1[h1] < newL) h1++;
while(h2 <= t2 && q2[h2] < newL) h2++;
d[i] = D - 1;
if(d[i] > 0) A[i] = l[q1[h1]], B[i] = r[q2[h2]];
continue;
}
if(D == 0){ d[i] = 0; continue; }
int maxRest = -inf, minRest = inf;
if(h1 <= t1) {
if(q1[h1] == L) {
if(h1 + 1 <= t1) maxRest = l[q1[h1 + 1]];
} else maxRest = l[q1[h1]];
}
if(h2 <= t2) {
if(q2[h2] == L) {
if(h2 + 1 <= t2) minRest = r[q2[h2 + 1]];
} else minRest = r[q2[h2]];
}
int x = R + 1, mx = max(maxRest, l[x]), mn = min(minRest, r[x]);
if(mx < mn) {
if(h1 <= t1 && q1[h1] == L) h1++;
if(h2 <= t2 && q2[h2] == L) h2++;
Add(x), d[i] = D;
} else {
int newL = L + 2;
while(h1 <= t1 && q1[h1] < newL) h1++;
while(h2 <= t2 && q2[h2] < newL) h2++;
d[i] = D - 1;
}
if(d[i] > 0) A[i] = l[q1[h1]], B[i] = r[q2[h2]];
}
for(int i = 1; i <= n; i++) {
if(i > 1) cout << ' ';
if(i == 1 || i == n || d[i] == 0) {
cout << h[i];
} else if(h[i] > h[i - 1] && h[i] > h[i + 1]) {
cout << ((d[i] & 1) ? A[i] : B[i]);
} else {
cout << ((d[i] & 1) ? B[i] : A[i]);
}
}
cout << '\n';
return 0;
}
```