[CF1454F] Array Partition - ST表,二分
Description
给定序列 (a),要求将其划分为三个非空子串(设三个子串长分别为 (x,y,z)),使得 (maxlimits_{i=1}^x a_i = minlimits_{i=x+1}^{x+y} a_i = maxlimits_{i=x+y+1}^n a_i)。
Solution
枚举 x,那么 y 会受到两个区间的限制
min 的限制区间用 ST 表 + 二分解出
max 的限制区间用后缀 max + 二分解出
#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << #x << ":=" << x << endl;
#define int long long
const int N = 200005;
const int M = 20;
int n, a[N], premax[N], sufmax[N], st[N][M];
int query(int l, int r)
{
if (l > r)
return 1e9;
int lg = log2(r - l + 1);
return min(st[l][lg], st[r - (1 << lg) + 1][lg]);
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i], st[i][0] = a[i];
for (int j = 1; j < M; j++)
for (int i = 1; i + (1 << (j - 1)) <= n; i++)
st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
for (int i = 1; i <= n; i++)
premax[i] = max(premax[i - 1], a[i]);
sufmax[n + 1] = 0;
for (int i = n; i >= 1; i--)
sufmax[i] = max(sufmax[i + 1], a[i]);
for (int x = 1; x < n; x++)
{
int val = premax[x];
int l1 = 1e9, r1 = 0, l2 = 1e9, r2 = 0;
{
int l = x + 1, r = n;
while (l < r)
{
int mid = (l + r) / 2;
if (query(x + 1, mid) <= val)
r = mid;
else
l = mid + 1;
}
if (query(x + 1, l) == val)
l1 = l;
}
{
int l = x + 1, r = n + 1;
while (l < r)
{
int mid = (l + r) / 2;
if (query(x + 1, mid) < val)
r = mid;
else
l = mid + 1;
}
if (query(x + 1, l - 1) == val)
r1 = l - 1;
}
{
int l = x + 1, r = n;
while (l < r)
{
int mid = (l + r) / 2;
if (sufmax[mid + 1] <= val)
r = mid;
else
l = mid + 1;
}
if (sufmax[l + 1] == val)
l2 = l;
}
{
int l = x + 1, r = n + 1;
while (l < r)
{
int mid = (l + r) / 2;
if (sufmax[mid + 1] < val)
r = mid;
else
l = mid + 1;
}
if (sufmax[l] == val)
r2 = l - 1;
}
int l = max(l1, l2), r = min(r1, r2);
if (l <= r)
{
// dbg(l1) dbg(l2) dbg(r1) dbg(r2)
cout
<< "YES" << endl;
cout << x << " " << l - x << " " << n - l << endl;
return;
}
}
cout << "NO" << endl;
}
signed main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--)
solve();
}