Codeforces 1167 E Range Deleting 双指针+思维

题意

给一个数列\(a​\),定义\(f(l,r)​\)为删除\(a​\)中所有满足\(l<=a_i<=r​\)的数后的数列,问有多少对\((l,r)​\),使\(f(l,r)​\)是一个非递减的数列

分析

若\(f(l,r)​\)合法，则\(f(l,r+1),f(l,r+2),\dots,f(l,x)​\)也都是合法的

把每个数在\(a​\)中第一次出现的位置\(S​\)和最后一次出现的位置\(T​\),若\(f(l+1,r-1)​\)合法则满足

\(max(T_{a_1},T_{a_2},\dots,T_{a_l})<min(S_{a_r},S_{a_{r+1}},\dots,S_{a_x})\)

\(max(T_{a_1},T_{a_2},\dots,T_{a_{i-1}})<S_{a_i} ~for~all~2<=i<=l\)

\(T_{a_i}<min(S_{a_{i+1}},S_{a_{i+2}},\dots,S_{a_x}) ~for~all~r<=i<=x​\)

考虑双指针来扫\((l,r)​\),先移动\(r​\)指针使\(f(1,r-1)​\)为合法，对答案的贡献为\(x-r+2​\)

每次往后推\(l​\)和\(r​\),使\(f(l+1,r-1)​\)合法

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define bug cout<<"--------------"<<endl
using namespace std;
typedef long long LL;
const double PI=acos(-1.0);
const double eps=1e-6;
const int inf=1e9;
const LL llf=1e18;
const int mod=1e9+7;
const int maxn=1e6+10;
int n,x;
int ll[maxn],rr[maxn];
int l[maxn],r[maxn];
int main(){
    ios::sync_with_stdio(false);
    //freopen("in","r",stdin);
    cin>>n>>x;
    memset(l,0x3f3f3f,sizeof(l));
    memset(ll,0x3f3f3f,sizeof(ll));
    for(int i=1,d;i<=n;i++){
        cin>>d;
        l[d]=min(i,l[d]);
        r[d]=i;
    }
    for(int i=1;i<=x;i++){
        rr[i]=max(rr[i-1],r[i]);
    }
    for(int i=x;i>=1;i--){
        ll[i]=min(l[i],ll[i+1]);
    }
    int R=x;
    LL ans=0;
    while(ll[R]>=r[R-1]&&R>=1) R--;
    for(int i=0;i<x;i++){
        if(i!=0&&l[i]<rr[i-1]) break;
        while(R<=i+1||rr[i]>ll[R]){
            R++;
        }
        ans+=x-R+2;
    }
    cout<<ans<<endl;
    return 0;
}