Educational Codeforces Round 65 (Rated for Div. 2) E. Range Deleting 二分 or 双指针

题目链接
题意：给你一个数组，让你求出满足删除 $(l,r)$(l,r)内所有值后，剩下的数组单调不减的 $(l,r),l\le r$(l,r),l≤r的对数。
思路：首先，对每个数进行预处理最先出现和最后出现的位置，若数组没这个数，则最后出现的位置设置成一个极大数，最先出现为0.
然后从大到小进行讨论，看不删这个数是否合法。意为：假设最大数为 $q$q，那么如果当前数为 $t$t,是否满足 $t-q$t−q所有数出现的位置均满足单调不减。满足既可以不删。然后用数组记录到 $t$t的最左边的坐标，不满足的话那么这个数必须删，也就是右指针的初始值。
然后从小到大进行累加贡献。先讨论不删这个数是否合法（同上），若不合法的话，则这个数必须删，后面也就不用讨论了。然后每次二分或者移动右指针进行讨论，设当前右指针为 $r$r，即要满足 $l_{right}\le r_{left}$lright​≤rleft​，不满足的话右指针往右移动即可。每次记录当前出现的最右的位置即可。
细节见代码

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 1e6 +11;
int n,x,a[N],l[N],r[N];
int b[N],c[N],R,dy,L;
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>x;
	for(int i=1;i<=x;i++)l[i]=n+33;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		r[a[i]]=i;
		if(l[a[i]]==n+33)l[a[i]]=i;
	}	
	LL ans=0;
	L=n+33;
	b[x+1]=n+34;
	for(int i=x;i>=1;i--){
		int sta=0;
		if(r[i]>L){sta=1;}
		b[i]=min(b[i+1],l[i]);
		if(sta){dy=i;break;}
		L=min(L,l[i]);
	}
	for(int i=1;i<=x;i++){
		int sta=0;
		if(l[i]<R)sta=1;
		dy=max(dy,i);
		int dx=dy,y=x,k=x+1;
		while(dy<=x&&b[dy+1]<=R)dy++;
		ans+=x-dy+1;
		if(sta)break;
		R=max(R,r[i]);
	}
	cout<<ans<<endl;
	return 0;
}