Codeforces ECR #010 : D. Nested Segments

AのReadforcesがひどすぎてCDEの方があっさり解けた。
http://codeforces.com/contest/652/problem/D

問題

１次元数直線上の区間がN個与えられる。
各区間に対し、そこに含まれる区間はいくつあるか答えよ。

解法

区間の両端の座標を座標圧縮し、平面走査＋BITの要領で数え上げる。

…圧縮しなくても、vector+lower_boundでも解けるような気もする。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> bt;

int N;
int L[202020],R[202020];
int ret[202020];
int E[606060];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	vector<int> MP;
	MP.push_back(-1<<30);
	MP.push_back(1<<30);
	FOR(i,N) {
		cin>>L[i]>>R[i];
		MP.push_back(L[i]-1);
		MP.push_back(L[i]);
		MP.push_back(R[i]);
	}
	
	sort(ALL(MP));
	MP.erase(unique(ALL(MP)),MP.end());
	MINUS(E);
	FOR(i,N) {
		L[i]=lower_bound(ALL(MP),L[i])-MP.begin();
		R[i]=lower_bound(ALL(MP),R[i])-MP.begin();
		E[R[i]]=i;
	}
	FOR(i,606000) if(E[i]>=0) {
		x=E[i];
		ret[x]=bt(R[x])-bt(L[x]-1);
		bt.add(L[x],1);
	}
	FOR(i,N) _P("%d\n"	,ret[i]);
}

まとめ

ここらへんはEducational感のある典型問題。