DDOSvoid's Blog

Luogu P6544 [CEOI2014] Cake

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

题目描述

https://www.luogu.com.cn/problem/P6544

简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和一个整数 $s$，满足 $a_i$ 互不相同，$s\in[1,n]$，现在有 $m$ 次操作，操作有两种，第一种操作给定 $i,e$，将 $a_i$ 变成第 $e$ 大，保证之前 $i$ 的排名大于 $e$；第二种操作给定 $x$，问从 $s$ 开始向两边拓展到 $x$ 最少需要拓展多少次，拓展规则如下，假设现在已经拓展了 $[l,r]$，那么下一次会从 $l-1$ 和 $r+1$ 中选择一个较小的进行拓展

$n\le 2.5\times 10^5,q\le 5\times 10^5,e\le 10$

Solution

我们考虑如果没有修改，那么每次查询相当找一段区间的最短的满足条件的后缀或者最短的满足条件的前缀，这个可以直接在线段树上二分

但问题是我们不能在以编号为下标的线段树上动态维护排名的修改，但注意到每次提升排名到前 $10$ 名，那么我们考虑不维护排名而是维护具体的数值，这样我们每次只需要修改排名在 $[1,e]$ 的数值即可

时间复杂度 $O(10n\log n+q\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
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <array>
#include <map>
#define maxn 250010
#define INF 1000000000
#define ll long long
using namespace std;

int n, m, s, a[maxn];
int k, id[maxn];

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

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

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

int query_mx(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) return T[i];
    int m = l + r >> 1;
    return max(query_mx(lc, l, m, L, R), query_mx(rc, m + 1, r, L, R)); 
}

int queryL(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L || T[i] < v) return 0;
    if (l == r) return T[i] > v ? l : 0;
    int m = l + r >> 1, ls = queryL(lc, l, m, L, R, v);
    if (ls) return ls;
    else return queryL(rc, m + 1, r, L, R, v); 
}

int queryR(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L || T[i] < v) return 0;
    if (l == r) return T[i] > v ? l : 0;
    int m = l + r >> 1, rs = queryR(rc, m + 1, r, L, R, v);
    if (rs) return rs;
    else return queryR(lc, l, m, L, R, v); 
}

int cnt;
inline void solve_1() {
    int x, y, rk = k; cin >> x >> y; 
    for (int i = y + 1; i <= k; ++i) if (id[i] == x) rk = i;
    for (int i = rk; i > y; --i) id[i] = id[i - 1]; id[y] = x;
    for (int i = y; i; --i) update(1, 1, n, id[i], ++cnt); 
}

inline void solve_2() {
    int x; cin >> x;
    if (x == s) return cout << 0 << "\n", void();
    if (x > s) {
        int v = query_mx(1, 1, n, s + 1, x);
        int res = queryR(1, 1, n, 1, s - 1, v);
        cout << (res ? x - res - 1 : x - 1) << "\n";
    } else {
        int v = query_mx(1, 1, n, x, s - 1);
        int res = queryL(1, 1, n, s + 1, n, v);
        cout << (res ? res - x - 1 : n - x) << "\n";
    } 
}

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

    cin >> n >> s; k = min(10, n); cnt = n; 
    for (int i = 1; i <= n; ++i) cin >> a[i];
    vector<int> tp(n + 1); for (int i = 1; i <= n; ++i) tp[i] = i;
    sort(tp.begin() + 1, tp.end(), [](const int &u, const int &v) { return a[u] > a[v]; });
    for (int i = 1; i <= k; ++i) id[i] = tp[i];
    build(1, 1, n); cin >> m;
    for (int i = 1; i <= m; ++i) {
        char c[3]; cin >> c;
        if (c[0] == 'E') solve_1();
        else if (c[0] == 'F') solve_2(); 
    }
    return 0;
}