Soltion:
有一个比较显然的 \(O(n^2)\) 做法,枚举中间区间的左右端点,然后用前后缀 \(\max\) 和 st 表查询中间的 \(\min\),其实不用 st 表也行,确定左端点枚举右端点的时候顺便求一下就好。
考虑枚举左端点,以一个较快的方法求出右端点。
发现后缀 \(\max\) 和 确定左端点后的 \(\min_{i=l}^{r} a_i\) 都是具有单调递减的,可以二分来做。
我们设前缀 \(\max\) 为 \(a\),\(\min_{i=l}^{r} a_i\) 为 \(b\),以及后缀 \(\max\) 为 \(c\)。
如果 \(a = b = c\) 时直接输出即可。
如果 \(a > b, a < c\) 或者 \(a < b, a > c\) 这样的话是无解的,因为一个需要变大而一个需要变小,但是 \(b,c\) 都是单调递减的,所以不可能有三者相等的情况了。
对于 \(b,c\) 在 \(a\) 的同一侧的情况比较简单,直接缩小二分区间就好。
void solve() {
int n;
cin >> n;
vector<int> a(n + 1), pre(n + 1), suf(n + 1);
vector<vector<int> > f(n + 1, vector<int>(__lg(n) + 1));
rep(i, 1, n) cin >> a[i];
rep(i, 1, n)
pre[i] = (i == 1 ? a[1] : max(pre[i - 1], a[i]));
per(i, n, 1)
suf[i] = (i == n ? a[n] : max(suf[i + 1], a[i]));
rep(i, 1, n)
f[i][0] = a[i];
rep(j, 1, __lg(n))
rep(i, 1, n - (1 << j) + 1)
f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
auto query = [&](int l, int r) {
int k = __lg(r - l + 1);
return min(f[l][k], f[r - (1 << k) + 1][k]);
};
rep(i, 1, n - 2) {
int a = pre[i];
int l = i + 1, r = n - 1, res = -1;
while(l <= r) {
int mid = l + r >> 1;
int b = query(i + 1, mid), c = suf[mid + 1];
if((b < a && c > a) && (b > a && c < a)) break;
if(b == a && c == a) {
cout << "YES\n";
cout << i << ' ' << mid - i << ' ' << n - mid << '\n';
return;
}
if(b <= a && c <= a) r = mid - 1;
else l = mid + 1;
}
}
cout << "NO\n";
}
标签:CF1454F,suf,pre,端点,max,rep,&&
From: https://www.cnblogs.com/Svemit/p/17802573.html