CF377D-Developing Game

发表于 | 阅读数

有 $n$ 个人，每人有属性 $l_i,v_i,r_i(l_i\leq v_i\leq r_i)$,要求选出最大的人的集合$S$ 使得 $\forall x,y\in S$ 有 $l_y\leq v_x\leq r_y$

分析可得$l_{max}\leq v_{min}\leq v_{max}\leq r_{min}$

等价于存在$l_{max}\leq x\leq v_{min}, v_{max}\leq y\leq r_{min}$

$l_{max}\leq x\leq v_{min}$,相当于所有$[l,v]$相交，同理相当于所有$[v,r]$相交,询问是否存在这个区域。就相当于二维相交问题，扫描线解决。

  • 考虑到记录方案数，只需要把最多重叠区域中的$(x,y)$，顺便记录下来，通过之前的等式判断哪些人是否符合即可。
代码 
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 3e5 + 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 SEN = 3e5 + 10;
struct segmentTree
{
    pii maxx[SEN << 2];
    int lazy[SEN << 2];
    void addtag(int pos, int l, int r, int w)
    {
        lazy[pos] += w;
        maxx[pos].first += w;
    }
    void pushdown(int pos, int l, int r)
    {
        if (lazy[pos])
        {
            int w = lazy[pos];
            int mid = (l + r) >> 1;
            addtag(pos << 1, l, mid, w);
            addtag(pos << 1 | 1, mid + 1, r, w);
            lazy[pos] = 0;
        }
    }
    void pushup(int pos)
    {
        maxx[pos] = max(maxx[pos << 1 | 1], maxx[pos << 1]);
    }
    pii query(int ql, int qr, int pos, int l, int r)
    {
        if (ql <= l && r <= qr)
        {
            return maxx[pos];
        }
        pushdown(pos, l, r);
        int mid = (l + r) >> 1;
        pii ans = mk(0, 0);
        if (ql <= mid)
            ans = max(ans, query(ql, qr, pos << 1, l, mid));
        if (qr > mid)
            ans = max(ans, query(ql, qr, pos << 1 | 1, mid + 1, r));
        return ans;
    }
    void update(int ql, int qr, int w, int pos, int l, int r)
    {
        if (ql <= l && r <= qr)
        {
            addtag(pos, l, r, w);
            return;
        }
        pushdown(pos, l, r);
        int mid = (l + r) >> 1;

        if (ql <= mid)
            update(ql, qr, w, pos << 1, l, mid);
        if (qr > mid)
            update(ql, qr, w, pos << 1 | 1, mid + 1, r);
        pushup(pos);
    }
    void build(int pos, int l, int r)
    {
        if (l == r)
        {
            maxx[pos].second = l;
            return;
        }
        int mid = (l + r) >> 1;
        build(pos << 1, l, mid);
        build(pos << 1 | 1, mid + 1, r);
        pushup(pos);
    }
} T;
struct Seg
{
    int l, r, op;
};
vector<Seg> g[N][2];
pii ans = mk(0, 0);
int l[N], r[N], v[N];
int main()
{
    int n = read();
    int mx = 0;
    for (int i = 1; i <= n; i++)
    {
        l[i] = read(), v[i] = read(), r[i] = read();
        g[l[i]][0].push_back((Seg){v[i], r[i], 1});
        g[v[i]][1].push_back((Seg){v[i], r[i], -1});
        mx = max(r[i], mx);
    }
    T.build(1, 1, mx);
    int ansy = 0;
    for (int i = 1; i < N; i++)
    {
        for (Seg now : g[i][0])
        {
            T.update(now.l, now.r, now.op, 1, 1, mx);
        }
        pii now = T.query(1, mx, 1, 1, mx);
        if (now.first > ans.first)
            ans = now, ansy = i;

        for (Seg now : g[i][1])
        {
            T.update(now.l, now.r, now.op, 1, 1, mx);
        }
    }
    printf("%d\n", ans.first);

    for (int i = 1; i <= n; i++)
        if (l[i] <= ansy && ansy <= v[i] && v[i] <= ans.second && ans.second <= r[i])
            printf("%d ", i);
    printf("\n");
}