CF 1437E-Make It Increasing LIS+細節注意

代碼裡有詳細解釋

#include <cstdio>
#include <cstring>
#include <climits>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
#define pEnter putchar('\n')
#define sc(n) scanf("%d",&(n))
#define pInt(n) printf("%d\n", (n))
#define plInt(n) printf("%lld\n", (n))
#define scc(n, m) scanf("%d%d",&(n), &(m))
#define sccc(n, m, k) scanf("%d%d%d",&(n), &(m), &(k))
#define mem(arr, val) memset(arr, val, sizeof(arr))
#define pVarInt(v) printf("%s = %d\n",#v,(v))
#define rep(var, s, t) for(int var=(s); var<=(t); var++)
#define drep(var, s, t) for(int var=(s); var>=(t); var--)
inline void PrintArrInt(int arr[], int s, int e){rep(i, s, e)printf("%d%c",arr[i],i==e?'\n':' ');}

const int maxn = 5e5 + 5;
const int INF = 0x3f3f3f3f;
int N, K, a[maxn], b[maxn], t[maxn], cnt;

/*CF 1437E
    題意：給定一個數組，其中有些位置的數字固定不能改，其他位置可以随便改值，問使整個序列嚴格上升的最小改動次數(若無法達成輸出-1)
    思路：首先先不管限制，即對于一個序列，改最少次，讓它變成遞增序列
                将所有數字減去它的索引位置，即 a[i]-=i
                隻要找到處理後的數組的 最長 不下降 子序列的長度為len ，這些值就不用改，其他值要改，故答案為N-len
                這裡用到了一個轉化，因為如果題目不要求嚴格遞增的話，其實對原數組求一個 最長 不下降 子序列就可以了
                但是由于要嚴格遞增，例如 3 6 4 5，這樣的就不行了，6改成3或4都不滿足，即不能保證可以有合法的修改方法
                a[i]-=i後，很明顯，相同的值就可以滿足條件，例如 3 3 3，在原來的數組中為 4 5 6
                求得最長 不下降 子序列後，總有方法把其他值改好：3 6 4 5->3 4 4 5

                現在加上限制，對于固定的兩個位置之間，相當于求必須包含左右端點的  最長 不下降 子序列
                先将左端點加入序列，在貪心過程中保證不換掉左端點，完成後，在序列中找到右端點即可得到一定包含端點的序列
*/

int solve(int L, int R) {
    cnt = 0; t[++cnt]=a[L];
    rep(i, L+1, R) {//求最長 不下降 子序列
        if(a[i]>=t[cnt]) t[++cnt]=a[i];
        else {
            int p=upper_bound(t+1, t+cnt+1, a[i])-t;//！！！！由于是不下降，值可以相同，是以在貪心時要把>a[i]的值"拉"下來，如果用lower_bound對于
            if(p!=1) t[p]=a[i];                                                     //這樣的序列就求錯了：3 4 5 3 3 3 3 3 4
        }
    }
    int p=upper_bound(t+1, t+cnt+1, a[R])-t-1;//！！！！由于a[R]最後一個加入序列，是以一定在與a[R]值相同的一段序列的最右端，必須用upper_bound往
    return R-L+1-p;                                                             //最右邊找
}

int main() {
    scc(N, K);
    rep(i, 1, N) sc(a[i]), a[i]-=i;
    rep(i, 1, K) sc(b[i]);
    bool isok = true;
    b[0]=0, b[K+1]=N+1;
    a[0]=-INF, a[N+1]=INF;
    rep(i, 1, K) if(a[b[i]]>a[b[i+1]]) {isok=false; break;}
    if(!isok) pInt(-1);
    else {
        int ans = 0;
        rep(i, 0, K) {
            int L=b[i], R=b[i+1]; 
            ans+=solve(L, R);
        }
        pInt(ans);
    }
    return 0;
}