Codeforces 173 E. Camping Groups

Codeforces データ構造

問題

n人の人がいて、それぞれの責任感r[i]および年齢a[i]が与えられる。
この人の中から、次の条件を満たすグループを作りたい。

  • 責任感r[i]が最大の人（タイの場合はタイの中の誰でもいい）をリーダーとする。
  • リーダーと、他の全員の年齢の差がkである。

このとき、次のような質問q個に答えよ。

  • 与えられた番号の人x, yが共に同じグループに入るときの、グループの人数の最大値を求める

制約条件

n, q≦10^5
k, r[i], a[i]≦10^9

方針

リーダーの年齢がちょうどaのときのグループの最大人数をf(a)とすると、
それぞれの質問について、
責任感が、max(r[x], r[y])以上で、年齢がmax(a[x], a[y]) - k以上min(a[x], a[y]) + k以下の人iについてf(a[i])の最大値を効率的に求められたらよい。


これは、クエリをrの大きい順に並べて、Range Minimum Queryに(a, f(a))をrの大きい順に代入していきつつ、
その時点での区間の最大値を取ることでlog n時間で求められる。


リーダーの年齢がちょうどaのときのグループの最大人数はどうやって求めるかというと、
今度は人(r, a)を、rの小さい順に並べて、BITのaに1を足して、a-k以上a-k以下の区間の点の個数を求めれば、log nで計算できる。


ただしaの値が大きいので座標圧縮が必要。

ソースコード

const int MX = 131072;
int n, k, q, r[MX], a[MX], x[MX], y[MX];
int bit[MX], mx[MX], ans[MX], N, data[MX * 2];
pi ps[MX], qs[MX];

inline int sum(int i){
	int res = 0;
	for(; i; i -= i & -i) res += bit[i];
	return res;
}
inline void add(int i, int x){
	for(; i < MX; i += i & -i) bit[i] += x;
}
int get(int a, int b, int l, int r, int k){
	if(b <= l || a >= r) return 0;
	if(a <= l && r <= b) return data[k];
	return max(get(a, b, l, (l+r) / 2, k*2 + 1),
		get(a, b, (l+r) / 2, r, k*2 + 2));
}
void update(int x, int v){
	x += N-1;
	data[x] = max(data[x], v);
	while(x > 0){
		x = (x - 1) / 2;
		data[x] = max(data[x], max(data[x * 2 + 1], data[x * 2 + 2]));
	}
}

void run()
{
	int sz = 0;
	map<int, int> m;
	map<int, int>::iterator it;
	
	cin >> n >> k;
	rep(i, n) cin >> r[i];
	rep(i, n) cin >> a[i], ps[i] = mp(r[i], a[i]), m[a[i]] = 0;
	sort(ps, ps + n);
	fr(i, m) i->second = sz++;
	m[inf] = sz++;
	for(N = 1; N < sz; N *= 2);
	
	rep(i, n){
		int j = i;
		while(j < n-1 && ps[j+1].first == ps[i].first) j++;
		for(int p = i; p <= j; p++) add(m[ps[p].second] + 1, 1);
		
		for(int p = i; p <= j; p++){
			it = m.upper_bound(min((ll)ps[p].second + k, inf - 1ll));
			int u = it->second;
			it = m.lower_bound(max((ll)ps[p].second - k, 0ll));
			int l = it->second, c = m[ps[p].second];
			mx[p] = max(0, sum(u) - sum(l));
		}
		i = j;
	}
	
	cin >> q;
	rep(i, q){
		cin >> x[i] >> y[i];
		x[i]--; y[i]--;
		qs[i] = mp(max(r[x[i]], r[y[i]]), i);
	}
	sort(qs, qs + q);
	for(int i = q-1, j = n; i >= 0; i--){
		while(j > 0 && qs[i].first <= ps[j-1].first){
			j--;
			update(m[ps[j].second], mx[j]);
		}
		int s = x[qs[i].second], t = y[qs[i].second];
		if(a[s] > a[t]) swap(s, t);
		it = m.upper_bound(min((ll)a[s] + k, inf - 1ll));
		int u = it->second;
		it = m.lower_bound(max((ll)a[t] - k, 0ll));
		int l = it->second;
		ans[qs[i].second] = l < u ? get(l, u, 0, N, 0) : 0;
		if(ans[qs[i].second] == 0) ans[qs[i].second] = -1;
	}
	rep(i, q) cout << ans[i] << endl;
}