Autumn Fest 2012 : H U・N・C・O

８問目。ここからは、http://www.slideshare.net/tomerun/tag/autumnfest2012|公式の解説をもとに解いてみた。
http://autumn_fest.contest.atcoder.jp/tasks/autumn_fest_08

本番では、D=2すら解けず…。
N=100000と大きいので、O(N^2)でも時間が足りない。
O(NlogN)以下にしないとだめなので、とりあえずソートしたけどダメだった…。

終了後解説を見て、このケースはBITを使って解けることを知った。
まず、全部の運行を開始時間順にソートする。
そして終了時間を元にBITに１個ずつ運行エントリを追加していく。

運行エントリの追加はlogNでできるし、「今見ている運行よりも終了時間が早い運行の数」もBITならlogNでできるので、D=2ならO(NlogN)でできる。
解説によると、２次元座標で「ある点より左上にある点の数」は同様にBITでO(NlogN)で求まるようだ。

あとは、ある運行がD=k個の最短区間なら、その数はその運行を挟むD=k-1の最短区間の数の和になる。
よって全体でN(NDlogN)で終わる。
ついでなので、蟻本をもとにBITのクラスを作ってみた。

int N,D;
vector< pair<int,int> > nums,nume;
int L[100000];
int R[100000];
ll nc[16][100000];

template<class V, int ME> class BIT {
public:
	V bit[ME];
	
	BIT(){clear();};
	void clear() {ZERO(bit);};
	
	V total(int entry) {
		V s=0;
		entry++;
		while(entry>0) {
			s+=bit[entry-1];
			entry -= entry & -entry;
		}
		s %= 314159265;
		return s;
	}
	void update(int entry, V val) {
		entry++;
		while(entry <= ME) {
			bit[entry-1] += val;
			bit[entry-1] %= 314159265;
			entry += entry & -entry;
		}
	}
};

BIT<ll,1<<17> bt;


void solve() {
	int x,y,i,j,p,rr,d,res;
	ll ret;
	
	nums.clear();
	nume.clear();
	N=GETi();
	D=GETi();
	
	FOR(i,N) {
		x=GETi();
		y=GETi();
		nums.push_back(make_pair(x,i));
		nume.push_back(make_pair(y,i));
	}
	
	ZERO(nc);
	sort(nums.begin(),nums.end());
	sort(nume.begin(),nume.end());
	FOR(i,nums.size()) {
		nc[1][i]++;
		L[nums[i].second]=i;
		R[nume[i].second]=nums.size()-1-i;
	}
	
	for(d=2;d<=D;d++) {
		ret = 0;
		bt.clear();
		FOR(i,nums.size()) {
			int id = nums[i].second;
			nc[d][id] = bt.total(R[id]);
			bt.update(R[id],nc[d-1][id]);
			ret+=nc[d][id];
		}
		ret %= 314159265;
	}
	
	_P("%lld\n",ret);
	return;
}

まとめ

「２次元座標で点の左上にある点の数」をBITで求められるとは知らなかった。
この知識は後々使えそうだ。