Codeforces 166(#111 Div2 only) E. Buses and People

問題

n個の点(si, fi, ti)が与えられるので次のQ個のクエリに答えよ。
クエリ：点(x, y, z)に対して、最初のn個の点の中から、s≦x, f≧y, t≧zを満たす点のうち、tがもっとも小さいものの番号を答える。

ただし、最初のn点のtiは全て異なる。

制約条件

n, Q≦10^5
si, fi, ti≦10^9

方針

tiを座標圧縮する。
クエリと点をx座標の小さい順にソート。（x座標が同じなら、点を先に）

segment木のrange max queryを作っておいて、
点(f, t)がきたら、range max queryのtをfで更新する。

クエリ(y, z)が来たら、range max queryの[z, inf)の区間から、
値がy以上になっている最初の場所を二分探索で探せばよい。

この二分探索は、segment木を上から見ていくだけなので、O(log n)でできる。
（bitの二分探索みたいな感じ）
けど、制限時間がゆるいのでquery(L, R)を狭めていくO(log^2n)の二分探索でも通るっぽい。

ソースコード

const int MX = 100010;
int n, m, ans[MX];

const int N = 131072;
int dat[2 * N - 1];
inline void update(int k, int x){
	k += N - 1;
	dat[k] = max(dat[k], x);
	while(k){
		k = (k - 1) / 2;
		dat[k] = max(dat[k * 2 + 1], dat[k * 2 + 2]);
	}
}
inline int find(int a, int b, int l, int r, int k, int x){
	if(b <= l || a >= r) return inf;
	if(dat[k] < x) return inf;
	if(l + 1 == r) return l;
	
	int t = find(a, b, l, (l + r) / 2, k * 2 + 1, x);
	if(t < inf) return t;
	return find(a, b, (l + r) / 2, r, k * 2 + 2, x);
}

int main(){
	rep(i, 2 * N - 1) dat[i] = -inf;
	
	scanf("%d%d", &n, &m);
	vector<pair<pi, pi> > v;
	vi ts;
	map<int, int> id;
	
	rep(i, n){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		v.pb(mp(mp(a, i), mp(b, c)));
		id[c] = i + 1;
		ts.pb(c);
	}
	rep(i, m){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		v.pb(mp(mp(a, i + n), mp(b, c)));
	}
	sort(all(v));
	sort(all(ts)); ts.erase(unique(all(ts)), ts.end());
	
	rep(i, v.size()){
		int c = lower_bound(all(ts), v[i].S.S) - ts.begin();
		if(v[i].F.S < n){
			update(c, v[i].S.F);
		}
		else{
			int k = find(c, N, 0, N, 0, v[i].S.F);
			ans[v[i].F.S - n] = k < inf ? id[ts[k]] : -1;
		}
	}
	rep(i, m) printf("%d%c", ans[i], i == m - 1 ? '\n' : ' ');
	
	return 0;
}