cf 1167 E.

题意

给出n个x范围的数，求删除范围在[L, R]的数，使得该序列成为一个非严格递增的序列，问有多少对数？（注空序列也算进答案，即[1,x]也是答案

题解

1.可以看出，如果删除[1, i]是符合题意的答案，那么[1, i+1] ~ [1, x]都是符合题意的答案。

2.如果[1, i]不是合法的，那么[2, i]也不可能是合法的。所以左右指针都只会往前移；

3.如果[L, R]是合法的，那么答案贡献是 x - R + 2;

判断区间[L, R]是否合法的：

[1, L-1]的数最靠后的位置 < [R + 1, x]的数最靠前的位置

下面继续捋一捋怎么写代码：

先找出最小的i，满足[1, i]是合法的。

把左指针往前移，如果[2, i]不合法，就把右指针往后移，直到合法！

如果i最靠前的位置 > [1, i - 1]最靠后的位置，说明左指针往后移也不可能出现合法的了。

#include 
    
     #include 
     
      #include 
      
       using std::max;using std::min;int l[1000010], ll[1000010], r[1000010], rr[1000010];int main() {    int n, x, a;    scanf("%d %d", &n, &x);    memset(l, 0x3f3f3f3f, sizeof(l));    memset(ll, 0x3f3f3f3f, sizeof(ll));    for(int i = 1; i <= n; i++) {        scanf("%d", &a);        l[a] = min(i, l[a]);        r[a] = i;    }    for(int i = 1; i <= x; i++) {        rr[i] = max(rr[i-1], r[i]);//rr记录[1, i]最靠后的位置        ll[x - i + 1] = min(l[x - i + 1], ll[x - i + 2]);//ll记录[i, x]最靠前的位置    }    int R = x;    long long ans = 0;    while(ll[R] >= r[R-1] && R >= 1) R--;//算出最小的i    for(int i = 0; i < x; i++) {        if(i && l[i] < rr[i-1]) break;//i最靠前的位置>[1, i - 1]最靠后的位置        while(R <= i + 1 || rr[i] > ll[R]) R++;//右指针往后移，直到找到合法的区间，        ans += x - R + 2;    }    printf("%lld\n", ans);    return 0;}