P1502 窗口的星星

blank_space · 2020-12-13 20:09:46 · 个人记录

P1502 窗口的星星

题目：

给定每一颗星星的坐标 和 亮度 球用一个给定的矩形能框住的星星的最大亮度之和

思路：

1. 蒋点转化为矩形 扫描线

2. 数据过大 离散化

3. 注意给定边框的边界

code：

/*
  Time: 12.13
  Worker: Blank_space
  Source: P1502 窗口的星星
*/
/*--------------------------------------------*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
#define emm(x) memset(x, 0, sizeof x)
/*--------------------------------------头文件*/
const int A = 1e4 + 7;
const int B = 1e5 + 7;
const int C = 1e6 + 7;
const int D = 1e7 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int FFF = 0x8fffffff;
/*------------------------------------常量定义*/
int T, W, H, n, _a[A], _b[A], c[A << 1], ans;
struct node{
    int a, b, y, val;
    bool operator < (const node & x) const
    {
        return y == x.y ? val > x.val : y < x.y;
    }
}s[A << 2];
/*------------------------------------变量定义*/
inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
    return x * f;
}
/*----------------------------------------快读*/
namespace seg{
    #define ls(x) x << 1
    #define rs(x) x << 1 | 1
    struct nod {
        int l, r, mid, maxx, lzy;
    }t[A << 3];
    void f(int p, int k) {t[p].maxx += k; t[p].lzy += k;}
    void push_down(int p)
    {
        f(ls(p), t[p].lzy); f(rs(p), t[p].lzy); t[p].lzy = 0;
    }
    void build(int p, int l, int r)
    {
        t[p].l = l; t[p].r = r; t[p].mid = (l + r) >> 1;
        if(l == r) return ;
        build(ls(p), l, t[p].mid); build(rs(p), t[p].mid + 1, r);
    }
    void up_date(int p, int l, int r, int k)
    {
        if(l <= t[p].l && t[p].r <= r) {f(p, k); return ;}
        if(t[p].lzy) push_down(p);
        if(l <= t[p].mid) up_date(ls(p), l, r, k);
        if(r > t[p].mid) up_date(rs(p), l, r, k);
        t[p].maxx = std::max(t[ls(p)].maxx, t[rs(p)].maxx);
    }
}
void work()
{
    n = read(); W = read() - 1; H = read() - 1;
    emm(s); emm(seg::t); emm(c); ans = 0;
    for(int i = 1; i <= n; i++)
    {
        int x = read(), y = read(), z = read(), _i = i << 1;
        c[_i - 1] = y; c[_i] = y + H;
        s[_i - 1].a = y; s[_i - 1].b = y + H;
        s[_i - 1].y = x; s[_i - 1].val = z;
        s[_i].a = y; s[_i].b = y + H;
        s[_i].y = x + W; s[_i].val = -z;
    }
    n <<= 1;
    std::sort(c + 1, c + 1 + n);
    std::sort(s + 1, s + 1 + n);
    int cnt = std::unique(c + 1, c + 1 + n) - c - 1;
    seg::build(1, 1, cnt - 1);
    for(int i = 1; i <= n; i++)
    {
        int l = std::lower_bound(c + 1, c + 1 + cnt, s[i].a) - c - 1;
        int r = std::lower_bound(c + 1, c + 1 + cnt, s[i].b) - c - 1;
        seg::up_date(1, l, r, s[i].val);
        ans = std::max(ans, seg::t[1].maxx);
    }
    printf("%lld\n", ans);
    return ;
}
/*----------------------------------------函数*/
signed main()
{
    T = read();
    while(T--) work();
    return 0;
}