코드 복사/붙여넣기 하는 당신이 아름답습니다.

10167: 금광

풀이

이 문제와 비슷하게 분할정복으로 접근한다.

x축을 기준으로 정렬해서, 모든 [l, r] 구간에서 최댓값을 하나씩 찾을 것이다.

시작점을 하나 정해놓고, 끝점까지 스위핑 하면서 최댓값을 찾아 주자.

스위핑이 하나 전진할 때마다 분할정복 트리를 업데이트 해 주면 된다.

이러한 구간이 많아야 3000^2개이므로 여기에 로그 붙여도 충분하다.

세그트리 업데이트 하는 느낌으로 분할정복을 하면 된다.

나는 멍청하게 구간합 업데이트를 펜윅트리 써서 했는데 여러분들은 그러지 말자. ㅋㅋㅋㅋ

까다로운 반례가 있으므로 주의하자.

코드

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const ll INF = 1e14;
const int MAXN = (1<<12);

int n;
struct abc {
    int x, y; ll w;
    bool operator <(abc &a)const {
        if (x == a.x) return y < a.y;
        return x < a.x;
    }
} a[MAXN+5];

ll t[MAXN+5];
struct node {
    int s, e;
    ll mmax, lmax, rmax;
} tree[MAXN*4+5];

void t_udpate(int i, ll x) { // point update
    for (; i<=n; i+=i&-i) t[i]+=x;
}

ll t_query(int s, int e) { // range sum [s, e]
    ll r1 = 0, r2 = 0;
    for (; e; e-=e&-e) r1+=t[e];
    for (--s; s; s-=s&-s) r2+=t[s];
    return r1-r2;
}

void update(int now) {
    int idx = a[now].y+MAXN-1;
    t_udpate(a[now].y, a[now].w);
    ll tmp = (tree[idx].mmax == -INF ? INF+a[now].w : a[now].w);
    tree[idx].mmax += tmp;
    tree[idx].lmax += tmp;
    tree[idx].rmax += tmp;
    idx /= 2;
    while (idx) {
        auto &l = tree[idx*2], &r = tree[idx*2+1], &m = tree[idx];
        m.mmax = max({ l.mmax, r.mmax, l.lmax+r.rmax });
        m.lmax = max(r.lmax, l.lmax+t_query(r.s, r.e));
        m.rmax = max(l.rmax, r.rmax+t_query(l.s, l.e));
        idx /= 2;
    }
}

int main() {
    scanf("%d", &n);
    vector<int> vx, vy;
    for (int i = 1; i <= n; i++) {
        scanf("%d %d %lld", &a[i].x, &a[i].y, &a[i].w);
        vx.push_back(a[i].x); vy.push_back(a[i].y);
    }
    sort(vx.begin(), vx.end());
    sort(vy.begin(), vy.end());
    for (int i = 1; i <= n; i++) {
        a[i].x = lower_bound(vx.begin(), vx.end(), a[i].x)-vx.begin()+1;
        a[i].y = lower_bound(vy.begin(), vy.end(), a[i].y)-vy.begin()+1;
    }
    sort(a+1, a+1+n);
    tree[1].s = 1, tree[1].e = MAXN;
    for (int i = 2; i <= MAXN*4; i++) {
        int s = tree[i/2].s, e = tree[i/2].e;
        if (i%2) s = (s+e)/2+1;
        else e = (s+e)/2;
        tree[i] = { s,e,-INF,-INF,-INF };
    }

    ll dap = -INF;
    int chk[3333] = {};
    for (int i = 1; i <= n; i++) {
        if (a[i-1].x != a[i].x) chk[i] = 1;
    }
    for (int i = 1; i <= n; i++) {
        if (!chk[i]) continue;
        ll cur = -INF;
        for (int j = i; j <= n; j++) {
            update(j);
            if (chk[j+1] || j == n) cur = max(cur, tree[1].mmax);
        }
        dap = max(dap, cur);
        for (int i = 1; i <= MAXN*2; i++) {
            tree[i].mmax = tree[i].lmax = tree[i].rmax = -INF;
            if (i <= MAXN) t[i] = 0;
        }
    }

    printf("%lld\n", dap);

    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2019-08-30 14:49

Read more posts by this author