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;
}