DDOSvoid's Blog

CF 1389F Bicolored Segments

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

题目描述

https://codeforces.com/contest/1389/problem/F

Solution

首先将区间按照右端点排序

不妨令 $f[i][0/1]$ 表示右端点是 $i$，最后一段区间的颜色是 $0/1$

不妨设当前线段的颜色为 $t$，左端点为 $l$

那么我们的转移应该是 $max_{i=0}^{l-1}\lbrace f[i][t~xor~1]+c[i+1][l]\rbrace$

注意到我们可以在枚举右端点的过程中，维护 $f[i][t~xor~1]+c[i+1][l]$

这个可以直接拿线段树维护，时间复杂度 $O(n\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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#define maxn 200010
#define Maxn 400010
#define ll long long
using namespace std;

int n;

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

    void update_add(int i, int l, int r, int L, int R, int v) {
        if (l > R || r < L) return ;
        if (L <= l && r <= R) return (void) (T[i].v += v, T[i].add += v);
        int m = l + r >> 1;
        update_add(lc, l, m, L, R, v); update_add(rc, m + 1, r, L, R, v);
        maintain(i);
    }

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

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

struct node {
    int l, r, t; 
} a[maxn];

int b[maxn * 2], cnt;
void init_hash() {
    for (int i = 1; i <= n; ++i) b[i] = a[i].l, b[i + n] = a[i].r;
    sort(b + 1, b + 2 * n + 1); cnt = unique(b + 1, b + 2 * n + 1) - b - 1;
    for (int i = 1; i <= n; ++i) {
        a[i].l = lower_bound(b + 1, b + cnt + 1, a[i].l) - b;
        a[i].r = lower_bound(b + 1, b + cnt + 1, a[i].r) - b;
    }
}

vector<pair<int, int>> A[2 * maxn];

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].l >> a[i].r >> a[i].t;
    init_hash(); for (int i = 1; i <= n; ++i) A[a[i].r].emplace_back(a[i].l, a[i].t - 1);
    for (int i = 1; i <= cnt; ++i) 
        for (auto u : A[i]) {
            int t = u.second, l = u.first;
            T[t ^ 1].update_add(1, 0, cnt, 0, l - 1, 1);
            int v = T[t ^ 1].query(1, 0, cnt, 0, l - 1);
            T[t].update_v(1, 0, cnt, i, T[t ^ 1].query(1, 0, cnt, 0, l - 1));
        }
    cout << max(T[0].query(1, 0, cnt, 0, cnt), T[1].query(1, 0, cnt, 0, cnt)) << "\n"; 
    return 0;
}