rangetree.cpp

//構築 : O(n log n)
//query(count) O(log n)
class RangeTreeWithFractionalCascading {
public:
	int n;
	vector<Pll> xsorted;

	vector<vector<Pll>> dat;
	vector<vector<Pii>> bsearch_speedup;
	RangeTree(vector<Pll>& a) {
		n = 1;
		while (n < sz(a)) n <<= 1;
		dat.resize(2 * n - 1);

		//sort by first
		sort(a.begin(), a.end());
		xsorted = a;
		xsorted.resize(n, Pll(LLONG_MAX, LLONG_MAX));
		bsearch_speedup.resize(n);

		FOR(i, n) {
			int k = n - 1 + i;
			if (i < sz(a)) dat[k].push_back(a[i]);
			else dat[k].push_back(Pll(LLONG_MAX, LLONG_MAX));
		}
		for (int i = n - 2; i >= 0; i--) {
			dat[i].resize(sz(dat[2 * i + 1]) + sz(dat[2 * i + 2]));
			//sort by second
			merge(dat[2 * i + 1].begin(), dat[2 * i + 1].end(),
				  dat[2 * i + 2].begin(), dat[2 * i + 2].end(),
				  dat[i].begin(),
				  [](const Pll& l, const Pll&  r) { return l.second != r.second ? l.second < r.second : l.first < r.first; }
			);
			//binary_search speed up with fractional cascading
			bsearch_speedup[i].resize(sz(dat[i]));
			int a1 = 0, a2 = 0;
			FOR(k, sz(dat[i])) {
				while (a1 < sz(dat[i * 2 + 1]) && dat[i * 2 + 1][a1].second < dat[i][k].second) a1++;
				bsearch_speedup[i][k].first = a1;
				while (a2 < sz(dat[i * 2 + 2]) && dat[i * 2 + 2][a2].second < dat[i][k].second) a2++;
				bsearch_speedup[i][k].second = a2;
			}
		}
	}
	// [lx,rx) * [ly,ry) にある頂点の個数を数え上げる，O(log n)
	int query(ll lx, ll rx, ll ly, ll ry) {
#define CMP [](const Pll& l, const ll val) { return l.second < val; }
		int ly_index = lower_bound(dat[0].begin(), dat[0].end(), ly, CMP) - dat[0].begin();
		int ry_index = lower_bound(dat[0].begin(), dat[0].end(), ry, CMP) - dat[0].begin();
#undef  CMP
		return query(lx, rx, ly_index, ry_index, 0, 0, n);
	}
	int query(ll lx, ll rx, int ly_index, int ry_index, int k, int a, int b) {
		if (rx <= xsorted[a].first || xsorted[b - 1].first < lx) return 0;
		if (lx <= xsorted[a].first && xsorted[b - 1].first < rx) {
			return ry_index - ly_index;
		}
		int nly_idx_f = (ly_index < sz(bsearch_speedup[k])) ? bsearch_speedup[k][ly_index].first : ly_index / 2;
		int nly_idx_s = (ly_index < sz(bsearch_speedup[k])) ? bsearch_speedup[k][ly_index].second : ly_index / 2;
		int nry_idx_f = (ry_index < sz(bsearch_speedup[k])) ? bsearch_speedup[k][ry_index].first : ry_index / 2;
		int nry_idx_s = (ry_index < sz(bsearch_speedup[k])) ? bsearch_speedup[k][ry_index].second : ry_index / 2;
		return query(lx, rx, nly_idx_f, nry_idx_f, 2 * k + 1, a, (a + b) / 2) +
			query(lx, rx, nly_idx_s, nry_idx_s, 2 * k + 2, (a + b) / 2, b);
	}
};