백준27412 Matrix

작성일 | In

문제 링크

  • https://icpc.me/27412

시간복잡도

  • $O(Q \log NM)$

풀이

subtask 2의 입력 제한이 $10^5$, subtask 3의 입력 제한이 $5\times 10^5$인 것을 보면 동적 세그먼트 트리를 짜면 시간 초과를 받을 것이라고 예상할 수 있습니다. BBST를 이용한 풀이를 생각해 봅시다.
만약 구간에 임의의 수를 더해야 한다면 꼼짝 없이 스플레이 트리나 트립을 구현해야 하겠지만, 다행이도 이 문제는 구간에 1응 더하는 쿼리만 주어집니다. 구간 $[s, e]$에 1을 더하는 것은 $s$에 1을 더하고 $e+1$에 1을 뺀 다음 누적합을 구하는 것으로 대신할 수 있습니다.
따라서 어떤 칸 $(r, c)$의 값을 구하는 것은, $r$번째 행에서 $[1, c]$에 1이 더해진 횟수와 1이 빠진 횟수를 각각 구하면 됩니다. BBST를 직접 구현해도 되고, gcc extensions에 있는 __gnu_pbds::tree를 사용해도 됩니다. 아래 코드는 pbds를 사용한 코드입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;

void initialize(long long N, long long M) {}

ordered_set<pair<ll,ll>> A[505050], B[505050];
unordered_map<ll, int> C; int P;

void update(long long X, long long Y1, long long Y2) {
    int id = C.count(X) ? C[X] : (C[X] = C.size());
    A[id].insert({Y1, ++P}); B[id].insert({Y2+1, P});
}

int query(long long X, long long Y) {
    int id = C.count(X) ? C[X] : (C[X] = C.size());
    auto it1 = A[id].lower_bound(make_pair(Y, INF));
    auto it2 = B[id].lower_bound(make_pair(Y, INF));
    int pl = it1 != A[id].end() ? A[id].order_of_key(*it1) : A[id].size();
    int mi = it2 != B[id].end() ? B[id].order_of_key(*it2) : B[id].size();
    return pl - mi;
}