Codeforces #222 Div1. D. Developing Game

これはDの割に簡単。
http://codeforces.com/contest/377/problem/D

問題

N人のスタッフがいる。
各スタッフの能力はV[i]である。

スタッフを何人か組み合わせてチームを作りたい。
ただし各スタッフは能力がL[i]以上R[i]以下の人としか組みたくない。

最大何人のチームが作れるか。実際に構成例を示せ。

解法

範囲に対し同じ値を加算可能、かつ区間の最大値を求めることができるSegTreeを作ろう。
以下V[i]及びR[i]の順にソートしてsweepし、人数が最大となる能力の区間を求めよう。

• 能力V[i]のスタッフを処理する場合：
  • チームの区間の最小値が[L[i]..V[i]]に含まれるなら、この人はチームに入りうる。よってSegTreeの[L[i]..V[i]]に1加算する。
• 組みたい人がR[i]のスタッフを処理する場合：
  • 以後R[i]より高い能力の人を処理する際、同じチームになることはありえない。よってSegTreeの[L[i]..V[i]]から1減算する。

あとは処理のたびにSegTreeの最大値を見るだけ。
スタッフ人数が最大となる区間が求まれば、そこに入りうるスタッフも確定する。

template<class V,int NV> class SegTree_2 {
public:
	vector<V> val,ma,from;
	SegTree_2(){val.resize(NV*2,0); ma.resize(NV*2,0);from.resize(NV*2,-1); };
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
			if(from[k]==-1) from[k]=r-1;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			if(ma[k*2]>ma[k*2+1]) ma[k]=ma[k*2], from[k]=from[k*2];
			else  ma[k]=ma[k*2+1], from[k]=from[k*2+1];
			ma[k]+=val[k];
		}
		
	}
};

int N;
int L[101000],R[101000],V[101000];
vector<int> Vev[303000],Rev[303000];
SegTree_2<int,1<<20> st;
int ma=-1,LL,RR;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>L[i]>>V[i]>>R[i];
		Vev[V[i]].push_back(i);
		Rev[R[i]].push_back(i);
	}
	
	FOR(i,300100) if(Vev[i].size() || Rev[i].size()) {
		FOR(j,Vev[i].size()) st.update(L[Vev[i][j]],V[Vev[i][j]]+1,1);
		if(st.ma[1]>ma) ma=st.ma[1], LL=st.from[1],RR=i;
		FOR(j,Rev[i].size()) st.update(L[Rev[i][j]],V[Rev[i][j]]+1,-1);
	}
	
	vector<int> ret;
	FOR(i,N) if(LL<=V[i] && V[i]<=RR && L[i]<=LL && RR<=R[i]) ret.push_back(i+1);
	
	_P("%d\n",ret.size());
	ITR(it,ret) _P("%d ",*it);
	_P("\n");
	
}

まとめ

これはDiv1 Cでもいい問題かな。