2019-2020 Winter Petrozavodsk Camp, Day 8: Almost Algorithmic Contest C StalinSort Algorithm

题目描述

https://codeforces.com/gym/103261/problem/C

简要题意：给定一个长度为 $n$ 的排列，现在从第二位开始进行操作，如果当前数大于前一个数，那么就什么都不做，否则需要选择删掉当前这个数或者前一个数，需要注意如果删掉前一个数需要保证删掉之后依然保证递增，另外对于每一位这个操作只能进行一次，求最多能保留多少数字

$n\le 5\times 10^5$

Solution

我们考虑 $dp$，令 $f_i$ 表示保留第 $i$ 的 $dp$ 值，然后我们注意下一个能接在 $i$ 之后的可以是哪些数

我们模拟一下这个过程，令 $nxt(i)$ 表示右边第一个大于 $a_i$ 的数的位置，注意到在 $[i+1,nxt(i)-1]$ 之间的所有数我们都要删掉，然后对于 $nxt(i)$ 我们必须保留，我们考虑继续向右走，对于一个大于 $a_i$ 的数，我们可以选择删掉 $nxt(i)$，留下这个数，直到我们走到 $nxt(nxt(i))$，这个数必须保留，综上所述，我们能够发现可以放在 $i$ 后面一个的数是 $[nxt(i),nxt(nxt(i))-1]$ 中大于 $a_i$ 的数，也就是说满足条件的 $j$ 是 $j\in[nxt(i),nxt(nxt(i))-1],a_j>a_i$

注意到后面那个条件是连续的，所以我们按照权值来做扫描线即可，时间复杂度 $O(n\log n)$

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#define maxn 500010
#define INF 1000000000
using namespace std;

int n, nxt[maxn], p[maxn], a[maxn];

#define lc i << 1
#define rc i << 1 | 1
struct Seg {
    int v, tag;
} T[maxn * 4]; 
inline void maintain(int i) { T[i].v = max(T[lc].v, T[rc].v); } 

void build(int i, int l, int r) {
    T[i].tag = -INF;
    if (l == r) return T[i].v = -INF, void();
    int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r);
    maintain(i); 
}

inline void Update(int i, int v) {
    T[i].v = max(T[i].v, v);
    T[i].tag = max(T[i].tag, v); 
}

inline void pushdown(int i) {
    int &tag = T[i].tag; if (tag == -INF) return;
    Update(lc, tag); Update(rc, tag);
    tag = -INF;
}

void update(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return Update(i, v); 
    int m = l + r >> 1; pushdown(i);
    update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v); 
}

int query(int i, int l, int r, int k) {
    if (l == r) return T[i].v;
    int m = l + r >> 1; pushdown(i);
    if (k <= m) return query(lc, l, m, k);
    else return query(rc, m + 1, r, k); 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], p[a[i]] = i; 
    stack<int> S; a[n + 1] = n + 1; nxt[0] = 1; nxt[n + 1] = n + 2; p[n + 1] = n + 1; 
    for (int i = 1; i <= n + 1; ++i) {
        while (!S.empty() && a[i] > a[S.top()]) nxt[S.top()] = i, S.pop();
        S.push(i); 
    } build(1, 1, n); 
    for (int i = 0; i <= n; ++i) {
        int v = i == 0 ? 0 : query(1, 1, n, p[i]); 
        update(1, 1, n, nxt[p[i]], nxt[nxt[p[i]]] - 1, v + 1);
    } cout << n - query(1, 1, n, n + 1) << "\n";
    return 0;
}