백준[16978] 수열과 쿼리 22

문제 설명

문제 링크

http://icpc.me/16978

16978번: 수열과 쿼리 22

풀이

세그먼트 트리를 이용하여 풀 수 있다.

쿼리를 입력받은 순서대로 하지 않고, i번째 1번 쿼리를 하기 전에 k <= i인 2번 쿼리를 모두 해주고 1번 쿼리를 해줘야 한다.

그렇게 하기 위해 먼저 쿼리를 모두 입력받고, k기준으로 정렬한 후에 쿼리를 수행해야 하고, 다시 원래 순서대로 출력해야 한다.

이렇게 쿼리의 순서를 계산하기 편한 순서로 바꾸는 테크닉을 오프라인 쿼리라고 한다고 한다.

cf) 구간의 합 최댓값이 10^5 * 10^6으로 int형 범위를 넘어갈 수 있다.

코드

#include <iostream>
#include <vector>

using namespace std;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
using ll = long long;
struct T { int k, qs, qe, idx; };
const int N = 1e5 + 5;
ll tree[N * 4];
ll ret[N];

void update(int node, int s, int e, int k, int idx) {
    if (e < idx || idx < s) return;
    tree[node] += k;
    if (s == e) return;
    int mid = (s + e) / 2;
    update(2 * node, s, mid, k, idx);
    update(2 * node + 1, mid + 1, e, k, idx);
}

ll query(int node, int s, int e, int qs, int qe) {
    if (e < qs || qe < s) return 0;
    if (qs <= s && e <= qe) return tree[node];
    int mid = (s + e) / 2;
    return query(2 * node, s, mid, qs, qe) + query(2 * node + 1, mid + 1, e, qs, qe);
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        int ipt; cin >> ipt;
        update(1, 0, N, ipt, i);
    }

    vector<pii> a;
    vector<T> b;
    int t = 0;

    int q; cin >> q;
    for (int i = 0; i < q; i++) {
        int c; cin >> c;
        if (c == 1) {
            int x, y; cin >> x >> y;
            a.push_back({x, y});
        } else {
            int x, y, z; cin >> x >> y >> z;
            b.push_back({x, y, z, t++});
        }
    }
    sort(b.begin(), b.end(), [](T &a, T &b) { 
        return a.k < b.k; 
    });

    int k = 0;
    for (int i = 0; i < a.size(); i++) {
        while (b[k].k == i) {
            auto [x, qs, qe, retIdx] = b[k];
            ret[retIdx] = query(1, 0, N, qs, qe);
            k++;
        }
        auto [idx, k] = a[i];
        k = k - query(1, 0, N, idx, idx);
        update(1, 0, N, k, idx);
    }
    for (int i = k; i < b.size(); i++) ret[b[i].idx] = query(1, 0, N, b[i].qs, b[i].qe);
    for (int i = 0; i < b.size(); i++) cout << ret[i] << '\n';
}