Language: C++

#include <iostream>
#include <fstream>
#include <iomanip>
#include <climits>
#include <limits>
#include <algorithm>
#include <array>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <unordered_map>
#include <random>
#include <cmath>
#include <complex>

using namespace std;

typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;

const int INFL = (int)1e9;
const ll INFLL = (ll)1e18;
const double INFD = numeric_limits<double>::infinity();
const double PI = 3.14159265358979323846;
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loopll(i, n) for(ll i = 0; i < (ll)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopll1(i, n) for(ll i = 1; i <= (ll)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Looprll(i, n) for(ll i = (ll)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
#define Looprll1(i, n) for(ll i = (ll)n; i >= 1; i--)
#define Loopitr(itr, container) for(auto itr = container.begin(); itr != container.end(); itr++)
#define printv(vector) Loop(i, vector.size()) { cout << vector[i] << " "; } cout << endl;
#define printmx(matrix) Loop(i, matrix.size()) { Loop(j, matrix[i].size()) { cout << matrix[i][j] << " "; } cout << endl; }
#define rndf(d) (ll)((double)(d) + (d >= 0 ? 0.5 : -0.5))
#define floorsqrt(x) ((ll)sqrt((double)x) + ((ll)sqrt((double)x) * (ll)sqrt((double)x) <= (ll)(x) ? 0 : -1))
#define ceilsqrt(x) ((ll)sqrt((double)x) + ((ll)x <= (ll)sqrt((double)x) * (ll)sqrt((double)x) ? 0 : 1))
#define rnddiv(a, b) ((ll)(a) / (ll)(b) + ((ll)(a) % (ll)(b) * 2 >= (ll)(b) ? 1 : 0))
#define ceildiv(a, b) ((ll)(a) / (ll)(b) + ((ll)(a) % (ll)(b) == 0 ? 0 : 1))
#define bitmanip(m,val) static_cast<bitset<(int)m>>(val)

/*******************************************************/

template <class val_t>
class kdTree {
private:
	struct node {
		int id;
		val_t val;
		int deg;
		node *parent;
		node *left, *right;
	};
	int dimension; // dimension
	int n; // the number of nodes
	node *root; // the root of the tree
	node *nil; // the node for leaves of the tree
	pair<val_t, val_t> bounding_box; // save min_val and max_val
	bool bounding_box_enabled; // enable bounding_box
	struct idval_t {
		int id;
		val_t val;
	};
	template <typename vidval_iterator>
	node* build_kdTree_rec(node *parent, pair<vidval_iterator, vidval_iterator> range, int depth) {
		if (distance(range.first, range.second) == 0) return nil;
		else {
			node *ret = new node;
			int axis = depth % dimension;
			sort(range.first, range.second, [=](const idval_t& l, const idval_t& r) { return l.val[axis] < r.val[axis]; });
			vidval_iterator mid = range.first + distance(range.first, range.second) / 2;
			idval_t target = { -1, bounding_box.first };
			target.val[axis] = mid->val[axis];
			mid = lower_bound(range.first, range.second, target, [=](const idval_t &l, const idval_t & r) {return l.val[axis] < r.val[axis]; });
			*ret = { mid->id, mid->val, depth, nil, nil, nil };
			ret->left = build_kdTree_rec<vidval_iterator>(ret, { range.first, mid }, depth + 1);
			ret->right = build_kdTree_rec<vidval_iterator>(ret, { mid + 1,range.second }, depth + 1);
			return ret;
		}
	}
	vi find_in_range_rec(node *focus, pair<val_t, val_t> &range, int depth) {
		if (focus == nil) return {};
		else {
			vi ret;
			int axis = depth % dimension;
			bool judge = true;
			Loop(i, dimension) {
				if (range.first[i] <= focus->val[i] && focus->val[i] <= range.second[i]) continue;
				else { judge = false; break; }
			}
			if (judge) ret.push_back(focus->id);
			if (range.first[axis] < focus->val[axis]) {
				vi left_result = find_in_range_rec(focus->left, range, depth + 1);
				ret.insert(ret.end(), left_result.begin(), left_result.end());
			}
			if (focus->val[axis] <= range.second[axis]) {
				vi right_result = find_in_range_rec(focus->right, range, depth + 1);
				ret.insert(ret.end(), right_result.begin(), right_result.end());
			}
			return ret;
		}
	}
	inline void update_bounding_box(val_t &a) {
		if (!bounding_box_enabled) {
			bounding_box = { a,a };
		}
		else {
			Loop(i, a.size()) {
				bounding_box.first[i] = min(bounding_box.first[i], a[i]);
				bounding_box.second[i] = max(bounding_box.second[i], a[i]);
			}
		}
	}
public:
	kdTree(vector<val_t> A, int dimension) {
		n = (int)A.size();
		this->dimension = dimension;
		bounding_box_enabled = false;
		vector<idval_t> ary(n);
		Loop(i, n) {
			ary[i] = { i, A[i] };
			update_bounding_box(A[i]);
		}
		nil = new node;
		root = build_kdTree_rec<vector<idval_t>::iterator>(nil, {ary.begin(), ary.end()}, 0);
		return;
	}
	// return id of vals in [range.first, range.second]
	vi find_in_range(pair<val_t, val_t> range) {
		vi ret = find_in_range_rec(root, range, 0);
		sort(ret.begin(), ret.end());
		return ret;
	}
};

int main() {
	int n; cin >> n;
	vvi a(n, vi(2));
	Loop(i, n) {
		Loop(j, 2) {
			cin >> a[i][j];
		}
	}
	kdTree<vi> kdtree(a, 2);
	int q; cin >> q;
	Loop(i, q) {
		pair<vi, vi> range = { vi(2), vi(2) };
		Loop(j, 2) {
			cin >> range.first[j] >> range.second[j];
		}
		vi ans = kdtree.find_in_range(range);
		Loop(j, ans.size()) cout << ans[j] << endl;
		cout << endl;
	}
}


Compiler output:
a.cc: In instantiation of 'kdTree<val_t>::kdTree(std::vector<_Tp>, int) [with val_t = std::vector<int>]':
a.cc:159:24:   required from here
  159 |         kdTree<vi> kdtree(a, 2);
      |                               ^
a.cc:140:58: error: dependent-name 'std::vector<kdTree<val_t>::idval_t>::iterator' is parsed as a non-type, but instantiation yields a type
  140 |                 root = build_kdTree_rec<vector<idval_t>::iterator>(nil, {ary.begin(), ary.end()}, 0);
      |                                                          ^~~~~~~~
a.cc:140:58: note: say 'typename std::vector<kdTree<val_t>::idval_t>::iterator' if a type is meant