2019/5/16 day5 解题日志

2019-05-16

字数统计: 595字 | 阅读时长: 2分

给数列A和整数x，求有多少$pair<l,r>$满足$1\le l \le r \le x$，且对A删除在[l,r]值域内的元素后，剩余序列是非递减的。
题目链接

day5

思路

根据数据范围，可以猜想$O(nlogn)$或者$O(n)$的算法。

枚举$l$值，然后二分最小的$r$？枚举$l$，$O(1)$得到$r$的值？
不妨先想想，最小的r是多少？由于存在$i$和$j$，使得$i>j,a[i]<a[j]$，那么这对$(i,j)$是冲突的，可以发现，pair(l,r)要么覆盖$a[i]$，要么覆盖$a[j]$，那么$r=max(r,a[i])$；
回到第一条，首先我们遍历$l$的值$(1..x)$，预处理出一个最小的$r$，这时候我们就可以$O(1)$求出下一个$r$的值了。
对于$pair(1,r)$来说，一定是合法的，显然，对于$pair(1,a),a\le x$都合法，直接统计答案便可。
现在来看$pair(2,r)$的最小$r$怎么得到？
由于此时肯定没删除数字$1$，那么肯定要删除所有与数字$1$矛盾的数字，只需要找到最后一个$1$出现的位置的前面，大于$1$的最大数$b$便可，此时$r = max(r,b)$；
最后判断一下，这个$l$变成$l+1$，然后不删$l$是不是可以，如果可以就直接下一步，有没有不可以的情况呢？
假设有x小于l，且x和l有矛盾，在此之前x肯定是不被删除的，如果此时将l也不删除，就出现矛盾了，所以这里直接退出循环。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans;
const int maxn = 1e6+10;
int n,x;
int a[maxn];
int minid[maxn],maxid[maxn];
int maxv[maxn],minv[maxn];
int main(){
    scanf("%d%d",&n,&x);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        maxid[a[i]]=i;
        maxv[i]=max(maxv[i-1],a[i]);
    }
    minv[n+1]=x+1;
    for(int i=n;i>=1;i--){
        minid[a[i]]=i;
        minv[i]=min(minv[i+1],a[i]);
    }
    int LOW=1;
    for(int i=1;i<=x;i++){
        if(maxid[i]==0)continue;
        if(maxv[maxid[i]]>i)LOW=i;
    }
    for(int i=1;i<=x;i++){
        LOW=max(LOW,i);
        if(maxid[i]==0){
            ans+=(x-LOW+1);
            continue;
        }
        ans+=(x-LOW+1);
        LOW=max(LOW,maxv[maxid[i]]);
        if(i>minv[minid[i]])break;
    }
    cout<<ans;
    return 0;
}