扫描线+线段树#4#5WA求救

回复帖子

@nwjxjrs 2021-03-25 23:58 回复
#include<iostream>
#include<algorithm>
#define MAXN 10000+5
using namespace std;
struct node1
{
    long long x1, x2, y;
    long long l;
}a[2 * MAXN];
struct node2
{
    int left, right;
    long long max;
    long long tag;
}tree[16 * MAXN];//16?
long long qx[2 * MAXN] = { 0 };
bool cmp(node1 a, node1 b)
{
    if (a.y == b.y)
        return a.l > b.l;
    return a.y < b.y;
}
void build(int o, int start, int end)
{
    tree[o].left = start, tree[o].right = end;
    tree[o].max = tree[o].tag = 0;
    if (start == end)
        return;
    int mid = (start + end) / 2;
    build(o * 2, start, mid);
    build(o * 2 + 1, mid + 1, end);
}
void spread(int o)
{
    if (tree[o].left != tree[o].right)
    {
        tree[o * 2].tag += tree[o].tag;
        tree[o * 2 + 1].tag += tree[o].tag;
        tree[o * 2].max += tree[o].tag;
        tree[o * 2 + 1].max += tree[o].tag;
        tree[o].tag = 0;
    }
}
void add(int o, long long int start, long long int end, long long val)
{
    if (tree[o].left == 0 && tree[o].right == 0)
        return;
    if (start > qx[tree[o].right + 1] || end < qx[tree[o].left])
        return;
    if (start <= qx[tree[o].left] && end >= qx[tree[o].right + 1])
    {
        tree[o].tag += val;
        tree[o].max += val;
        return;
    }
    spread(o);
    int mid = (tree[o].left + tree[o].right) / 2;
    add(o * 2, start, end, val);
    add(o * 2 + 1, start, end, val);
    tree[o].max = max(tree[o * 2].max, tree[o * 2 + 1].max);
}
int main(void)
{
    int T;
    cin >> T;
    while (T--)
    {
        int n, w, h;
        cin >> n >> w >> h;
        for (int i = 1; i <= n; i++)
        {
            long long x, y, l;
            cin >> x >> y >> l;
            a[i] = { x,x + w - 1,y,l };
            a[i + n] = { x,x + w - 1,y + h - 1,-l };
            qx[i] = x;
            qx[i + n] = x + w - 1;
        }
        sort(qx + 1, qx + 1 + 2 * n);
        sort(a + 1, a + 1 + 2 * n, cmp);
        int top = 2 * n;
        build(1, 1, top - 1);
        long long ans = 0;
        for (int i = 1; i <= 2 * n; i++)
        {
            add(1, a[i].x1, a[i].x2, a[i].l);
            ans = max(ans, tree[1].max);
        }
        cout << ans << endl;
    }
    return 0;
}
@nwjxjrs 2021-03-26 00:01 回复 举报

我的离散化方式可能有些奇怪,但是应该没有问题,扫描线模板题我这么离散化就过了


反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。