首页 > 其他分享 >CF1454F

CF1454F

时间:2023-11-01 11:13:08浏览次数:42  
标签:CF1454F suf pre 端点 max rep &&

link

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

相关文章