DDOSvoid's Blog

CF 1418D Trash Problem

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

题目描述

https://codeforces.com/contest/1418/problem/D

Solution

我们考虑选两个垃圾桶之后，不妨令其坐标为 $x_1,x_4$

在 $x_1$ 左边的肯定从 $min$ 一直扫过去，在 $x_4$ 右边的肯定从 $max$ 扫过去

在 $x_1$ 和 $x_4$ 中间肯定有一个分界点，不妨令分界点两边的为 $x_2$ 和 $x_3$

可以得到总花费为 $max-min-(x_3-x_2)$

也就是需要维护最大间距，这个拿 $set$ 啥的维护一下就 $ok$

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
#include <iostream>
#include <set>
#include <cstdio>
#include <queue>
#define maxn 100010
#define INF 1000000001
using namespace std;

int n, m, a[maxn];

struct Heap {
    priority_queue<int> add, del;

    inline void erase(int x) { del.push(x); } 

    inline void push(int x) { add.push(x); }

    int top() {
        while (!del.empty() && add.top() == del.top()) add.pop(), del.pop();
        return add.top();
    }
} Q;

set<int> S;
set<int>::iterator it, It;

inline int query() {
    if (S.size() <= 4) return 0;
    int x = *--(--S.end()), y = *++S.begin(), z = Q.top(); 
    return *--(--S.end()) - *++S.begin() - Q.top();
} 

inline void solve_0() {
    int x; scanf("%d", &x);
    if (S.size() == 1) return (void) S.erase(x); 
    It = it = S.lower_bound(x); --it; ++It; 
    if (*it) Q.erase(x - *it); 
    if (*It != INF) Q.erase(*It - x);
    if (*it && *It != INF) Q.push(*It - *it); 
    S.erase(x);
    printf("%d\n", query()); 
} 

inline void solve_1() {
    int x; scanf("%d", &x);
    if (S.empty()) return (void) S.insert(x); 
    It = it = S.upper_bound(x); --it;
    if (*it) Q.push(x - *it);
    if (*It != INF) Q.push(*It - x);
    if (*it && *It != INF) Q.erase(*It - *it); 
    S.insert(x);
    printf("%d\n", query()); 
}

int main() {
    cin >> n >> m; S.insert(0); S.insert(INF); 
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        if (S.empty()) { S.insert(x); continue; } 
        It = it = S.upper_bound(x); --it;
        if (*it) Q.push(x - *it);
        if (*It != INF) Q.push(*It - x);
        if (*it && *It != INF) Q.erase(*It - *it); 
        S.insert(x); 
    } printf("%d\n", query());
    for (int i = 1; i <= m; ++i) { 
        int opt; scanf("%d", &opt);
        if (opt == 1) solve_1();
        else solve_0();
    } 
    return 0;
}