Codeforces 377(#222 Div1) D. Developing Game

Codeforces データ構造

問題

n人の人からなるべく大きい人数のグループを作る。
i番目の人はスキルがsiである。この人は、グループの他人全員のスキルがli以上ri以下じゃなければグループに入らない。
最大で何人のグループができるか。

制約条件

n≦10^5
0≦li≦ri≦si≦3*10^5

方針

L, Rを固定してスキルが[L, R]の人だけを使うと考える。
すると、li≦L, L≦si≦R, R≦riが成り立っている人が使える。


L, Rを全部試すのは無理なので、Lを動かしながら人数が効率的に求められないか考えてみる。
人間をliの小さい順に並べておく。
Lを大きくしたとき、

  • li≦Lになって、新たに使えるようになったiを考えている集合に入れる。
  • si＜Lになってしまい使えなくなったiを集合から外す。


後者の管理は、集合に入っている人をpriority_queueで持てば速くできる。
で、新たに人(si, ri)が使えるようになったとき、
答えは、si≦R≦riが成り立つような範囲のRのとき1増える。
つまり、segment木で区間[si, ri]に1を足してやる。


で、最大値は全区間上でのsegment木の最大値になる。
解の復元が要求されているので、最大値を実現したRもsegment木が返すようにする。


segment木のRMQに区間の加算をできるようにするには、遅延評価を入れればよい。

ソースコード

const pi UNDEF(0, -1);

template<class T>struct SegTree{
	
	T *dat;
	int n, *add;
	SegTree(int size = 1000000){
		for(n = 1; n < size; n *= 2);
		dat = new T[2 * n - 1];
		add = new int[2 * n - 1];
		init();
	}
	~SegTree(){ delete [] dat; }
	
	void init(){
		memset(add, 0, sizeof(int) * (2 * n - 1));
		rep(i, n) dat[i + n - 1] = pi(0, i);
		for(int i = n - 2; i >= 0; i--) dat[i] = max(dat[i * 2 + 1], dat[i * 2 + 2]);
	}
	inline void plus(int a, int b, int k, int l, int r, int x){
		if(r <= a || b <= l) return;
		if(a <= l && r <= b){
			add[k] += x;
			return;
		}
		if(add[k]){
			add[k * 2 + 1] += add[k];
			add[k * 2 + 2] += add[k];
			add[k] = 0;
		}
		plus(a, b, k * 2 + 1, l, (l + r) / 2, x);
		plus(a, b, k * 2 + 2, (l + r) / 2, r, x);
		
		T c = dat[k * 2 + 1], d = dat[k * 2 + 2];
		c.first += add[k * 2 + 1]; d.first += add[k * 2 + 2];
		dat[k] = max(c, d);
	}
	inline void plus(int a, int b, int x){ plus(a, b, 0, 0, n, x); }
	inline T query(int a, int b, int k, int l, int r){
		if(r <= a || b <= l) return UNDEF;
		if(a <= l && r <= b){
			T res = dat[k];
			res.first += add[k];
			return res;
		}
		if(add[k]){
			add[k * 2 + 1] += add[k];
			add[k * 2 + 2] += add[k];
			add[k] = 0;
		}
		T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		
		return max(vl, vr);
	}
};

const int MX = 100000;
int n, l[MX], sk[MX], r[MX];

int main(){
	scanf("%d", &n);
	vector<pair<int, pi> > v;
	rep(i, n){
		scanf("%d%d%d", l + i, sk + i, r + i);
		v.pb(mp(l[i], mp(sk[i], r[i])));
	}
	sort(all(v));
	priority_queue<pi, vector<pi>, greater<pi> > in;
	SegTree<pi> tree(3 * 100010);
	
	int ans = 0, ml = -1, mr = -1;
	
	rep(it, v.size()){
		
		int L = v[it].first;
		in.push(v[it].second);
		tree.plus(v[it].second.first, v[it].second.second + 1, 1);
		
		
		while(in.size() && in.top().first < L){
			
			int l = in.top().first, r = in.top().second; in.pop();
			tree.plus(l, r + 1, -1);
		}
		pi mx = tree.query(0, tree.n, 0, 0, tree.n);
		if(mx.first > ans){
			ans = mx.first;
			ml = L; mr = mx.second;
		}
	}
	printf("%d\n", ans);
	rep(i, n) if(ml <= sk[i] && sk[i] <= mr && l[i] <= ml && mr <= r[i])
		printf("%d%c", i + 1, --ans ? ' ' : '\n');
	
	return 0;
}