题目描述

难度分:$2100$

输入$n(1 \leq n \leq 10^6)$，$x(1 \leq x \leq 10^6)$和长为$n$的数组$a(1 \leq a[i] \leq x)$。

定义$D(a,L,R)$为删除$a$中所有元素值在$[L,R]$中的元素后，剩余的元素组成的数组（不改变顺序）。

输出有多少对$(L,R)$满足$1 \leq L \leq R \leq x$且$D(a,L,R)$是非降数组，即相邻元素左边$\leq$右边。

输入样例$1$

3 3
2 3 1

输出样例$1$

4

输入样例$2$

7 4
1 3 1 2 2 4 3

输出样例$2$

6

算法

双指针

这个题的值域$x$和数组长度$n$都这么大，估计就是要做到线性的时间复杂度，大体肯定是要枚举一个端点，然后确定另一个端点的范围。我们可以发现一个单调性，当把$[l,r]$区间中的数删掉能够满足剩下的子序列是单调不减，则删掉$[l,r+1]$、$[l,r+2]$、……这些右端点更右的区间肯定也是可以的，因此枚举$l$确定最小能够满足条件的$r$，那么这个$l$对答案的贡献就会是$x-r+1$，把每个$l$的贡献累加起来就是答案。

构建$4$个辅助数组$first$、$last$、$pre$和$suf$，其中$first[num]$表示数组$a$中$num$出现的最早位置，$last[num]$表示数组$a$中$num$出现的最晚位置，$pre[i]$表示区间$[1,i]$里的数出现的最晚位置，$suf[i]$表示$[i,x]$区间里的数出现的最早位置。

考虑$l-1$到$l$的变化，此时从$l$开始删，那$l-1$就不会被删掉。需要保证$[1,l-2]$的所有数都在$l-1$的左边，因此$pre[l-2] \lt first[l-1]$。考虑$r$到$r+1$的变化，如果$pre[l-1] \gt suf[r+1]$，说明$\leq l-1$的数全部出现完会越过$[r+1,x]$区间里第一次出现的数，不合题意需要右移$r$指针直到$pre[l-1] \leq suf[r+1]$，就找到了最近的$r$。

复杂度分析

时间复杂度

预处理出$first$和$last$两个数组的时间复杂度是$O(n)$，预处理出$pre$和$suf$的时间复杂度为$O(n)$，因此预处理的时间复杂度为$O(n+x)$。之后双指针统计答案的时间复杂度是$O(x)$，整个算法的时间复杂度就是$O(n+x)$。

空间复杂度

除去输入的数组$a$，$first$、$last$、$pre$、$suf$的空间都取决于$a[i]$的值域，因此额外空间复杂度为$O(x)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 1000010, INF = 0x3f3f3f3f;
int n, x, a[N], first[N], last[N], suf[N], pre[N];

int main() {
    scanf("%d%d", &n, &x);
    memset(first, 0x3f, sizeof(first));
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if(first[a[i]] == INF) first[a[i]] = i;
        last[a[i]] = i;
    }
    // pre[i]表示[1,i]最晚出现的位置
    for(int i = 1; i <= x; i++) {
        pre[i] = max(pre[i - 1], last[i]);
    }
    // suf[i]表示[i,x]最早出现的位置
    suf[x] = first[x], suf[x + 1] = INF;
    for(int i = x - 1; i >= 1; i--) {
        suf[i] = min(suf[i + 1], first[i]);
    }
    int r = x - 1;
    while(r >= 1 && last[r] < suf[r + 1]) {
        r--;
    }
    long long ans = 0;
    for(int l = 1; l <= x; l++) {
        if(l > 2 && first[l - 1] < pre[l - 2]) break;
        while(r <= x && (r < l || pre[l - 1] > suf[r + 1])) {
            r++;
        }
        ans += x - r + 1; 
    }
    printf("%lld\n", ans);
    return 0;
}