CF1389F Bicolored Segments

发表于 | 阅读数

给 $n$条线段 $[l_i,r_i]$
每条有个颜色 $t_i\in\{0,1\}$求最多选出多少条线段，使没有不同颜色的线段相交。

显然离散化，以$r_i$排好序。

设$dp[r_i][1/0]$表示以$r$结尾。

$count(l,r,1)$表示$[l,r]$里面的$1$线段数量。

后面这部分$dp[x][0]+count(x+1,r_i,1)$发现可以在线段树上维护。

每个$[l_i,r_i],t_i$的线段，都会$x\in[1,l_i-1]$的$dp[x] [ ! t]+1$

然后每次更新维护下自身以及取最大值即可

$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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}
const int SN = 6e5 + 10;
struct Segment
{
    int tag[N << 2], maxx[N << 2];
    void pushup(int pos)
    {
        maxx[pos] = max(maxx[pos << 1 | 1], maxx[pos << 1]);
    }
    void addtag(int pos, int w)
    {
        maxx[pos] += w;
        tag[pos] += w;
    }
    void pushdown(int pos)
    {
        if (tag[pos])
        {
            addtag(pos << 1, tag[pos]);
            addtag(pos << 1 | 1, tag[pos]);
            tag[pos] = 0;
        }
    }
    void update(int pos, int ql, int qr, int w, int l, int r)
    {

        if (ql <= l && r <= qr)
        {

            addtag(pos, w);
            return;
        }
        pushdown(pos);
        int mid = (l + r) >> 1;
        if (ql <= mid)
            update(pos << 1, ql, qr, w, l, mid);
        if (mid < qr)
            update(pos << 1 | 1, ql, qr, w, mid + 1, r);
        pushup(pos);
    }
} t[2];

int l[N], r[N], f[N], li[N], num;
vector<int> g[N];
int main()
{
    int n = read();
    for (int i = 1; i <= n; i++)
    {
        l[i] = read(), r[i] = read();
        f[i] = read() - 1;
        li[++num] = l[i];
        li[++num] = r[i];
    }
    sort(li + 1, li + 1 + num);
    num = unique(li + 1, li + 1 + num) - li - 1;
    for (int i = 1; i <= n; i++)
    {
        l[i] = lower_bound(li + 1, li + 1 + num, l[i]) - li;
        r[i] = lower_bound(li + 1, li + 1 + num, r[i]) - li;
        g[r[i]].push_back(i);
    }
    int mx[2];

    for (int i = 1; i <= num; i++)
    {

        for (int x : g[i])
        {

            t[f[x] ^ 1].update(1, 0, l[x] - 1, 1, 0, num);
            //cout << f[x] << " " << 0 << " " << l[x] << endl;
        }
        mx[1] = 0, mx[0] = 0;
        for (int j = 0; j < 2; j++)
            mx[j ^ 1] = t[j].maxx[1];
        //cout << mx[1] << " " << mx[0] << endl;
        for (int j = 0; j < 2; j++)
            t[j].update(1, i, i, mx[j], 0, num);
    }
    printf("%d\n", max(t[1].maxx[1], t[0].maxx[1]));
}