DDOSvoid's Blog

CF 1437 Make It Increasing

发表于 分类于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/contest/1437/problem/E

Solution

首先我们考虑将 $a_i$ 减掉 $i$，这样原题限制就变成了使得序列单调不降了

首先不考虑 $b$ 的限制

尽量少的修改数等价于尽量多的保留

于是原问题转换为求最长不降子序列

现在我们考虑 $b$ 的限制，发现由于 $b$ 的存在，$b_i$ 和 $b_{i+1}$ 之间的序列是没有关系的

所以我们分区间做最长不降子序列

时间复杂度 $O(n\log n)$

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 500010
#define INF 1000500010
using namespace std;

int n, m, a[maxn], b[maxn];

int c[maxn], cnt; 
void init_hash() {
    for (int i = 1; i <= n; ++i) c[i] = (a[i] -= i); 
    sort(c + 1, c + n + 1); cnt = unique(c + 1, c + n + 1) - c - 1;
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(c + 1, c + cnt + 1, a[i]) - c;
}

int d[maxn], len; 

int ans; 
int main() {
    cin >> n >> m; n += 2; m += 2;
    a[1] = -INF; a[n] = INF; b[1] = 1; b[m] = n;
    for (int i = 2; i < n; ++i) cin >> a[i];
    for (int i = 2; i < m; ++i) cin >> b[i], ++b[i];
    init_hash();
    for (int i = 2; i <= m; ++i) {
        if (a[b[i - 1]] > a[b[i]]) return puts("-1"), 0;
        len = 0; int l = b[i - 1], r = b[i];
        for (int j = l; j <= r; ++j) {
            if (a[j] < a[l] || a[j] > a[r]) continue;
            if (a[j] >= d[len]) d[++len] = a[j];
            else *upper_bound(d + 1, d + len + 1, a[j]) = a[j];
        } ans += (r - l + 1) - len;
    } cout << ans << endl;
    return 0;
}