Educational Codeforces Round 39 (Rated for Div. 2) G

题意：

给一个序列\(a_i(1 <= a_i <= 10^{9}),2 <= n <= 200000\), 如果至多删除其中的一个数之后该序列为严格上升序列，那么称原序列为几乎严格上升序列。

现在每次将序列中的任意数字变成任意数字，问最少要操作几次才能将序列变成几乎严格上升子序列。

思路：

如果不考虑删除，求让整个序列都变成严格上升子序列的次数

求出\(序列a_i - i\)的最长不下降子序列的长度\(len\), \(n - len\)就是答案

现在来考虑删除一个数的情况

我们枚举删除第\(k\)个数 前面的数做变换\(a_i - i (i < k)\), 后面的数做变换\(a_i - (i-1) (i > k)\)

我们计算以k-1结尾的最长不下降子序列和后面某个\(a_j(a_j >= a_{k-1})\)起始的最长不下降子序列拼接起来得到的长度，更新答案即可

先离散化处理

维护以\(a_i\)结尾的的最长不下降子序列的长度和以\(a_i\)开始的最长不下降子序列的长度

假设先从后往前处理，可以处理出后缀，同时也可以计算出每个数要拼接的最长后缀的长度，再从前往后处理算出前缀，更新答案即可。

用线段树维护 复杂度\(O(nlogn)\)

#include<bits/stdc++.h>

#define LL long long

#define P pair<int,int>

using namespace std;

const int N = 4e5 + 10;

int a[N];

vector<int> b;

int n,nn;

int dppre[N],dpsuf[N],sufmx[N];

int mx[N << 2];

void update(int pos,int val,int l,int r,int rt){

    if(l == r){

        mx[rt] = max(mx[rt],val);

        return ;

    }

    int m = l + r >> 1;

    if(pos <= m) update(pos,val,l,m,rt<<1);

    else update(pos,val,m+1,r,rt<<1|1);

    mx[rt] = max(mx[rt << 1], mx[rt << 1|1]);

}

int querymx(int L,int R,int l,int r,int rt){

    if(L <= l && R >= r) return mx[rt];

    int ans = 0;

    int m = l + r>>1;

    if(L <= m) ans = max(ans, querymx(L, R, l, m, rt<<1));

    if(R > m) ans = max(ans, querymx(L, R, m + 1, r, rt<<1|1));

    return ans;

}

/*

10

5 6 7 8 9 5 10 11 12 13

*/

int main(){

    cin>>n;

    for(int i = 1;i <= n;i++){

        scanf("%d",a + i);

        b.push_back(a[i] - i);

        b.push_back(a[i] - i + 1);

    }

    sort(b.begin(), b.end());

    b.erase(unique(b.begin(),b.end()),b.end());

    nn = b.size();

    for(int i = n;i >= 1;i--){

        int pos = lower_bound(b.begin(), b.end(), a[i-1] - i+1) - b.begin() + 1;

        if(i == 1) pos = 1;

        sufmx[i-1] = querymx(pos, nn, 1, nn, 1);

        pos = lower_bound(b.begin(), b.end(), a[i] - i + 1) - b.begin() + 1;

        int v = querymx(pos, nn, 1, nn, 1);

        dpsuf[i] = v + 1;

        update(pos, dpsuf[i], 1, nn, 1);

        //cout<<i - 1<<" "<<sufmx[i - 1]<<" "<<v + 1<<endl;

    }

    for(int i = 1;i <= (nn<<2);i++){

        mx[i] = 0;

    }

    int ans = sufmx[0];

    for(int i = 1;i <= n;i++){

        int pos = lower_bound(b.begin(), b.end(), a[i] - i) - b.begin() + 1;

        int v = querymx(1, pos, 1, nn, 1);

        dppre[i] = v + 1;

        ans = max(dppre[i] + sufmx[i], ans);

        //cout<<i<<" "<<dppre[i]<<" "<<sufmx[i]<<endl;

        update(pos, dppre[i], 1, nn, 1);

    }

    cout<<max(0,n - 1 - ans)<<endl;

    return 0;

}

Educational Codeforces Round 39 (Rated for Div. 2) G的相关教程结束。