VK Cup 2015 Round 1 : C. Rooks and Rectangles

これは周囲の反応の良い問題なのだが、Eで手こずったせいで本番問題すら見なかった。
http://codeforces.com/contest/529/problem/C

問題

N*Mの２次元グリッドがあり、そこでK個のチェスのルーク(将棋でいう飛車)の駒がいるその位置が与えられる。

以下のクエリがQ個与えられる。
各クエリはグリッド上の矩形の範囲(X1,Y1)-(X2,Y2)を示している。
矩形内のすべてのセルについて、矩形内の何れかのルークが到達可能であるかどうかを答えよ。

解法

各クエリに対し条件を満たすには、矩形中で以下のどちらかであればよい。

• 全ての列に１体以上ルークがいる
• 全ての行に１体以上ルークがいる

以下、前者の方の解法を示す。
前者を満たさない場合、盤面を90度回転して同じ解法を繰り返せば、結果的に両方の条件を判定できる。

解法としてはSegTreeと尺取法の要領で行う。
SegTreeでは、各列に置いてルークが登場するもっとも下の行番号を格納する。
このSegTreeで行番号の列間での最小値を取れば、あるX座標の範囲内で最も上にいるルークがわかる。

次に、ルークの位置及びクエリの下端の座標の小さい順に処理を行う。

• ルークが登場した場合、上記SegTreeの値を更新すればよい。
• クエリが登場した場合、SegTreeでX1～X2の範囲で最も上にいるルークを求め、それがY1以上であることを確認すればよい。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=1<<20;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

int H,W,K,Q;
int X[202000],Y[202000];
int X1[202000],Y1[202000];
int X2[202000],Y2[202000];
int ok[202000];
vector<int> evR[210000],evQ[210000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>W>>H>>K>>Q;
	FOR(i,K) cin>>X[i]>>Y[i];
	FOR(i,Q) cin>>X1[i]>>Y1[i]>>X2[i]>>Y2[i];
	
	FOR(k,2) {
		SegTree_1<int,1<<20> miny;
		FOR(i,210000) evR[i].clear(),evQ[i].clear();
		FOR(i,K) evR[Y[i]].push_back(i);
		FOR(i,Q) evQ[Y2[i]].push_back(i);
		for(i=1;i<=W;i++) miny.update(i,0);
		for(i=1;i<=H;i++) {
			FORR(r,evR[i]) miny.update(X[r],i);
			FORR(r,evQ[i]) ok[r] |= miny.getval(X1[r],X2[r]+1)>=Y1[r];
		}
		
		swap(W,H);
		FOR(i,K) swap(X[i],Y[i]);
		FOR(i,Q) swap(X1[i],Y1[i]);
		FOR(i,Q) swap(X2[i],Y2[i]);
	}
	FOR(i,Q) cout << (ok[i]?"YES":"NO") << endl;
	
}

まとめ

わかってしまえばなかなかシンプルな解法で良い。
90度回して繰り返すのもいいね。