BOJ 11012 Egg

1 개요[ | ]

BOJ 11012 Egg
2 C++[ | ]

#include <bits/stdc++.h>
using namespace std;

#define MAX_SIZE 100005
typedef long long ll;
int T, n, m;
vector<vector<int>> xpos(MAX_SIZE);

class Node {
public:
    ll val;
    Node* left, *right;

    Node(Node* left = 0, Node* right = 0) :
        left(left), right(right), val(0) {
    }

    Node* insert(int l, int r, int w, ll val) {
        if (l <= w && w <= r) {
            if (l == r) {
                Node* leaf = new Node();
                leaf->val = this->val + val;
                return leaf;
            }
            int m = (l + r) >> 1;
            Node* cl = this->left->insert(l, m, w, val);
            Node* cr = this->right->insert(m + 1, r, w, val);
            Node* leaf = new Node(cl, cr);
            leaf->val = cl->val + cr->val;
            return leaf;
        }
        return this;
    }

    ll query(int s, int e, int l, int r) {
        if (e < l || r < s) return 0;
        if (l <= s && e <= r) return this->val;
        int m = (s + e) >> 1;
        ll answer = 0;
        answer += this->left->query(s, m, l, r);
        answer += this->right->query(m + 1, e, l, r);
        return answer;
    }
};

void solve() {
    vector<Node*> nodes(MAX_SIZE + 2);
    nodes[0] = new Node();
    nodes[0]->left = nodes[0]->right = nodes[0];
    nodes[0]->val = 0;
    
    for (int y = 1; y < MAX_SIZE; ++y) {
        nodes[y] = nodes[y - 1];
        for (auto& x : xpos[y]) {
            nodes[y] = nodes[y]->insert(1, MAX_SIZE, x, 1);
        }
    }
    
    ll answer = 0;
    int l, r, b, t;
    while (m--) {
        cin >> l >> r >> b >> t;
        answer += nodes[t+1]->query(1, MAX_SIZE, l+1, r+1);
        answer -= nodes[b]->query(1, MAX_SIZE, l+1, r+1);
    }
    cout << answer << "\n";
}

void sub() {
    cin >> n >> m;
    xpos.resize(0);
    xpos.resize(MAX_SIZE);
    for (int i = 0; i < n; ++i) {
        int y, x;
        cin >> x >> y;
        xpos[y+1].push_back(x+1);
    }
    solve();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--) {
        sub();
    }
}