#C240731D. 排序
网址（Website）
题解（Solution）
设 $g[i]$ 表示固定第 $i$ 位不替换，使 $[1,i-1]$ 位有序的最少操作次数，则有：
考虑最后的数组一定是一段没有替换，一段替换了的形式，枚举，我们直接令当前的 $j$ 为上一段替换部分结尾的下一个位置，且区间 $[j+1,i-1]$ 需要被全部替换为 $b[]$ 数组中的数，此时需满足值在 $[a[j],a[i]]$ 区间内的 $b[i]$ 至少有 $i-j$ 个，令 $s[i]$ 表示比 $a[i]$ 小的 $b[i]$ 有多少个，则转换为需满足 $s[i]-s[j]>i-j-1$，即 $s[i]-i+1>s[j]-j$ ，此时有： $g[i] = min_{j=1}^{i-2}(g[j]+(i-j-1))=i-1+min_{j=1}^{i-2}(g[j]-j)$ 。
特别的，如果 $a[i-1]<a[i]$ ，则 $g[i] = min(g[i-1],g[i])$ 。
很明显这样时间复杂度是 $O(n^2)$ 的，注意到每次要求的就是满足 $s[i]-i>s[j]-j-1$ 的 $g[j]-j$ 的最小值，我们直接用树状数组，以 $s[j]-j$ 为下标，维护 $g[j]-j$ 的值，每次查询时只需要查询 $[-5\times 10^5,s[i]-i+1]$ 的最小值，由于出现了负数下标，在update时需要将所有的下标加上 $5\times 10^5$ ，同时注意将树状数组的 $c[i]$ 初始化为极大值。
小知识：树状数组具有维护前缀任意值的能力，而当出现加减法等可以通过前缀相减来抵消的问题时，便有能力计算任意区间的数据。
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define fi first
#define se second
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2012345;
const int C = 501234;
int g[N],s[N];//比a[i]小的b[]的个数有多少
int n,m,a[N],b[N];
//树状数组维护 s[i]-i
#define lbt(x) (x&-x)
int c[N];//里面存的是g[i]-i-1
void update(int x,int v){
for(int i=x;i<=N-5;i+=lbt(i))
c[i] = min(c[i],v);
}
inline int ask(int x){
int res=inf;
for(int i=x;i;i-=lbt(i))
res = min(c[i],res);
return res;
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
freopen("sort.in","r",stdin),
freopen("sort.out","w",stdout);
cin>>n>>m;int Tim = clock();
For(i,1,n) cin>>a[i];
For(j,1,m) cin>>b[j];
sort(b+1,b+m+1);
memset(c,0x3f,sizeof c);
for(int i=1;i<=n;i++){//求出s[i]
s[i] = lower_bound(b+1,b+m+1,a[i])-b-1;
}
a[0] = -1, g[0] = 0;
a[n+1] = inf,s[n+1] = m;
//求g[i]
For(i,1,n+1){//固定i，到j
g[i] = i-1 + ask(s[i]-i+C);
// cerr<<s[i]-i<<' '<<g[i]-i<<'\n';
if(a[i]>a[i-1])
g[i] = min(g[i],g[i-1]);
update(s[i-1]-i+C,g[i-1]-i+1);
}cout<<(g[n+1]>n?-1:g[n+1])<<'\n';
return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}
