Codeforces1437 E. Make It Increasing（LIS）

题意：

你有一个长度为n的数列a和一个含有k个不同整数的集合b，b中的数都在[1,n]内。
现在你可以进行一些操作，每次操作中你可以选择两个数i和x，并将x赋值给ai。其中1<=i<=n，但i不能出现在集合b中，而x可为任意整数。
求出将数列a变为严格上升序列的最小操作次数。

题解：

  1. 首先实现严格递增是比较难处理的，我们可以通过a[i]=a[i]-1，问题就变成非严格递增
  2. 因为有k个位置不能改变，如果这k个位置并非严格递增，那题目无解。也就是a[b[i]]>a[b[i+1]]
  3. 如果有解，因为b[i]的存在，a会被分成好几部分，其实我们只需要实现每一部分的上升序列即可。也就是考虑每一部分最多可以保留多少个数，我们求出每一段[b[i]+1,b[i+1]-1]中的LIS，这就是最多可保留的
  4. 对于[b[i]+1,b[i+1]-1]这段里面的a[x],如果a[i]比左端小，比右端大，（a[x]<a[b[i]]或a[x]>a[b[i+1]]）那a[x]就一定是要修改的，那么a[x]就不必参与LIS的计算

    代码：

    #include<bits/stdc++.h>
using namespace std;
const int maxm=5e5+5;
int stk[maxm];
int a[maxm];
int b[maxm];
int n,m;
signed main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++){
      scanf("%d",&a[i]);
      a[i]-=i;
  }
  for(int i=1;i<=m;i++){
      scanf("%d",&b[i]);
  }
  for(int i=1;i<=m-1;i++){
      if(a[b[i]]>a[b[i+1]]){
          puts("-1");
          return 0;
      }
  }
  a[0]=-1e9,a[n+1]=1e9;
  b[0]=0,b[m+1]=n+1;
  int ans=0;
  for(int i=0;i<=m;i++){
      int len=0;
      for(int j=b[i]+1;j<=b[i+1]-1;j++){
          if(a[j]<a[b[i]]||a[j]>a[b[i+1]]){
              continue;
          }
          int l=1,r=len;
          int pos=-1;
          while(l<=r){
              int mid=(l+r)/2;
              if(stk[mid]>a[j])pos=mid,r=mid-1;
              else l=mid+1;
          }
          if(pos==-1)stk[++len]=a[j];
          else stk[pos]=a[j];
      }
      ans+=b[i+1]-b[i]-1-len;
  }
  printf("%d\n",ans);
  return 0;
}

```