题目 | Max Min - 颢天笔记

AtCoder Beginner Contest 247

E - Max Min

https://atcoder.jp/contests/abc247/tasks/abc247_e

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $500$ points

Problem Statement

We have a number sequence $A = (A_{1}, A_{2}, \dots, A_{N})$ of length $N$ and integers $X$ and $Y$ . Find the number of pairs of integers $(L, R)$ satisfying all the conditions below.

$1 \leq L \leq R \leq N$
The maximum value of $A_{L}, A_{L + 1}, \dots, A_{R}$ is $X$ , and the minimum is $Y$ .

Constraints

$1 \leq N \leq 2 \times 10^{5}$
$1 \leq A_{i} \leq 2 \times 10^{5}$
$1 \leq Y \leq X \leq 2 \times 10^{5}$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $X$ $Y$
$A_{1}$ $A_{2}$ $\dots$ $A_{N}$

Output

Print the answer.

Sample Input 1

4 3 1
1 2 3 1

Sample Output 1

4

$4$ pairs satisfy the conditions: $(L, R) = (1, 3), (1, 4), (2, 4), (3, 4)$ .

Sample Input 2

5 2 1
1 3 2 4 1

Sample Output 2

0

No pair $(L, R)$ satisfies the condition.

Sample Input 3

5 1 1
1 1 1 1 1

Sample Output 3

15

It may hold that $X = Y$ .

Sample Input 4

10 8 1
2 7 1 8 2 8 1 8 2 8

Sample Output 4

36

我的笔记

数列分段

要满足 $max A [l \sim r] = X$ 和 $min A [l \sim r] = Y$ ，那么说明 $Y \leq A [l \sim r] \leq X$ 。如果有一个 $A_{i}$ 不在要求的最小值和最大值区域内，那么包含了 $A_{i}$ 的区间都不满足题意。那么我们大可以将原数列在 $A_{i}$ 处断开，求两个子数列的情况之和即可。

例如 $A = (2, 3, 1, 4, 5, 3, 6, 3, 2, 4)$ ， $X = 5, Y = 2$ ，那么可以将 $A$ 分裂成多个子数列： $(2, 3), (4, 5, 3), (3, 2, 4)$

时间复杂度： $O (N)$

计算每段数列的情况

我们将数列分段后，易得 $Y \leq A [l \sim r] \leq X$ ，那么只要区域中包含 $X$ 和 $Y$ ，这个区域就是符合条件的。

使用双指针，初始化 $l = r = 0$ ，区间中 $X$ 的个数 $c n t_{X} = 0$ ，区间中 $Y$ 的个数 $c n t_{Y} = 0$ ，答案 $a n s_{k} = 0$ .

如果该区间不符合条件，即 $c n t_{X} = 0$ 或 $c n t_{Y} = 0$ ，那么 $r$ 指针右移，然后更新 $c n t_{X}, c n t_{Y}$

如果该区间符合条件，即 $c n t_{X} > 0$ 且 $c n t_{Y} > 0$ ，那么 $r$ 指针现在的位置和右侧的所有位置都是成立的，那么 $a n s_{k} = a n s_{k} + (子数列长度 - r)$ ，然后 $l$ 指针右移，更新 $c n t_{X}, c n t_{Y}$ .

时间复杂度： $O (2 N)$

这样就可以得到该段数列的情况，题目答案 $r e s = \sum a n s_{k}$

总时间复杂度： $O (3 N)$

源码

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 10;
int N, X, Y;
int A[MAXN];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> X >> Y;
    for (int i = 0; i < N; i++)
        cin >> A[i];
    int i = 0;
    long long ans = 0;
    while (i < N)
    {
        vector<int> subseq;
        while (i < N && A[i] >= Y && A[i] <= X)
        {
            subseq.push_back(A[i]);
            i++;
        }
        if (!subseq.empty())
        {
            int l = 0, r = 0;
            int cnt_X = 0, cnt_Y = 0;
            if (subseq[0] == X)
                cnt_X++;
            if (subseq[0] == Y)
                cnt_Y++;
            while (l < subseq.size() && r < subseq.size())
            {
                if (!cnt_X || !cnt_Y)
                {
                    r++;
                    if (subseq[r] == X)
                        cnt_X++;
                    if (subseq[r] == Y)
                        cnt_Y++;
                }
                else
                {
                    ans += subseq.size() - r;
                    if (subseq[l] == X)
                        cnt_X--;
                    if (subseq[l] == Y)
                        cnt_Y--;
                    l++;
                }
            }
        }
        else
        {
            i++;
        }
    }
    cout << ans << endl;
    return 0;
}

题目 | Max Min