CF1454F Array Partition

2021-09-04

Solution

751 Words

题目大意

给定一个长度为 $n$ 的序列 $a$ ，要求将其划分为三个非空字串，长度分别为 $x, y, z$ ，满足：
$$
\max_{i=1}^x a_i = \min_{i=x+1}^{x+y}a_i = \max_{i=x+y+1}^n a_i
$$
若存在方案，输出 $\texttt{YES}$ 和任意一组 $x, y, z$ 的值；若不存在，输出 $\texttt{NO}$。

$3 \leq n \leq 2 * 10^5, 1 \leq a_i \leq 10^9$

题目分析

已经有很多题解做法是枚举 $x$ 了，这里提供一种另类的做法。

我们考虑对于 $\forall i \in [2,n-1]$ 的$i$，检测 $a_i$ 作为 $\min_{i=x+1}^{x+y}a_i$ 是否可行。

首先我们可以预处理出每个 $i$ 左右比他小的第一个数，可在 $ \Theta(n) $ 时间内使用单调栈处理出。

接着我们预处理出前缀和后缀最大值，这样就可以用二分处理出以 $a_i$ 为最大值的最长/最短前/后缀长度。

在处理出这些东西后，我们就可以根据这些信息来快速判断一个位置是否可行（具体实现参见代码）。

由于我们只要输出任意一组答案，故我们可以在找到可行的 $i$ 之后枚举 $x, y$ ，总时间复杂度 $\Theta(n \log n)$。

代码

#include <bits/stdc++.h>

#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)
#define meow(cat...) fprintf(stderr, cat)

const int MaxN = 4e5 + 10;

std::vector<int> v;
std::unordered_map<int, int> cnt;
int premax[MaxN], sufmax[MaxN];
int n, flag, a[MaxN], l[MaxN], r[MaxN];

void init()
{
    cnt.clear();
    for(int i = 0; i <= n + 9; i++)
        l[i] = r[i] = premax[i] = sufmax[i] = 0;
}

inline int read()
{
    int x = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0')
        ch = getchar();
    while (ch <= '9' && ch >= '0')
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}

signed main()
{
    int T = read();
    while (T--)
    {
        n = read(), flag = 0, init();
        for (int i = 1; i <= n; i++)
            a[i] = read(), cnt[a[i]] += 1, 
                premax[i] = std::max(premax[i - 1], a[i]);
        v.clear(), v.push_back(0);
        for(int i = 1; i <= n; i++)
        {
            while(v.size() && a[v.back()] >= a[i])
                 v.pop_back();
            l[i] = v.back(), v.push_back(i);
        }
        v.clear(), v.push_back(n + 1);
        for(int i = n; i; i--)
        {
            while(v.size() && a[v.back()] >= a[i])
                v.pop_back();
            r[i] = v.back(), v.push_back(i);
        }
        for(int i = n; i; i--)
            sufmax[i] = std::max(sufmax[i + 1], a[i]);
        std::reverse(sufmax + 1, sufmax + n + 1);
        for(int i = 2; i < n; i++)
        {
            int l1 = std::lower_bound(premax + 1, premax + n + 1, a[i]) - premax;
            int r1 = std::upper_bound(premax + 1, premax + n + 1, a[i]) - premax - 1;
            int r2 = n + 1 - (std::lower_bound(sufmax + 1, sufmax + n + 1, a[i]) - sufmax);
            int l2 = n + 1 - (std::upper_bound(sufmax + 1, sufmax + n + 1, a[i]) - sufmax) + 1;
            // meow("$ %d %d %d %d %d %d %d %d\n", i, a[i], l1, r1, l2, r2, l[i], r[i]);
            if(l[i] > r1 || l1 > r[i] || l[i] > r2 || l2 > r[i] || l1 >= i || r2 <= i
                || l1 > r1 || l2 > r2 || cnt[a[i]] < 3) { /*meow("-1\n");*/ continue; }
            // if(premax[l1] != a[i] || premax[r1] != a[i] || 
            //     sufmax[l2] != a[i] || sufmax[r2] != a[i]) { meow("-2\n"); continue; }
            int a = 0, b = 0;
            for(int j = i - 1; j >= l[i]; j--)
                if(l1 <= j && j <= r1)
                    if(l[i] <= j + 1 && j + 1 <= r[i]) { a = j; break; }
            for(int j = i - a; a + j <= r[i]; j++)
                if(l2 <= j + a + 1 && j + a + 1 <= r2)
                    if(l[i] <= j + a && j + a <= r[i]) { b = j; break; }
            // if((!(a < i && i <= a + b)) || a == 0 || b == 0) { /*meow("%d %d -3\n", a, b);*/ continue; }
            printf("YES\n%d %d %d\n", a, b, n - a - b), flag = 1; break;
        }
        if(!flag) puts("NO");
    }
    return 0;
}

二分, 枚举, 贪心

CF1454F Array Partition

题目大意

题目分析

代码

目录

分类

Your browser is out-of-date!