CF1437E Make It Increasing

给你一个数列 a ,一个集合 b , 对于每个 b 中的元素x， a_x 不能修改，其他都可以修改，问最少多少次可以将 a 修改为严格单调递增的。如果不存在，输出 -1 。

a 中的所有元素在任意时刻必须都是整数。

首先先判断是否合法，要保证两个不能改变的数a_{b_i}和a_{b_{i+1}}之间够不够放下b_{i+1}-b_i个数

if(a[b[i+1]]-a[b[i]]<b[i+1]-b[i])
    puts("-1");//放不下

然后考虑，如果要让序列递增，那么必有
a_{i+1}-a_i\geq 1
即
a_{i+1}-a_i\geq i+1-i
那么就是
a_{i+1}-(i+1)\geq a_i-i
那么我们令c_i=a_i-i，我们想使修改的数的尽量少，就要在原序列找到一个**包含所有不可修改的数 **（a_{b_i})的最长不下降子序列。

由于这个限制条件，必须在 nlogn 求 LIS 的方法下作出修改。

for(int i=1;i<=n;++i){
        if(!top||a[i]>=q[top]){
            q[++top]=a[i];
            if(i==b[t]){
                ++t;
                lb=top;
            }
        }
        else{
            int p=std::upper_bound(q+1,q+1+top,a[i])-q;
            if(p<=lb)   
                continue;
            q[p]=a[i];
            if(b[t]==i){
                ++t;
                lb=p;
                top=p;
            }
        }
    }

记录前一个必须包含的数的坐标为 lb ，如果当前的数a_i当前的可以接在子序列后，就直接接，如果受到限制，就记录。

如果不可以接，考虑更新最长子序列的数组。

在原数组中找到比a_i大的第一个数，记录下标为p

如果 p 在 lb 前面，由于a_{lb}>a_i，所以当前数不可更新子序列q数组。

然后可以考虑更新子序列q数组

如果当前的数是受限制的，那么子序列从当前数字后的数必须全部舍去（因为这个数必须加入子序列数组，如果不舍去，子序列就不是不下降的了）此时p成为了子序列数组的最后一个数。

#include<bits/stdc++.h>
const int N = 5e5+10;
int a[N],b[N],t=1,q[N],top=0;
int n,m,lb;
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;++i){
        scanf("%d",&b[i]);
    }
    std::sort(b+1,b+1+m);
    for(int i=1;i<=m-1;++i){
        if(a[b[i+1]]-a[b[i]]<b[i+1]-b[i]){
            puts("-1");
            return 0;
        }
    }
    for(int i=1;i<=n;++i)
        a[i]-=i;
    for(int i=1;i<=n;++i){
        if(!top||a[i]>=q[top]){
            q[++top]=a[i];
            if(i==b[t]){
                ++t;
                lb=top;
            }
        }
        else{
            int p=std::upper_bound(q+1,q+1+top,a[i])-q;
            if(p<=lb)   
                continue;
            q[p]=a[i];
            if(b[t]==i){
                ++t;
                lb=p;
                top=p;
            }
        }
    }
    printf("%d",n-top);
    return 0;
}