Problem – C – Codeforces

题意：你有一个斯大林排序算法，维护一个已排序序列，如果新加入的数仍然有序则不进行操作，否则可以毙掉新加的数或者序列里最后一个数，但是枪毙只能进行一次，如果毙掉原来的数后不满足有序则不能这样操作。

问对给定排列执行这个算法之后最少删除几个数，$n \le 5\times 10 ^ 5$。

不难看出加入一个新的数时只会和当前最后一个数有关系，所以可以维护一个DP数组$dp_i$表示以$i$结尾时最多保留几个数，那么如果$i<j$且$dp_i$可以转移到$dp_j$，则说明$i$和$j$可以共存于最后的序列中。

考虑如何维护这个东西。

题解的结论是这样的：设$next_i$表示第一个比$i$大的位置，则每个$i$可以转移到的$j$一定在$[next_i, next_{next_i})$内。（当然还要加上一个$a_i < a_j$的限制）

证明待补

有了这个结论之后逐个求DP值就行了，用一个线段树维护$a_i$这一维。

方便起见，可以规定$a_0 = 0$，$a_{n + 1} = n + 1$，这样就可以从一个必定在最终序列里的数开始DP，而后者是为了方便限制$next_i$。

#include <bits/stdc++.h>
 
using namespace std;
 
constexpr int maxn = 500005, maxm = (1 << 20) + 3;
 
int mx[maxm], M;
 
void modify(int x, int d) {
	mx[x += M + 1] = d;
 
	while (x > 1) {
		mx[x >> 1] = max(mx[x], mx[x ^ 1]);
		x >>= 1;
	}
}
 
int query(int r) {
	int ans = -0x3f3f3f3f, l = 1;
 
	for (l += M - 1, r += M + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
		if (~l & 1)
			ans = max(ans, mx[l ^ 1]);
		if (r & 1)
			ans = max(ans, mx[r ^ 1]);
	}
 
	return ans;
}
 
vector<pair<int, int> > u[maxn];
vector<int> v[maxn];
 
int dp[maxn], nx[maxn], a[maxn], stk[maxn];
 
int main() {
 
	int n;
	scanf("%d", &n);
 
	M = 1;
	while (M <= n + 1)
		M *= 2;
 
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	
	int top = 0;
	stk[0] = a[n + 1] = n + 1;
 
	for (int i = n; i; i--) {
		while (a[stk[top]] < a[i])
			top--;
		
		nx[i] = stk[top];
		
		stk[++top] = i;
	}
 
	memset(dp, -63, sizeof(dp));
	memset(mx, -63, sizeof(mx));
	
	dp[0] = 0;
 
	modify(0, 0);
	v[nx[1]].push_back(0);
 
	int ans = 0;
 
	for (int i = 1; i <= n; i++) {
		for (auto pi : u[i])
			modify(pi.first, pi.second);
		
		for (auto x : v[i])
			modify(x, -0x3f3f3f3f);
 
		int tmp = query(a[i]);
 
		if (tmp < 0)
			continue;
		
		dp[i] = tmp + 1;
		ans = max(ans, dp[i]);
 
		// printf("dp[%d] = %d\n", i, dp[i]);
		
		if (nx[i] == n + 1)
			continue;
		
		int l = nx[i], r = nx[nx[i]];
		// printf("l = %d  r = %d\n", l, r);
 
		u[l].push_back(make_pair(a[i], dp[i]));
		v[r].push_back(a[i]);
	}
 
	printf("%d\n", n - ans);
 
	return 0;
}