2019 HDU 다 교 6 차 1005. Snowy Smile (선분 트 리 유지보수 서브 세그먼트 와)

몇 개의 대역 권 점 을 주 고 임의의 크기 의 사각형 을 잃 어 버 리 고 상자 기둥 에 점 을 내 려 가면 최대 몇 개의 가중치 를 얻 을 수 있 는 지 물 어보 세 요.
문 제 를 보충 하 다.
n 총 화 는 1e4 보다 적 고 4 초 를 주 었 으 며 대체적으로 n 자 log 의 알고리즘 입 니 다.
매 거 진 행렬 의 상하 (또는 좌우) 두 경계, 나머지 두 변 은 반드시 매 거 져 야 하 는 것 이 아니 라 하나의 선분 트 리 로 최대 부분 을 유지 하고 직접 해결 할 수 있 습 니 다.
판자 + 1?

#include

using namespace std;

typedef long long ll;
const int maxn = 2e3 + 5;

struct node {
    int x, y;
    ll w;
} p[maxn];

int _, n;

vector<int> G[maxn];
vector<int> X, Y;

struct segmentTree {
    // -ai(ls) + aj(rs) ←   (i < j)
    ll s[maxn << 2], ls[maxn << 2], rs[maxn << 2], lrs[maxn << 2];

    void pushUp(int rt) {
        s[rt] = s[rt << 1] + s[rt << 1 | 1];
        ls[rt] = max(ls[rt << 1], s[rt << 1] + ls[rt << 1 | 1]);
        rs[rt] = max(rs[rt << 1 | 1], s[rt << 1 | 1] + rs[rt << 1]);
        lrs[rt] = max(max(lrs[rt << 1], lrs[rt << 1 | 1]), rs[rt << 1] + ls[rt << 1 | 1]);
    }

    void build(int rt, int l, int r) {
        s[rt] = ls[rt] = rs[rt] = lrs[rt] = 0;
        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        build(rt << 1, l, mid);
        build(rt << 1 | 1, mid + 1, r);
    }

    void update(int rt, int l, int r, int pos, ll val) {
        if (l == r) {
            s[rt] += val;
            ls[rt] = rs[rt] = lrs[rt] = max(0LL, s[rt]);
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) {
            update(rt << 1, l, mid, pos, val);
        } else {
            update(rt << 1 | 1, mid + 1, r, pos, val);
        }
        pushUp(rt);
    }

    void solve() {
        ll ans = 0;
        for (int i = 1; i <= X.size(); ++i) {
            build(1, 1, Y.size());
            for (int j = i; j <= X.size(); ++j) {
                for (auto e : G[j]) {
                    update(1, 1, Y.size(), p[e].y, p[e].w);
                }
                ans = max(ans, lrs[1]);
            }
        }
        printf("%lld
", ans);
    }
} st;

int main() {
    scanf("%d", &_);
    while (_--) {
        scanf("%d", &n);
        X.clear(), Y.clear();
//        X.push_back(INT_MIN), Y.push_back(INT_MIN);
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d%lld", &p[i].x, &p[i].y, &p[i].w);
            X.push_back(p[i].x);
            Y.push_back(p[i].y);
        }
        sort(X.begin(), X.end());
        X.erase(unique(X.begin(), X.end()), X.end());
        sort(Y.begin(), Y.end());
        Y.erase(unique(Y.begin(), Y.end()), Y.end());

        for (int i = 0; i <= X.size(); ++i) {
            G[i].clear();
        }

        for (int i = 1; i <= n; ++i) {
            p[i].x = lower_bound(X.begin(), X.end(), p[i].x) - X.begin() + 1;
            p[i].y = lower_bound(Y.begin(), Y.end(), p[i].y) - Y.begin() + 1;
            G[p[i].x].push_back(i);
        }

        st.solve();
    }
    return 0;
}