DDOSvoid's Blog

The 2020 ICPC Asia Macau Regional Contest J Jewel Grab

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

题目描述

http://codeforces.com/gym/103119/problem/J

简要题意：给定一个长度为 $n$ 的序列，每个位置有两个参数 $(c,v)$，$c$ 是这个位置的颜色，$v$ 是这个位置的价值，现在有 $m$ 次操作，每次操作要么更改一个位置的颜色和价值，要么查询从 $s$ 开始最多跳过 $k$ 次所能获得的最大价值，其中从 $s$ 开始跳过 $k$ 次表示，从 $s$ 开始向右走，每到一个点，我们可以选择跳过或者不跳过，如果不跳过则该点的颜色必须之前没有到过，然后我们获得该点的价值

$n,m\le 2\times 10^5,k\le 10$

Solution

注意到最多跳过 $10$ 次，所以我们可以考虑每次暴力找下一个需要跳过的点，注意到一个如果需要被跳过，那么它的 $pre$ 一定大于等于 $l$，那么现在就相当于用线段树找 $[x,y]$ 中位置最靠左的满足 $pre \ge l$ 的点，这个显然是线段树的经典做法，另外修改都是单点修改

时间复杂度 $O(kn\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
#include <iostream>
#include <set>
#include <vector>
#define maxn 200010
#define ll long long
#define lowbit(i) ((i) & (-i))
using namespace std;

int n, m, c[maxn], w[maxn];

ll Bit[maxn];
void add(int i, int v) { while (i <= n) Bit[i] += v, i += lowbit(i); }

ll get_sum(int i) {
    ll s = 0;
    while (i) s += Bit[i], i -= lowbit(i);
    return s; 
}

int pre[maxn];
set<int> S[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] = pre[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(int i, int l, int r, int L, int R, int k) {
    if (l > R || r < L || T[i] < k) return 0;
    if (l == r) return T[i] >= k ? l : 0;
    int m = l + r >> 1, v = query(lc, l, m, L, R, k);
    if (v) return v;
    else return query(rc, m + 1, r, L, R, k); 
}

inline void solve_1() {
    int x, y, z; cin >> x >> y >> z;
    add(x, z - w[x]); w[x] = z;
    auto l = S[c[x]].lower_bound(x), r = S[c[x]].upper_bound(x); --l;
    if (*r != n + 1) pre[*r] = *l, update(1, 1, n, *r, *l);
    S[c[x]].erase(x); c[x] = y; S[c[x]].insert(x); 
    l = S[c[x]].lower_bound(x), r = S[c[x]].upper_bound(x); --l;
    if (*r != n + 1) pre[*r] = x, update(1, 1, n, *r, x);
    pre[x] = *l; update(1, 1, n, x, *l);
}

int tmp[maxn];
inline void solve_2() {
    int x, y; cin >> x >> y;
    vector<int> vec; ll ans = 0; int p = x; 
    while (p <= n) {
        int t = query(1, 1, n, p, n, x);
        if (!t) { ans += get_sum(n) - get_sum(p - 1); break; }
        ans += get_sum(t - 1) - get_sum(p - 1);
        if (!y) break;
        if (!tmp[c[t]]) tmp[c[t]] = w[pre[t]], vec.push_back(c[t]);
        if (tmp[c[t]] < w[t]) ans += w[t] - tmp[c[t]], tmp[c[t]] = w[t];
        p = t + 1; --y;
    } cout << ans << "\n";
    for (auto t : vec) tmp[t] = 0; 
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> c[i] >> w[i], S[c[i]].insert(i); 
    for (int i = 1; i <= n; ++i) S[i].insert(0), S[i].insert(n + 1);
    for (int i = 1, last = 0; i <= n; ++i, last = 0)
        for (auto t : S[i]) 
            if (1 <= t && t <= n) pre[t] = last, last = t;
    build(1, 1, n);
    for (int i = 1; i <= n; ++i) add(i, w[i]); 
    for (int i = 1; i <= m; ++i) {
        int opt; cin >> opt;
        if (opt == 1) solve_1();
        else solve_2(); 
    }
    return 0;
}