UTPC2012 : H - 区間スケジューリングクエリ

ここまでは配点200ptの中級問題。
これでもこちらはヒーヒー言ってるのに、UTPCレベル高過ぎだろ…
http://utpc2012.contest.atcoder.jp/tasks/utpc2012_08

仕事の開始・終了時間と、各人の仕事開始・終了時間が与えられるので、各人が処理できる仕事数を答える問題。
計算量を度外視すればこれは簡単で、蟻本にもある通り「終了時間順に仕事をソートし、終了時間が手前な順に処理する」でよい。
ただ、この手順は仕事数Nと人数Qに対しO(NQ)かかるので、最大値のN=10^5、Q=10^5に適用すると最悪O(NQ)でTLEになる。

こちらも自分では解決できなかったのでhttp://www.utpc.jp/2012/slides/intervalQuery.pdf:titl=解説を参考に解いた。
前処理として、各仕事において次に取り組む仕事を求めておき、それを倍々に２つ先、４つ先、８つ先…と求めておく。
この情報を使えば、１人当たりの時間がO(logN)なので全体でO(Q logN)で何とか解くことができる。

なお、軽量化のために前処理で明らかに不要な仕事(他の仕事より開始が早く終了が多い仕事)は削除している。

int N,Q;
vector<pair<int,int> > mp,mp2;
vector<int> lefts;
int next[100005][16];

void solve() {
	int x,y,i,j,res,TM,nc;
	int tx,ty,ng,LS;
	char cmd[100];
	ll p,cch;
	
	N=GETi();
	Q=GETi();
	
	FOR(i,N) {
		x=GETi();
		y=GETi();
		mp2.push_back(make_pair(y,-x));
	}
	MINUS(next);
	
	sort(mp2.begin(),mp2.end());
	int pl=-1000000001;
	j=0;
	FOR(i,N) {
		if(-mp2[i].second>pl) {
			pl=-mp2[i].second;
			mp.push_back(make_pair(mp2[i].first,-mp2[i].second));
			lefts.push_back(-mp2[i].second);
		}
	}
	N=mp.size();
	
	FOR(i,N) {
		vector<int>::iterator it=lower_bound(lefts.begin(),lefts.end(),mp[i].first);
		if(it!=lefts.end()) next[i][0]=it-lefts.begin();
	}
	
	FOR(j,14) FOR(i,N) if(next[i][j]>=0 && next[next[i][j]][j]>=0) next[i][j+1]=next[next[i][j]][j];
	
	FOR(i,Q) {
		int L=GETi();
		int R=GETi();
		
		vector<int>::iterator it=lower_bound(lefts.begin(),lefts.end(),L);
		res=0;
		if(it!=lefts.end()) {
			int cur=it-lefts.begin();
			if(mp[cur].first<=R) {
				res++;
				for(j=14;j>=0;j--) {
					while(next[cur][j]!=-1 && mp[next[cur][j]].first<=R) {
						res += 1<<j;
						cur = next[cur][j];
					}
				}
			}
		}
		_P("%d\n",res);
	}
	
	return;
}

まとめ

倍々で求めていく経路圧縮、蟻本で見たけど初めてコード書いた。
こういうのをパッと思いつきたいな。