poj2482 Stars in Your Window线段树扫描线

im0use · 2023-03-07 20:10:14 · 个人记录

做法

直接模拟？O(N^2) 级别的时间复杂度。

一维情况

对于一维来说可以直接用线段树，或者单调栈。

二维情况

用线段树维护一个维度的最值，可以直到线段树只能去维护单点的区间最值，如何做，用一个点表示一个范围的和。我们维护线段树的 x 坐标，表示 (x-w,x] 的和，对于原本点的 x 维护 x,x+w，表示 x 的可加范围，然后线段树中存储有序的 x 值，当枚举到该点时，使用二分在可加区域上加权，对区间最值查询即可得到最大值。

对于 y 坐标，仍然可以使其有序，可知当 y 在考察范围时,y+h 就必须去掉，所以将 y+h 取亮度负值将原有的 y 抵消，注意要先抵消这种作用后才能干别的事情。

#include <cstdio>
#include <iostream>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <cctype>
#include <cmath>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <functional>

typedef long long i64;

template<class Info, class Tag>
struct LazySegmentTree {
    const int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LazySegmentTree(int n) : n(n), info(4 << std::__lg(n)), tag(4 << std::__lg(n)) {}
    LazySegmentTree(std::vector<Info> init) : LazySegmentTree(init.size()) {
        build(1, 0, n, init);
    }
    void build(int p, int l, int r, const std::vector<Info> &init) {
        if (r - l == 1) {
            info[p] = init[l];
            return;
        }
        int m = (l + r) / 2;
        build(2 * p, l, m, init);
        build(2 * p + 1, m, r, init);
        pull(p);
    };
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y || r <= x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 0, n, l, r, v);
    }
};

struct Tag {
    i64 x;
    Tag(i64 x = 0) : x(x) {};
    void apply(const Tag &t) {
        x += t.x;
    }
};

struct Max {
    i64 x;
    Max(i64 x = 0) : x(x) {}
    void apply(const Tag &t) {
        x += t.x;
    }
};

Max operator+(const Max &a, const Max &b) {
    return std::max(a.x, b.x);
}

struct X {
    i64 xl, xr, y;
    i64 c;
    X() : xl(0), xr(0), y(0), c(0) {}
    X(i64 xl, i64 xr, i64 y, i64 c) : xl(xl), xr(xr), y(y), c(c) {}
    bool operator<(const X &a) const {
        if (y != a.y) {
            return y < a.y;
        }
        return c < a.c;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    i64 n, w, h;
    while (std::cin >> n >> w >> h) {
        std::vector<X> a(2 * n);
        std::vector<i64> axisX(2 * n);
        for (int i = 0; i < n; i++) {
            i64 x, y, c;
            std::cin >> x >> y >> c;
            axisX[i] = x;
            axisX[i + n] = x + w;
            a[i] = X(x, x + w, y, c);
            a[i + n] = X(x, x + w, y + h, -c);
        }
        std::sort(a.begin(), a.end());
        std::sort(axisX.begin(), axisX.end());
        axisX.erase(std::unique(axisX.begin(), axisX.end()), axisX.end());
        LazySegmentTree<Max, Tag> tree(axisX.size());
        i64 max = 0;
        for (int i = 0; i < a.size(); i++) {
            int left = std::lower_bound(axisX.begin(), axisX.end(), a[i].xl) - axisX.begin();
            int right = std::lower_bound(axisX.begin(), axisX.end(), a[i].xr) - axisX.begin();
//            std::cout << a[i].xl << " " << a[i].xr << ", [" << left << " " << right << " ] " << a[i].c << "\n";
            tree.rangeApply(left, right, Tag(a[i].c));
            max = std::max(max, tree.info[1].x);
        }
        std::cout << max << "\n";
    }
    return 0;
}