Pagini recente » Cod sursa (job #2707991) | Cod sursa (job #1658476) | Cod sursa (job #2789396) | Cod sursa (job #2876291) | Cod sursa (job #3166806)
#include <bits/stdc++.h>
#include <random>
#include <chrono>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const char nl = '\n';
const char sp = ' ';
const int inf = 0x3f3f3f3f;
const long long INF = 1000000000000000000;
const int mod = 1e9 + 7;
const char out[2][4]{ "NO", "YES" };
#define all(A) A.begin(), A.end()
using ll = long long;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
#define variableName(var) #var
#define __debug(var) cout << #var << " = " << var << '\n'
inline int rint(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
struct point {
ll x, y;
bool operator==(const point& other) const {
return x == other.x && y == other.y;
}
};
struct DynamicOrtogonalSegmentTree {
struct TreeNode {
TreeNode* children[2][2];
int value;
TreeNode() {
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
children[i][j] = nullptr;
}
}
value = 0;
}
void compute() {
value = 0;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
if (children[i][j] != nullptr) {
value += children[i][j]->value;
}
}
}
}
};
TreeNode* root = new TreeNode;
pair<point, point> range;
// add a point to the 2D dynamic segment tree
void add(TreeNode* root, pair<point, point> curr, point pos) {
// found it
if (curr.first == pos && curr.second == pos) {
root->value++;
return;
}
ll midx = (curr.first.x + curr.second.x) / 2;
ll midy = (curr.first.y + curr.second.y) / 2;
pair<point, point> next;
if (pos.x <= midx) {
next.first.x = curr.first.x;
next.second.x = midx;
}
else {
next.first.x = midx + 1;
next.second.x = curr.second.x;
}
if (pos.y <= midy) {
next.first.y = curr.first.y;
next.second.y = midy;
}
else {
next.first.y = midy + 1;
next.second.y = curr.second.y;
}
if (root->children[pos.y > midy][pos.x > midx] == nullptr) {
root->children[pos.y > midy][pos.x > midx] = new TreeNode;
}
add(root->children[pos.y > midy][pos.x > midx], next, pos);
root->compute();
}
void add(point pos) { add(root, range, pos); }
// get the number of points in a 2D range
int get(TreeNode* root, pair<point, point> curr, pair<point, point> query) {
// empty
if (root == nullptr) {
return 0;
}
// outside of query
if (curr.second.x < query.first.x || curr.first.x > query.second.x
|| curr.second.y<query.first.y || curr.first.y>query.second.y) {
return 0;
}
// inside of query
if (query.first.x <= curr.first.x && curr.second.x <= query.second.x
&& query.first.y <= curr.first.y && curr.second.y <= query.second.y) {
return root->value;
}
// curr intersects query
ll midx = (curr.first.x + curr.second.x) / 2;
ll midy = (curr.first.y + curr.second.y) / 2;
return get(root->children[0][0], { curr.first, { midx, midy } }, query) +
get(root->children[0][1], { { midx + 1, curr.first.y }, { curr.second.x, midy } }, query) +
get(root->children[1][0], { { curr.first.x, midy + 1 }, { midx, curr.second.y } }, query) +
get(root->children[1][1], { { midx + 1, midy + 1 }, curr.second }, query);
}
int get(pair<point, point> query) { return get(root, range, query); }
} tree;
int n, m;
int max_coord_x = 0, max_coord_y = 0;
vector<point> points;
vector<pair<point, point>> querys;
void normalizeInput() {
map<int, int> normx;
map<int, int> normy;
for (auto& p : points) {
normx[p.x] = normy[p.y] = 0;
}
for (auto& q : querys) {
normx[q.first.x] = normx[q.second.x] = normy[q.first.y] = normy[q.second.y] = 0;
}
for (auto& it : normx) {
static int k = 0;
it.second = k++;
}
for (auto& it : normy) {
static int k = 0;
it.second = k++;
}
for (auto& p : points) {
p.x = normx[p.x];
p.y = normy[p.y];
}
for (auto& q : querys) {
q.first.x = normx[q.first.x];
q.first.y = normy[q.first.y];
q.second.x = normx[q.second.x];
q.second.y = normy[q.second.y];
}
max_coord_x = normx.rbegin()->second;
max_coord_y = normy.rbegin()->second;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
fin >> n;
points.resize(n);
for (auto& p : points) {
fin >> p.x >> p.y;
}
fin >> m;
querys.resize(m);
for (auto& q : querys) {
fin >> q.first.x >> q.first.y >> q.second.x >> q.second.y;
}
normalizeInput();
tree.range = {
point{ 0, 0 },
point{ max_coord_x, max_coord_y }
};
for (auto& p : points) {
tree.add(p);
}
for(auto& q : querys) {
fout << tree.get(q) << nl;
}
}