백준 17671번 두 안테나

문제 링크

참고 문헌

풀이 검색해서 풀었다.

통신 가능한 쌍 $i < j$에 대해 $ans[i] = \max(H[i] - H[j])$라고 하자. 이를 세그먼트 트리로 관리하며 스위핑으로 구할 것이다.

$i$는 $[i + A[i], i + B[i]]$ 범위에서 유효하다. $i$가 유효할 때 세그먼트 트리의 $i$번째 인덱스에 $H[i]$를 저장한다. 이후 $j$가 추가될 때, $j - B[j] \le i \le j - A[j]$ 범위의 $i$에 대해 다음과 같이 갱신한다: \(ans[i]=min(ans[i],H[i]−H[j])\)

이때 세그먼트 트리는 lazy propagation으로 $H[j]$를 갱신하고, 노드에는 $H[i]$를 저장함으로써 $ans[i]$를 효율적으로 구할 수 있다.

노드에 구간의 $ans[i]$의 최댓값을 저장하고, $r = j$인 쿼리를 세그먼트 트리에 $[l, r]$ 구간 쿼리를 날려서서 답을 구하면 된다.

같은 과정을 $H[i]$의 부호를 반대로 하여 한 번 더 수행하면 문제를 완전히 해결할 수 있다.

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 202020;
const int INF = 1e9 + 7;

struct Node {
    int mx = -INF;
    int ans = -INF;
    Node() {}
    Node(int v) : mx(v) {}
};

Node merge(Node a, Node b)
{
    Node ret;
    ret.ans = max(a.ans, b.ans);
    ret.mx = max(a.mx, b.mx);
    return ret;
}

struct SegTree {
    int n;
    vector<int> lazy;
    vector<Node> tree;
    void init(int _n)
    {
        n = _n;
        lazy.resize(4*n, INF);
        tree.resize(4*n);
    }
    void push(int s, int e, int idx)
    {
        if(lazy[idx] != INF) {
            tree[idx].ans = max(tree[idx].ans, tree[idx].mx - lazy[idx]);
            if(s != e) {
                lazy[2*idx] = min(lazy[2*idx], lazy[idx]);
                lazy[2*idx+1] = min(lazy[2*idx+1], lazy[idx]);
            }
            lazy[idx] = INF;
        }
    }
    void update(int x, int v, int s, int e, int idx)
    {
        push(s, e, idx);
        if(e < x || x < s) return;
        if(s == e) {
            tree[idx].mx = v;
            return;
        }
        int m = (s + e) / 2;
        update(x, v, s, m, 2*idx);
        update(x, v, m+1, e, 2*idx+1);
        tree[idx] = merge(tree[2*idx], tree[2*idx+1]);
    }
    void update_range(int l, int r, int v, int s, int e, int idx)
    {
        push(s, e, idx);
        if(r < s || e < l) return;
        if(l <= s && e <= r) {
            lazy[idx] = min(lazy[idx], v);
            push(s, e, idx);
            return;
        }
        int m = (s + e) / 2;
        update_range(l, r, v, s, m, 2*idx);
        update_range(l, r, v, m+1, e, 2*idx+1);
        tree[idx] = merge(tree[2*idx], tree[2*idx+1]);
    }
    Node query(int l, int r, int s, int e, int idx)
    {
        push(s, e, idx);
        if(r < s || e < l) return Node();
        if(l <= s && e <= r) return tree[idx];
        int m = (s + e) / 2;
        return merge(query(l, r, s, m, 2*idx), query(l, r, m+1, e, 2*idx+1));
    }

    void update(int x, int v) { return update(x, v, 1, n, 1); }
    void update_range(int l, int r, int v) { return update_range(l, r, v, 1, n, 1); }
    Node query(int l, int r) { return query(l, r, 1, n, 1); }
};

int N, H[MAXN], A[MAXN], B[MAXN], Q, L[MAXN], R[MAXN], ans[MAXN];

int main()
{
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> H[i] >> A[i] >> B[i];
    cin >> Q;
    for(int i = 1; i <= Q; i++) cin >> L[i] >> R[i];
    
    vector<int> q(Q);
    iota(q.begin(), q.end(), 1);
    sort(q.begin(), q.end(), [](int i, int j){return R[i] < R[j];});
    
    vector<tuple<int, int, int>> add;
    for(int i = 1; i <= N; i++) {
        add.emplace_back(i+A[i], i, 1);
        add.emplace_back(i+B[i]+1, i, 0);
    }
    sort(add.begin(), add.end());

    int j = 0;
    int k = 0;
    SegTree seg1, seg2;
    seg1.init(N);
    seg2.init(N);
    for(int i = 1; i <= N; i++) {
        while(j < add.size() && get<0>(add[j]) <= i) {
            auto [_, idx, op] = add[j++];
            if(op) seg1.update(idx, H[idx]), seg2.update(idx, -H[idx]);
            else seg1.update(idx, -INF), seg2.update(idx, -INF);
        }
        seg1.update_range(i-B[i], i-A[i], H[i]);
        seg2.update_range(i-B[i], i-A[i], -H[i]);
        while(k < q.size() &&  R[q[k]] <= i) {
            int l = L[q[k]];
            int r = R[q[k]];
            ans[q[k]] = max({seg1.query(l, r).ans, seg2.query(l, r).ans, -1});
            k++;
        }
    }
    for(int i = 1; i <= Q; i++) cout << ans[i] << "\n";
}