参考资料：
[1]:https://blog.****.net/weixin_43262291/article/details/90271693
题意：
给你一个包含 n 个数的序列 a，并且 max{ai} ≤ x；
定义一个操作 f(L,R) 将序列 a 中 L ≤ ai ≤ R 的数删除；
问有多少对满足条件的 (L,R) 使得执行完 f(L,R) 操作后的序列非递减；
题解：
[1]博文看了一晚上，终于理解了；
枚举左区间 i，找到符合条件的最小的右区间 ki，f(1,k1),f(2,k2),....,f(x,kx)；
如果执行完 f(1,k1) 后序列非递减，那么执行完 f(1,k1+1),f(1,k1+2),....,f(1,x) 后同样会使得序列非递减；
f(i,ki)同理，那么最终答案就是 (x-k1+1)+(x-k2+1)+......+(x-kx+1)；
如何高效的求解k1,k2,....,kx呢?
首先看看相关变量解释：
int n,x;///max{a[i]} <= x
int a[maxn];
int l[maxn];///l[i]:数字i第一次出现的位置
int r[maxn];///r[i]:数字i最后一次出现的位置
int L[maxn];///L[i]:数字[i,n]最先出现的位置
int R[maxn];///R[i]:数字[1,i]最后出现的位置
预处理出l,r,L,R数组：
mem(l,INF);
mem(r,);
for(int i=;i <= n;++i)
{
l[a[i]]=min(i,l[a[i]]);
r[a[i]]=i;
}
mem(L,INF);
mem(R,);
for(int i=x;i >= ;--i)
L[i]=min(L[i+],l[i]);
for(int i=;i <= x;++i)
R[i]=max(R[i-],r[i]);
明确一点，k1 ≤ k2 ≤ ...... ≤ kx；
那么，首先求出 k1，然后，递推出 ki；
如何求解k1呢？
上述查找可转化为找最小的 k1 使得 [k1+1,x] 组成的序列非递减；
int k=x;///如果[k,x]非递减，那么k-1找下一个位置
for(;k > && r[k] <= L[k+];--k);
如何根据 k1 递推出 ki 呢？
for(int i=;i <= x && R[i-] <= l[i-];++i)
for(;k < i || R[i-] > L[k+];++k);///找到第一个使得R[i-1]>=L[k+1]的k
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define INF 0x3f3f3f3f
const int maxn=1e6+; int n,x;///max{a[i]} <= x
int a[maxn];
int l[maxn];///l[i]:数字i第一次出现的位置
int r[maxn];///r[i]:数字i最后一次出现的位置
int L[maxn];///L[i]:数字[i,n]最先出现的位置
int R[maxn];///R[i]:数字[1,i]最后出现的位置 ll Solve()
{
mem(l,INF);
mem(r,);
for(int i=;i <= n;++i)
{
l[a[i]]=min(i,l[a[i]]);
r[a[i]]=i;
}
mem(L,INF);
mem(R,);
for(int i=x;i >= ;--i)
L[i]=min(L[i+],l[i]);
for(int i=;i <= x;++i)
R[i]=max(R[i-],r[i]); int k=x;///如果[k,x]非递减，那么k-1找下一个位置
for(;k > && r[k] <= L[k+];--k); ll ans=x-k+; ///要确保[1,i-1]非递减
///且已知[k+1,x]非递减
for(int i=;i <= x && R[i-] <= l[i-];++i)
{
for(;k < i || R[i-] > L[k+];++k);///找到第一个使得R[i-1]>=L[k+1]的k ans += x-k+;
}
return ans;
}
int main()
{
// freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin);
scanf("%d%d",&n,&x);
for(int i=;i <= n;++i)
scanf("%d",a+i); printf("%lld\n",Solve());
return ;
}