Luobuyu's Blog

0%

P1502 窗口的星星

发表于 分类于 ， 热度： ℃ 评论：
本文字数： 3.5k 阅读时长 ≈ 3 分钟
扫描线经典题目，注意和亚特兰蒂斯面积并的区别。

P1502.窗口的星星

题目描述：

小卡买到了一套新房子，他十分的高兴，在房间里转来转去。

晚上，小卡从阳台望出去，“哇~~~~好多星星啊”，但他还没给其他房间设一个窗户。

天真的小卡总是希望能够在晚上能看到最多最亮的星星，但是窗子的大小是固定的，边也必须和地面平行。

这时小卡使用了超能力（透视术）知道了墙后面每个星星的位置和亮度，但是小卡发动超能力后就很疲劳，只好拜托你告诉他最多能够有总和多亮的星星能出现在窗口上。

输入格式

本题有多组数据，第一行为 $T$ ，表示有 $T$ 组数据。

对于每组数据：

第一行 $3$ 个整数 $n,w,h$ 表示有 $n$ 颗星星，窗口宽为 $w$ ，高为 $h$ 。

接下来 $n$ 行，每行三个整数 $x_i,y_i,l_i$ 表示星星的坐标在 $(x_i, y_i)$ ，亮度为 $l_i$ 。

输出格式

$T$ 个整数，表示每组数据中窗口星星亮度总和的最大值。

数据范围：

$1\le T \le 10, 1\le n \le 10^4, 1\le W,H \le 10^6, 0\le x_i,y_i \le 2^{31}$

为了便于理解，输入样例中每组数据之间添加了空行，实际测试数据中并无空行。

小卡买的窗户框是金属做的，所以在边框上的不算在内。

题解：

每个矩形的左下角为 $x_i,y_i$ ，当窗口的右上角坐标 $x, y$ 在 $x_i \le x \le x_i + w - 1, y_i \le y \le y_i + h - 1$ 时可以看到星星 $x_i,y_i$ 。也就是窗口的右上角坐标在这个矩形范围内，则可以覆盖星星。可以查询矩形交集的最大值。因为在边框上的不算，因此可以对矩形范围缩小 $0.5$ ，就得到了上面的矩形。

而且要注意和面积并的区别，面积并权值都在线段上，对于一个线段 $y_1, y_2$ ，需要在线段树中维护 $y_1, y_2-1$ 。而这个题目权值在坐标点上，可以直接对区间 $y_1, y_2$ 修改，不用再减一了。

代码：

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
134
135
using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e4 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int w, h;
// [xi, yi, xi + w - 1, yi + h - 1]
struct Line
{
    int x, y1, y2, l;
    bool operator<(const Line &p) const
    {
        return x == p.x ? l > p.l : x < p.x;
    }
} line[maxn << 1];
int yy[maxn << 1];
struct SegTree
{
    struct TreeNode
    {
        int l, r;
        ll lazy, sum;
        void init(int _l, int _r)
        {
            l = _l, r = _r;
            lazy = sum = 0;
        }
        int len()
        {
            return r - l + 1;
        }
        int mid()
        {
            return (r + l) >> 1;
        }
    };
    vector<TreeNode> tree;
    SegTree(int n) : tree(n << 2) {}
    void build(int cur, int l, int r)
    {
        tree[cur].init(l, r);
        if (l == r)
            return;
        int mid = tree[cur].mid();
        build(cur << 1, l, mid);
        build(cur << 1 | 1, mid + 1, r);
        tree[cur].sum = max(tree[cur << 1].sum, tree[cur << 1 | 1].sum);
    }
    void pushdown(int cur)
    {
        tree[cur << 1].lazy += tree[cur].lazy;
        tree[cur << 1].sum += tree[cur].lazy;
        tree[cur << 1 | 1].lazy += tree[cur].lazy;
        tree[cur << 1 | 1].sum += tree[cur].lazy;
        tree[cur].lazy = 0;
    }
    void update(int cur, int l, int r, int k)
    {
        if (l <= tree[cur].l && tree[cur].r <= r)
        {
            tree[cur].sum += k;
            tree[cur].lazy += k;
            return;
        }
        if (tree[cur].lazy)
            pushdown(cur);
        int mid = tree[cur].mid();
        if (l <= mid)
            update(cur << 1, l, r, k);
        if (mid + 1 <= r)
            update(cur << 1 | 1, l, r, k);
        tree[cur].sum = max(tree[cur << 1].sum, tree[cur << 1 | 1].sum);
    }
    ll query(int cur, int l, int r)
    {
        if (l <= tree[cur].l && tree[cur].r <= r)
        {
            return tree[cur].sum;
        }
        if (tree[cur].lazy)
            pushdown(cur);
        int mid = tree[cur].mid();
        ll maxx = 0;
        if (l <= mid)
            maxx = max(maxx, query(cur << 1, l, r));
        if (mid + 1 <= r)
            maxx = max(maxx, query(cur << 1 | 1, l, r));
        return maxx;
    }
};
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tcase;
    read(tcase);
    while (tcase--)
    {
        read(n, w, h);
        int x1, y1, x2, y2, l;
        for (int i = 1; i <= n; ++i)
        {
            read(x1, y1, l);
            x2 = x1 + w - 1, y2 = y1 + h - 1;
            line[i * 2 - 1] = {x1, y1, y2, l};
            line[i * 2] = {x2, y1, y2, -l};
            yy[i * 2 - 1] = y1;
            yy[i * 2] = y2;
        }
        n <<= 1;
        sort(line + 1, line + 1 + n);
        sort(yy + 1, yy + 1 + n);
        int tot = unique(yy + 1, yy + 1 + n) - yy - 1;
        SegTree segTree(tot);
        segTree.build(1, 1, tot);
        ll maxx = 0;
        for (int i = 1; i <= n; ++i)
        {
            int y1 = lower_bound(yy + 1, yy + 1 + tot, line[i].y1) - yy;
            int y2 = lower_bound(yy + 1, yy + 1 + tot, line[i].y2) - yy;
            segTree.update(1, y1, y2, line[i].l);
            maxx = max(maxx, segTree.query(1, 1, tot));
        }
        cout << maxx << endl;
    }
    return 0;
}