【Codeforces 1167E】Range Deleting

原题链接：https://codeforces.ml/problemset/problem/1167/E

题目大意：

给出数组a，a_i<=m,长度为n

定义操作f(l,r)：将数组中 l<=a_i<=r删除后，得到的新数组。

问有多少对{l,r}，使得执行f(l,r)操作后，剩下的序列为单调不递减序列

例如：2 3 1 删掉2 3 后 变为 1 ，此时单调不递减，所以f(2,3)是可行操作f(2,3)

题目思路：

卡了一下午的题目叭..

这个题目确实有点惊讶到我(或许是太菜，被轻易惊讶、

首先，可以确定，如果删除一段区间[l,r]内所有的数之后，新数组单调不递减，在这基础上如果删掉[x,y] x<=l && y>=r 此时新数组绝对还是单调不递减，由此可见：删除操作具有单调性。

了解单调之后，考虑求区间个数采取尺取 或者 二分

之后便有了统一套路，可以不可以求出以l开头的所有合法区间？

所以只需要找到右边第一个合法的，那么向右扩充的区间全部合法

假设要删除的区间为[l,r] ，如果删除l,r区间后合法

那么需要满足[1,l-1]是单调不递减的的,[r+1,m]也是不递减的，并且满足 [1,l-1]所有的数 都在 [r+1,n]的左边即可

那么[l,r]即为合法区间

所以：

1.需要处理 1,pref 是否可行的最远的pref，当l-1大于pref时即不可行

2.需要处理 curf,n 是否可行的最近的curf，当r+1小于curf时即不可行

3.0 一定可行  n+1一定可行

4.之后我们预处理出 每个a_i 最左边出现的位置，与最右边出现的位置，当且仅当R[l-1]<L[r+1]时 区间可行

5.考虑到一些未出现的数字，5未出现但是还需要和6 作比较，那么取小于5的第一个数作比较，这里使用并查集进行优化。

6.最后套一下尺取模板，解决了问题：

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF=1e17;
const int maxn=2e6+6;
const int mod=1e9+7;
const double eps=1e-9;
const double PI = acos(-1);
inline bool read(ll &num)
{char in;bool IsN=false;
in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
int L[maxn],R[maxn];
int vis[maxn];
ll num[maxn];
int ls=0,rs=m+1;
int pre[maxn],cur[maxn];
int Find_pre(int x){
    if(!x) return x;
    if(!vis[x]) return pre[x]=Find_pre(pre[x]);
    return x;
}
int Find_cur(int x){
    if(x==m+1) return x;
    if(!vis[x]) return cur[x]=Find_cur(cur[x]);
    return x;
}
bool check(int l,int r){
    if(l-1<=ls&&r+1>=rs){
        int dx=Find_pre(l-1);
        int dy=Find_cur(r+1);
        if(R[dx]<L[dy]) return true;
    }
    return false;
}
int main(){
    read(n);read(m);
    for(int i=1;i<=m;i++) cur[i]=i+1,pre[i]=i-1;
    R[0]=0;
    L[m+1]=n+5;
    for(int i=1;i<=n;i++){
        read(num[i]);
        if(!L[num[i]]) L[num[i]]=i;
        R[num[i]]=i;
        vis[num[i]]=1;
    }
    int lst=0;
    for(int i=1;i<=m;i++){
        if(!L[i]){
            ls=i;
            continue;
        }
        if(L[i]<lst) break;
        ls=i;
        lst=R[i];
    }
    lst=n+5;
    for(int i=m;i>=1;i--){
        if(!L[i]){
            rs=i;
            continue;
        }
        if(R[i]>lst) break;
        rs=i;
        lst=L[i];
    }
    ll ans=0;
    int s=1;
    for(int i=1;i<=m;i++){
        while(s<=i&&check(s,i)){
            ans+=m-i+1;
            s++;
        }
    }
    printf("%lld\n",ans);
    return 0;
}
/**
###
**/

总结：

1.这个题的思路确实很妙，我一直卡就卡在怎样判断l,r区间是否可行，没想出O1的办法。换个思路：从[l,r]删除后的结果来反推，预处理即可O1判断区间可行