백준 11012번 Egg

문제 요약

2차원 좌표 상에서 점이 N개 놓여 있습니다. 그리고 직사각형 쿼리가 주어지는데 해당 직사각형 안에 존재하는 점의 갯수를 구해야 합니다.

 

좌표의 범위는 최대 10만입니다.

풀이

2차원 세그트리를 만들어서 점들을 기록해 놓는다면 $O(log^2MAX), MAX=10^5$로 해결이 가능하지만 이거를 쌩으로 만들어 버리면 메모리가 $O(MAX^2)$가 필요해서 만들 수가 없습니다.

 

직사각형 쿼리가 $l, r, b, t$로 들어오는데 이 부분에 대한 구간합을 묻는 것과 동일합니다.

tree[x][y]를 x좌표가 [0...x]인 점들 중에서 y좌표가 y인 점들의 개수라고 생각합시다.

그러면 해당 쿼리는 tree[r][b...t] - tree[l-1][b...t]를 묻는 것과 같습니다.

 

tree[x]를 일일이 다 만들면 다시 메모리초과가 납니다. 그러나, tree[x]와 tree[x+1]을 비교했을 때, 바뀌는 부분은 x좌표가 x+1인 점들의 y좌표에만 변경이 일어납니다.

즉, 0부터 MAX까지에 해당하는 세그먼트 트리를 만들고 tree[-1]같이 이름을 붙여두면 tree[x]에서 tree[x+1]로 변할 때마다 x좌표가 x+1인 점들의 y좌표만 업데이트 해줍니다.

이를 PST로 처리하면 추가적인 메모리를 $O(NlogMAX)$만 사용합니다.이제 tree[x]에 대한 모든 세그먼트 트리를 완성할 수 있습니다.

위에서 말한대로 쿼리를 처리하면 됩니다.

#include<iostream>
#include<utility>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
#define MAXN 100001
int N, M, tsz;

struct Node {
    int l, r, val;
    Node() : l(0), r(0), val(0) {};
    Node(int _l, int _r, int _val) : l(_l), r(_r), val(_val) {};
};

void init(vector<Node> &tree) {
    int sz = tsz >> 1;
    for (int i = 1; i <= sz; ++i) {
        tree[i].l = i << 1; tree[i].r = i << 1 | 1;
    }
}

void update(vector<Node> &tree, int node, int s, int e, int val, int idx) {
    if (s != e) {
        int mid = (s + e) >> 1;
        int n1 = tree[node].l, n2 = tree[node].r;
        if (idx <= mid) {
            tree[node].l = tree.size();
            tree.push_back(Node(tree[n1].l, tree[n1].r, tree[n1].val + val));
            update(tree, tree[node].l, s, mid, val, idx);
        }
        else {
            tree[node].r = tree.size();
            tree.push_back(Node(tree[n2].l, tree[n2].r, tree[n2].val + val));
            update(tree, tree[node].r, mid + 1, e, val, idx);
        }
    }
}

int query(vector<Node> &tree, int node, int s, int e, int l, int r) {
    if (r < s || l > e) return 0;
    if (l <= s && e <= r) return tree[node].val;
    int mid = (s + e) >> 1;
    int n1 = tree[node].l, n2 = tree[node].r;
    return query(tree, n1, s, mid, l, r) + query(tree, n2, mid + 1, e, l, r);
}

int roots[100005];
vector<Node> tree;
int main() {
    tsz = 1;
    while (tsz < MAXN) tsz <<= 1;
    tsz <<= 1;
    cin.tie(nullptr); ios::sync_with_stdio(false);
    int tc; cin >> tc;
    while (tc--) {
        cin >> N >> M;
        vector<vector<int>> yval(MAXN+1);
        tree = vector<Node>(tsz);
        for (int i = 0; i < N; ++i) {
            int x, y;
            cin >> x >> y;
            ++x; ++y;
            yval[x].push_back(y);
        }
        init(tree);
        roots[0] = 1;
        for (int i = 1; i <= MAXN; ++i) {
            roots[i] = tree.size();
            int pi = roots[i - 1];
            tree.push_back(Node(tree[pi].l, tree[pi].r, tree[pi].val));
            for (auto y : yval[i]) {
                tree[roots[i]].val += 1;
                update(tree, roots[i], 1, MAXN, 1, y);
            }
        }
        long long ans = 0;
        for (int i = 0; i < M; ++i) {
            int l, r, b, t;
            cin >> l >> r >> b >> t;
            ++r; ++b; ++t;
            ans += query(tree, roots[r], 1, MAXN, b, t) - query(tree, roots[l], 1, MAXN, b, t);
        }
        cout << ans << '\n';
    }
    return 0;
}