Codeforces ECR #068 : E. Count The Rectangles

これは比較的簡単かな…。
http://codeforces.com/contest/1194/problem/E

問題

X軸またはY軸に平行な線分がN個与えられる。
平行な線分は互いに共通部分を持たないものとする。

4つの線分を選び、それらで(辺がはみ出てもよいの)四角形を何個構築できるか。

解法

縦棒1本毎に、その左側にある「横棒の開始」と、右側にある「右辺となる縦棒」「横棒の終了」をX座標順に走査していこう。
存在する横棒の数を、BITでY座標毎にカウントできるようにすればO(N^2logN)で数え上げられる。

int N;
vector<pair<int,int>> V[10101];

vector<pair<int,int>> add[10101];
vector<int> del[10101];

template<class V, int ME> class BIT {
public:
	V bit[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) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,14> bt;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		x1+=5001;
		y1+=5001;
		x2+=5001;
		y2+=5001;
		if(x1>x2) swap(x1,x2);
		if(y1>y2) swap(y1,y2);
		
		if(x1==x2) V[x1].push_back({y1,y2});
		else add[x1].push_back({y1,x2});
	}
	ll ret=0;
	FOR(x,10002) FORR(v,V[x]) {
		for(i=0;i<=10002;i++) del[i].clear();
		for(i=0;i<=x;i++) {
			FORR(a,add[i]) {
				bt.add(a.first,1);
				del[a.second].push_back(a.first);
			}
			FORR(a,del[i]) bt.add(a,-1);
		}
		for(i=x+1;i<=10002;i++) {
			FORR(vv,V[i]) {
				int y1=max(v.first,vv.first);
				int y2=min(v.second,vv.second);
				if(y2>y1) {
					int num=bt(y2)-bt(y1-1);
					ret+=1LL*num*(num-1)/2;
				}
			}
			
			FORR(a,del[i]) bt.add(a,-1);
		}
	}
	cout<<ret<<endl;
}

まとめ

本番ここまではさっくりと行ったのにね。