http://codeforces.com/contest/1437

E. Make It Increasing

 

题意：给定数列 A 和 B ，每次操作任选 A 中一个数，修改成任意值，但是下标在 B 中的数不能改。问最少操作次数使得 A 严格递增。

树状数组

B 数组把 A 数组分成几块，对于每块单独处理。

两个数能够递增等价于 ai−aj≥i−ja_i-a_j\ge i-j，也就是 ai−i≥aj−ja_i-i\ge a_j-j。

所以要求最长非递减子序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int n, k;
int a[N], b[N], c[N];
vector<int>vc;
int mx[N];
void add(int q, int x) {
	for (int i = q; i <= n + 2; i += (i&-i))mx[i] = max(mx[i], x);
}
int qry(int r) {
	int res = 0;
	for (int i = r; i; i -= (i&-i))res = max(res, mx[i]);
	return res;
}
void clear(int q) {
	for (int i = q; i <= n + 2; i += (i&-i))mx[i] = 0;
}
int ans;
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (int i = 1; i <= k; i++)scanf("%d", &b[i]);
	for (int i = 1; i < k; i++) {
		if (a[b[i + 1]] - a[b[i]] < b[i + 1] - b[i]) {
			puts("-1");
			return 0;
		}
	}
	b[0] = 0, b[k + 1] = n + 1;
	a[0] = -INF, a[n + 1] = INF;
	for (int i = 0; i <= k; i++) {
		int l = b[i], r = b[i + 1];
		vc.clear();
		for (int j = l + 1; j <= r; j++) {
			if (a[j] - j < a[l] - l)continue;
			vc.push_back(a[j] - j);
		}
		sort(vc.begin(), vc.end());
		vc.erase(unique(vc.begin(), vc.end()), vc.end());
		for (int j = l + 1; j <= r; j++) {
			if (a[j] - j < a[l] - l)continue;
			c[j] = lower_bound(vc.begin(), vc.end(), a[j] - j) - vc.begin() + 1;
			int x = qry(c[j]);
			add(c[j], x + 1);
		}
		ans += r - l - qry(c[r]);
		for (int j = l + 1; j <= r; j++) {
			if (a[j] - j < a[l] - l)continue;
			clear(c[j]);
		}
	}
	printf("%d\n", ans);
	return 0;
}