Remove Extra One

发表于 更新于 分类于 ，

    给出一个1到n的排列a，如果a[j] < a[i], j<i，那么a[i]称之为record。

    现在需要删除a中一个元素，然后使得剩余的数的record最大。

Remove Extra One

Created by LXC on Wed May 10 00:09:29 2023

https://codeforces.com/problemset/problem/900/C

ranting: 1700

tag: brute force, data structures, math

题意

给出一个1到n的排列a，如果a[j] < a[i], j<i，那么a[i]称之为record。

现在需要删除a中一个元素，然后使得剩余的数的record最大。

题解

个人思路

考虑删除一个数a[i]对后续有多少个数成为record，记为rec[a[i]]

对于a[j]，如果前方只有一个数a[i]大于a[j]。那么a[j]可以为rec[a[j]]贡献1.

我们可以用树状数组找到前方有多少个数大于当前数，以及用单调栈求出前方最近的大于自己的数。

代码

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define N 100005
#define MOD 998244353
using namespace std;

int A[N];

void add(int x) {
    for (int i = x; i < N; i += i & -i) {
        A[i]++;
    }
}

int ask(int x) {
    int rt = 0;
    for (int i = x; i > 0; i = i & (i - 1)) {
        rt += A[i];
    }
    return rt;
}

void sol() {
    int n;
    cin >> n;
    vector<int> st, c(n + 1, 0), rec(n + 1, 0);
    int sz = 0;
    // rec[i] i是否已经是 record
    // c[i] 删除i后能能产生的record数
    // 对于i，删掉它，record 将变为 record总数-rec[i]+c[i]
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        add(x);
        while (st.size() && st.back() < x)
            st.pop_back();
        if (st.size() == 1 && ask(x) == i)
            c[st.back()]++;
        st.push_back(x);
        if (st.size() == 1) {
            sz++;
            rec[x]++;
        }
    }
    // for (int i = 1; i <= n; i++) {
    //     if (rec[i])
    //         cout << i << " ";
    // }
    // cout << "\n";
    int mx = 0, ans = 1;
    for (int i = n; i > 0; i--) {
        int e = sz - rec[i] + c[i];
        // cout << i << " " << e << "\n";
        if (e >= mx) {
            mx = e;
            ans = i;
        }
    }
    cout << ans << "\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}