[2019.12.26] JOI spring camp 2018/2019 Day 2

https://oj.uz/problems/source/377

1. Two Antennas (두 안테나)

극한의 스위핑 문제... 우선 쿼리에 변화가 없으므로 오프라인으로 쿼리를 처리해야겠다는 생각을 할 수 있다. R이 증가하는 순서대로 쿼리를 정렬하자.

 

통신을 할 수 있는 조건은 1 <= i < j <= n에 대해 i+A[i] <= j <= i+B[i]이고 j-B[j] <= i <= j-A[j]인 경우이다. 이 때 우선은 H[j] > H[i]라 가정한다면 우리가 구하는 답은 조건을 만족하는 모든 i, j 쌍에 대하여 max(H[j]-H[i])이다. H[i] >H[j]인 경우는 모든 H의 부호를 바꿔 생각하면 된다.

 

1번부터 n번까지 순차적으로 업데이트한다 생각하면, j번째 안테나가 영향을 끼치는 범위는 j-B[j]~j-A[j]라는 것을 알 수 있다. 이 구간의 원소 i에 대해 만약 i+A[i] <= j <= i+B[i]라면 서로 통신이 가능하므로, 조건을 만족하는 쌍을 이렇게 스위핑을 이용해 순차적으로 구할 수 있다는 것을 알 수 있다. 이를 통해 답도 구할 수 있다.

 

이 과정을 그대로 수행하면 O(n^2)이기 때문에 이를 줄이려는 생각을 해야 한다. 우선 ans[i]를 i번째 원소가 j > i인 안테나와 통신했을 때의 최댓값이라 하자. 그러면 우선 쿼리의 답은 max(ans[i]) for L <= i <= R이다. 때문에 이를 Segment Tree를 이용하여 관리해야 함을 알 수 있다. 오른쪽에 안테나가 추가될 때마다 ans가 업데이트되기 때문이다.

 

이제 이 업데이트 쿼리를 어떻게 진행해야 할 지 생각해보자. 우선 구간 쿼리이므로 Lazy Propagation을 써야 할 텐데, 어떻게 써야 할 지 감이 잘 오지 않는다. j번째 안테나를 업데이트할 구간이 [L, R]이라 히고, 우선 그 구간 내의 모든 안테나와 j번째 안테나가 통신이 가능하다 가정하자. L <= s, e <= R인 구간 [s, e]에 대해 답은 H[j] - (min(H[i]) for s <= i <= e)로 바뀐다. 즉, 세그먼트 트리로 구간에서 H의 최솟값을 가지고 있다면 Lazy Propagation을 통해서 구간 업데이트를 log 시간만에 처리할 수 있다. 이 때 tree[node]에는 해당 노드가 의미하는 구간에서 H[i]의 최솟값과 ans[i]의 최댓값을 가지고 있어야 하고, lazy[node]에는 그 구간에 적용된 가장 큰 H[j]를 가지고 있어야 한다. 당연히 처음에 H[i]의 최솟값은 ∞, ans[i]의 최댓값은 -1, lazy[node]는 -∞로 초기화해줘야 한다.

 

그렇다면 [L, R] 구간에서 j와 통신이 불가능한 원소는 어떻게 고려해야 할까? 우리는 현재 1번부터 순서대로 업데이트하고 있다. 때문에 i+A[i] <= j <= i+B[i]일 때만 세그먼트 트리에 H[i]를 적용시키고, 그렇지 않을 때는 ∞라고 생각하면 된다. 즉 j = i+A[i]가 된 순간에 H[i]를 적용시키고, j > i+B[i]가 된 순간에 H[i]를 다시 ∞로 생각하면 된다.

 

이제 R이 증가하는 순서대로 정렬된 쿼리를 하나씩 처리하면 된다. R까지 i번째 안테나가 적용되는 범위에서 업데이트해주고, j번째 원소가 추가될 때 구간 업데이트를 잘 처리해주면 각 쿼리에 대한 답을 구할 수 있다. (H[i] < H[j]인 경우에 대해) i번째 안테나가 적용되는 범위는 벡터를 이용해 시작점과 끝점에서 업데이트해줘도 되고, 나처럼 우선순위 큐 등을 이용할 수도 있다. (벡터로 미리 저장하는 것이 더 좋은 것 같다.) H[i] = -H[i]로 바꿔준 뒤 한 번 더 실행하면 실제 답을 구할 수 있다.

 

풀이를 생각한 후에는 금방 짠 것 같은데, Lazy Propagation에서 적용을 시킨 뒤에는 Lazy 값을 -∞로 다시 해주는 행위를 하지 않아 i번째 안테나가 고려되지 않아야 하는 구간에서 고려되는 대참사를 일으키고 말았다. 이를 디버깅하는데 무려 2시간을 날렸다...

 

코드

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()
#define my_assert cout << "!" << endl;

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 101010;
const int INF = (1 << 30) - 1;
const ll LINF = 1LL << 60;

struct antena {
    int h, a, b;
} arr[2*MAX];

struct SEG {
    vector <pll> tree;
    vector <ll> lazy;

    SEG(int n) {
        tree.resize(4*n+10);
        lazy.resize(4*n+10);
        for(int i = 1; i < tree.size(); i++) {
            tree[i].fi = -1;
            tree[i].se = LINF;
            lazy[i] = -LINF;
        }
    }

    void update_lazy(int node, int s, int e) {
        tree[node].fi = max(tree[node].fi, lazy[node] - tree[node].se);
        if(s != e) {
            lazy[node*2] = max(lazy[node*2], lazy[node]);
            lazy[node*2+1] = max(lazy[node*2+1], lazy[node]);
        }
        lazy[node] = -LINF;
    }

    void update1(int node, int s, int e, int l, int r, int val) {
        if(l > r) return;
        update_lazy(node, s, e);
        if(s > r || e < l) return;
        if(s >= l && e <= r) {
            lazy[node] = max(lazy[node], (ll)val);
            update_lazy(node, s, e);
            return;
        }
        int m = (s + e) / 2;
        update1(node*2, s, m, l, r, val), update1(node*2+1, m+1, e, l, r, val);
        tree[node].fi = max(tree[node*2].fi, tree[node*2+1].fi);
    }

    void update2(int node, int s, int e, int k, bool flag) {
        update_lazy(node, s, e);
        if(s == e) {
            if(flag) tree[node].se = arr[k].h;
            else tree[node].se = LINF;
            return;
        }
        int m = (s + e) / 2;
        if(k <= m) update2(node*2, s, m, k, flag);
        else update2(node*2+1, m+1, e, k, flag);
        tree[node].se = min(tree[node*2].se, tree[node*2+1].se);
    }

    int cal(int node, int s, int e, int l, int r) {
        update_lazy(node, s, e);
        if(s > r || e < l) return -1;
        if(s >= l && e <= r) return tree[node].fi;
        int m = (s + e) / 2;
        return max(cal(node*2, s, m, l, r), cal(node*2+1, m+1, e, l, r));
    }
};

struct Query {
    int l, r, idx;
} Q[2*MAX];
int ans[2*MAX], n, q;

void solve() {
    SEG st(n);
    int idx = 0;
    priority_queue <pii, vector <pii>, greater <pii> > pq1, pq2;
    for(int i = 1; i <= q; i++) {
        while(idx < Q[i].r) {
            while(!pq2.empty() && pq2.top().fi == idx) {
                st.update2(1, 1, n, pq2.top().se, false);
                pq2.pop();
            }
            idx++;
            while(!pq1.empty() && pq1.top().fi == idx) {
                st.update2(1, 1, n, pq1.top().se, true);
                pq1.pop();
            }
            st.update1(1, 1, n, max(1, idx - arr[idx].b), max(0, idx - arr[idx].a), arr[idx].h);
            pq1.em(idx + arr[idx].a, idx);
            pq2.em(idx + arr[idx].b, idx);
        }
        ans[Q[i].idx] = max(ans[Q[i].idx], st.cal(1, 1, n, Q[i].l, Q[i].r));
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i].h >> arr[i].a >> arr[i].b;
    }
    cin >> q;
    for(int i = 1; i <= q; i++) {
        cin >> Q[i].l >> Q[i].r;
        Q[i].idx = i;
        ans[i] = -1;
    }
    sort(Q+1, Q+q+1, [](Query a, Query b) {
        return a.r < b.r;
    });
    solve();
    for(int i = 1; i <= n; i++) {
        arr[i].h = - arr[i].h;
    }
    solve();
    for(int i = 1; i <= q; i++) {
        cout << ans[i] << '\n';
    }
}

 

2. Two Dishes (두 요리)

n<=3000, m<=3000이라 생각하면 dp[i][j] = max(dp[i-1][j] + f(i, j), dp[i][j-1] + g(i, j)) 로 생각할 수 있다. 이 때 f(i, j)은 1번 요리를 i-1번째까지 만들고 2번 요리를 j번째까지 만들었을 때 1번 요리의 i번째 요리를 만들면 점수를 얻을 수 있을 때 그 점수, 아닌 경우 0을 의미하는 것이고 g(i, j)도 비슷하게 1번 요리를 i번째까지 만들고 2번 요리를 j-1번째까지 만들었을 때 2번 요리의 j번째 요리를 만들면 점수를 얻을 수 있을 때 그 점수, 아닌 경우 0을 의미한다. 이 이후에는 도저히 방법을 모르겠어서 공식 홈페이지의 풀이 PPT를 열어보았으나 무슨 말인지를 모르겠다... 위의 아이디어를 응용하는 것이 맞고, DP Table의 업데이트 횟수가 적은 것을 이용하는 것으로 보이나, 결국 풀지 못했다.

 

+수정

codeforces 댓글에 풀이가 있더라.. X[i]를 1번 요리의 i번째 점수를 획득할 수 있도록 하는 2번 요리 최대 개수 (즉, f(i, j)가 P[i]가 되도록 하는 최대 j), 비슷한 방식으로 Y[j]는 2번 요리의 j번째 점수를 획득할 수 있도록 하는 1번 요리의 최대 개수라 하고 (i, X[i]), (Y[j], j)에 점을 찍어보자. 이 때 점수 가중치도 고려한다. (0, 0) --> (n, m)인 경로에서 경로를 포함한 위쪽 영역의 (i, X[i]) 점수 합과 경로를 포함한 아래쪽 영역의 (Y[j], j) 점수 합의 최대를 찾으면 된다. 근데 여기서 (Y[j], j)를 (Y[j]+1, j-1)꼴로 바꾸면 (i, X[i])와 같은 종류의 점으로 보고 가중치를 음수로 하면 된다. (그러니까, 선택하는 점수에서 선택하지 않는 점수로 바꾸는 것) 이 때 이러한 점들의 가중치는 미리 더해 둔다. 이제 이 문제를 세그먼트 트리로 푸는데, Lazy Propagation이 필요 없다고 한다? 나는 어떻게 해야 할 지 몰라서 Lazy를 썼고, oj.uz에선 맞았으나 백준에선 TLE....

 

2024.02.14 수정) 기억이 안 나지만 lazy 쓰고도 백준에서 맞았던 것 같다(?)

 

코드

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()
#define my_assert cout << "!" << endl;

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 1110101;
const int INF = (1 << 30) - 1;
const ll LINF = 1LL << 60;

int n, m;
ll A[MAX], S[MAX], P[MAX];
ll B[MAX], T[MAX], Q[MAX];
ll sumA[MAX], sumB[MAX], ans;
ll tree[8*MAX], lazy1[8*MAX];
int lazy2[8*MAX];

inline void update_lazy(int node, int s, int e) {
    tree[node] = tree[node] * lazy2[node] + lazy1[node];
    if(s != e) {
        if(lazy2[node] == 1) {
            lazy1[node*2] += lazy1[node];
            lazy1[node*2+1] += lazy1[node];
        }
        else {
            lazy1[node*2] = lazy1[node], lazy2[node*2] = 0;
            lazy1[node*2+1] = lazy1[node], lazy2[node*2+1] = 0;
        }
    }
    lazy1[node] = 0;
    lazy2[node] = 1;
}

inline void update1(int node, int s, int e, int r, ll val) {
    update_lazy(node, s, e);
    if(s > r) return;
    if(e <= r) {
        lazy1[node] += val;
        update_lazy(node, s, e);
        return;
    }
    int mi = (s + e) / 2;
    update1(node*2, s, mi, r, val);
    update1(node*2+1, mi+1, e, r, val);
    tree[node] = max(tree[node*2], tree[node*2+1]);
}

inline void update2(int node, int s, int e, int l, int r, ll a, ll b) {
    update_lazy(node, s, e);
    if(s > r || e < l) return;
    if(s >= l && e <= r) {
        lazy2[node] = a;
        lazy1[node] = b;
        update_lazy(node, s, e);
        return;
    }
    int mi = (s + e) / 2;
    update2(node*2, s, mi, l, r, a, b);
    update2(node*2+1, mi+1, e, l, r, a, b);
    tree[node] = max(tree[node*2], tree[node*2+1]);
}

inline ll cal(int node, int s, int e, int l, int r) {
    update_lazy(node, s, e);
    if(s > r || e < l) return -LINF;
    if(s >= l && e <= r) return tree[node];
    int mi = (s + e) / 2;
    return max(cal(node*2, s, mi, l, r), cal(node*2+1, mi+1, e, l, r));
}

inline int get(int node, int s, int e, ll val) {
    update_lazy(node, s, e);
    if(s == e) return s;
    update_lazy(node*2, s, e);
    if(tree[node*2] > val) return get(node*2, s, (s+e)/2, val);
    else return get(node*2+1, (s+e)/2+1, e, val);
}

struct point {
    int x, y; ll val;
    point(int x, int y, ll val) : x(x), y(y), val(val) {}
};
vector <point> po;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    for(int i = 1; i < 4 * MAX; i++) lazy2[i] = 1;

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> A[i] >> S[i] >> P[i];
        sumA[i] = sumA[i-1] + A[i];
    }
    for(int i = 1; i <= m; i++) {
        cin >> B[i] >> T[i] >> Q[i];
        sumB[i] = sumB[i-1] + B[i];
        ans += Q[i];
    }
    for(int i = 1; i <= n; i++) {
        int temp = upper_bound(sumB, sumB+m+1, S[i] - sumA[i]) - sumB - 1;
        if(temp >= 0) po.eb(i, temp, P[i]);
    }
    for(int i = 1; i <= m; i++) {
        int temp = upper_bound(sumA, sumA+n+1, T[i] - sumB[i]) - sumA - 1;
        if(temp < 0) ans -= Q[i];
        else if(temp < n) po.eb(temp+1, i-1, -Q[i]);
    }
    sort(all(po), [](point a, point b) {
        if(a.x == b.x) return a.y > b.y;
        return a.x < b.x;
    });

    ll rem = 0;
    for(int i = 0; i < po.size(); i++) {
        if(i+1 < po.size() && po[i].x == po[i+1].x && po[i].y == po[i+1].y) {
            rem += po[i].val;
            continue;
        }
        update1(1, 0, m, po[i].y, po[i].val + rem);
        ll temp = cal(1, 0, m, 0, po[i].y);
        int idx = m + 1;
        if(cal(1, 0, m, 0, m) > temp) idx = get(1, 0, m, temp);
        update2(1, 0, m, po[i].y+1, idx - 1, 0, temp);
        rem = 0;
    }
    cout << cal(1, 0, m, m, m) + ans;
}

 

3. 볼 수 없어 못 풀었다.