BOJ)10167 금광

문제: icpc.me/10167

직사각형 모양의 영역으로 금광을 개발 할 때 얻을 수 있는 최대 이익을 구하는 문제이다.

문제를 푸는데 상당히 고생했는데 KOI 2014 중등부 문제인걸 보고 어이가없어서 웃음만 나왔다... 

일단 N이 3000이므로 N^2혹은 N^2logN 알고리즘을 사용해야 하는데 

처음 생각한것은 x축기준으로 스위핑 하여 y축을 세그먼트 트리 구간합에 업데이트 시키는 작업을 순서대로 하는데

이 때 이 작업은 전단계의 점들을 반드시 포함하게 되므로 모든점에 대해서 이 작업을 반복하는 것이다.

이 때 처음에는 최대 구간합을 구하기 위해서 이미 업데이트 된 모든 점이랑 비교하여 구간합의 최댓값을 구했는데

이렇게 할 경우 한점에서 업데이트한 후 구간합의 최댓값을 구하는데 O(NlogN) 여기에 전부 업데이트 할 시 O(N^2logN) 

하지만 우리는 모든 점에 대해서 x좌표가 커지는 쪽으로 업데이트 해야하므로 O(N^3logN)이 사용된다.

n개의 점에 대해서 x좌표가 커지는 쪽으로 n만큼 업데이트 시켜야 하는건 복잡도를 줄일 수 없으므로 한점을 갱신 한 뒤 

구간의 최댓값을 구하는걸 O(NlogN)에서 O(logN)으로 줄여야 한다.

이걸 고민하다가 kks227님의 블로그를 보고 알게 되었는데 

분할정복으로 구할 수 있었다.

한 구간에서 

LSUM ->그 구간의 왼쪽 끝에서부터의 연속한 원소의 최대 합

RSUM ->그 구간의 오른쪽 끝에서부터의 연속한 원소의 최대 합

TOTALSUM ->그 구간의 모든 원소의 합

MAXSUM-> 그 구간에서 나올 수 있는 최대 연속합 

이라 정의할 때 

LSUM=max(왼쪽자식의LSUM, 왼쪽자식의TOTALSUM+오른쪽 자식의 LSUM)

RSUM=max(오른쪽자식의RSUM, 오른쪽자식의TOTALSUM+왼쪽 자식의RSUM)

TOTALSUM=왼쪽자식의TOTALSUM+오른쪽자식의TOTALSUM

MAXSUM=max(왼쪽자식의RSUM+오른쪽자식의LSUM, 왼쪽자식의MAXSUM, 오른쪽자식의 MAXSUM, LSUM, RSUM)

이란 수식을 얻을수 있어

우리는 갱신과 MAXSUM계산을 세그먼트 트리를 이용하여 O(logN)에 처리할 수 있다.

참고로 업데이트 하는 y좌표는 좌표압축을 이용하여 처리해주면 된다. 그리고 답은 long long 범위이다.

+추가)주의 할 점은 좌표를 볼 때 x좌표가 같은 점들은 반드시 한번에 업데이트 한 후 봐야 한다. 

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define MAX_N 3000
using namespace std;
typedef long long ll;
ll n, x, y, z, res;
vector<ll> ypos;
ll max(ll a, ll b, ll c, ll d,ll e) {
    return max(max(a, b), max(c, max(d, e)));
}
struct element {
    ll x, y, z;
    bool operator<(const element &A)const {
        return x < A.x;
    }
};
struct mseg {    //왼쪽 끝부터 최대 연속 합,오른쪽 끝부터 최대 연속 합,구간 합, 구간의 최대 연속 합
    ll lsum, rsum, tsum, msum;
};
mseg seg[4 * MAX_N];
element ele[MAX_N];
ll get_ypos(ll pos) {
    return lower_bound(ypos.begin(), ypos.end(), pos) - ypos.begin();
}
void update(ll pos, ll val, ll node, ll x, ll y) {
    if (y < pos || pos < x)
        return;
    if (x == y) {
        seg[node].tsum += val;
        seg[node].lsum += val;
        seg[node].rsum += val;
        seg[node].msum += val;
        return;
    }
    ll mid = (x + y) >> 1;
    update(pos, val, node * 2, x, mid);
    update(pos, val, node * 2 + 1, mid + 1, y);
    seg[node].lsum = max(seg[node * 2].lsum, seg[node * 2].tsum + seg[node * 2 + 1].lsum);
    seg[node].rsum = max(seg[node * 2 + 1].rsum, seg[node * 2 + 1].tsum + seg[node * 2].rsum);
    seg[node].tsum = seg[node * 2].tsum + seg[node * 2 + 1].tsum;
    seg[node].msum = max(seg[node * 2].rsum + seg[node * 2 + 1].lsum, seg[node * 2].msum, seg[node * 2 + 1].msum, seg[node].lsum, seg[node].rsum);
}
ll query(ll lo, ll hi, ll node, ll x, ll y) {
    if (y < lo || hi < x)
        return 0;
    if (lo <= x&&y <= hi)
        return seg[node].msum;
    ll mid = (x + y) >> 1;
    return max(query(lo, hi, node * 2, x, mid), query(lo, hi, node * 2 + 1, mid + 1, y));
}
int main() {
    scanf("%lld", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lld%lld%lld", &x, &y, &z);
        ele[i] = { x,y,z };
        ypos.push_back(y);
    }
    sort(ele, ele + n);
    sort(ypos.begin(), ypos.end());
    ypos.erase(unique(ypos.begin(), ypos.end()), ypos.end());
    const ll MAX_Y = ypos.size();
    for (int i = 0; i < n; i++) {
        memset(seg, 0, sizeof(seg));
        if (i&&ele[i].x == ele[i - 1].x)
            continue;
        for (int j = i; j < n; j++) {
            ll pos = get_ypos(ele[j].y);
            update(pos, ele[j].z, 1, 0, MAX_Y - 1);
            if (j != n - 1 && ele[j].x == ele[j + 1].x)
                continue;
            ll q = query(0, MAX_Y - 1, 1, 0, MAX_Y - 1);
            res = max(q, res);
        }
    }
    printf("%lld\n", res);
    return 0;
}