CSAcademy Round #36 : E. BBox Count

計算量自信なかった解法で合ってた。最後までやればよかった。
https://csacademy.com/contest/round-36/task/bbox-count/

問題

2次元座標上に異なる位置の格子点がN個与えられる。
これらのうち一部を選択してそのBounding Boxを求めるとき、面積が正のBounding Boxは何通りあるか。

解法

Bounding Boxの左端と右端を定めつつ、下端・上端の候補をBITで数え上げていく。
まず、各X座標ごとに登場する格子点をY座標を並べ、昇順にソートしておく。

次に左端x=Lを総当たりしていく。
Lに対し、右端RをL+1から徐々に増加していこう。
その際、BITでL≦x≦Rの範囲にある格子点で、各yに相当するものが1個以上存在するかどうかを数え上げていこう。

X座標xに相当するY座標のソート済み配列をP[x]とする。
P[L]、P[R]、BITを使い、上端下端を数えていこう。
その際、x=Lまたはx=R中の格子点において、Y座標が最も小さくなるものを考え、順次処理していく。

たとえば今P[L][a]＜P[R][b]であり、その前の処理ではpreY＜P[L][a]が処理対象のY座標だったとする。
P[L][a]がx=Lまたはx=R中の格子点においてY座標が最も小さくなり、かつBounding Boxが正の面積を持たなければならない。
その場合、下端はpreY＜y≦P[L][a]、上端はP[R][b]≦yの範囲の格子点を選べばよいので、BITを使い両者に相当する格子点の数を求め掛け合わせよう。

そうしたら次はa++して同様に進めればよい。
P[L][a]==P[R][b]の場合、上端と下端が1以上差がなければならないことに注意。下端がP[L][a]未満なら上端はP[L][a]以上を取れるが、下端がP[L][a]ちょうどなら上端はP[L][a]+1以上でなければならない。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	void clear() {ZERO(bit);};
	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;}
};


vector<int> X[2525];
int N;
ll ret=0;



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	FOR(i,N) {
		cin>>x>>y;
		X[x].push_back(y);
	}
	
	FOR(x,2501) sort(ALL(X[x]));
	
	ll tot=0;
	int L,R;
	FOR(L,2501) if(X[L].size()) {
		BIT<int,13> bt;
		bt.clear();
		FORR(e,X[L]) bt.add(e,1);
		
		for(R=L+1;R<=2500;R++) if(X[R].size()) {
			FORR(e,X[R]) if(bt(e)==bt(e-1)) bt.add(e,1);
			int a=0,b=0,pre=0;
			while(a<X[L].size() && b<X[R].size()) {
				if(X[L][a]<X[R][b]) {
					tot += (bt(2501)-bt(X[R][b]-1)) * (bt(X[L][a])-bt(pre));
					pre = X[L][a];
					a++;
				}
				else if(X[L][a]>X[R][b]) {
					tot += (bt(2501)-bt(X[L][a]-1)) * (bt(X[R][b])-bt(pre));
					pre = X[R][b];
					b++;
				}
				else {
					tot += (bt(2501)-bt(X[L][a]-1)) * (bt(X[R][b]-1)-bt(pre));
					tot += (bt(2501)-bt(X[L][a]));
					pre = X[L][a];
					a++;
					b++;
				}
			}
		}
	}
	cout<<tot<<endl;
	
}

まとめ

O(N^2*logN)で結構重いかと思ったけど、250msで終わった。