Codeforces #573 Div1 D. Tokitsukaze and Strange Rectangle

なんかDまで典型感強くてDiv2っぽい回だ。
http://codeforces.com/contest/1190/problem/D

問題

2次元座標上でN個の点の座標が与えられる。
下辺・右辺・左辺が軸に平行で、上部が無限に続く矩形でいくつかの点を含むことを考える。
この矩形に含まれる点の部分集合の取り方はいくつあるか。

解法

Y座標の大きい順に点を処理していく。
「現在処理している点のうち、Y座標が一番小さいものを1個以上含む矩形」を数え上げればよい。
先に座標圧縮しておけば、BITで各X座標において1個以上点があるかどうかを覚えておくと高速に数え上げられる。

int N;
int X[201010],Y[201010];
vector<int> Xs,Ys;
vector<int> ev[202020];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	void set(int e,V v) { add(e,v-val[e]);}
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};
BIT<int,20> bt;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		Xs.push_back(X[i]);
		Ys.push_back(Y[i]);
	}
	sort(ALL(Xs));
	sort(ALL(Ys));
	Xs.erase(unique(ALL(Xs)),Xs.end());
	Ys.erase(unique(ALL(Ys)),Ys.end());
	FOR(i,N) {
		X[i]=lower_bound(ALL(Xs),X[i])-Xs.begin()+1;
		Y[i]=lower_bound(ALL(Ys),Y[i])-Ys.begin();
		ev[Y[i]].push_back(X[i]);
	}
	
	ll ret=0;
	for(i=200000;i>=0;i--) if(ev[i].size()) {
		sort(ALL(ev[i]));
		unique(ALL(ev[i]));
		FORR(e,ev[i]) bt.set(e,1);
		int pre=0;
		FOR(j,ev[i].size()) {
			
			int lef=bt(ev[i][j]-1)-bt(pre)+1;
			int ri=bt(N+2)-bt(ev[i][j])+1;
			ret+=1LL*lef*ri;
			pre=ev[i][j];
		}
	}
	cout<<ret<<endl;
	
	
}

まとめ

これ1250ptでもいいような…本番10分かかってないぞ。