CSAcademy Round #77 : E. Rooks

Div2 Eっぽい無駄に実装が面倒な問題。
https://csacademy.com/contest/round-77/task/rooks/

問題

H*Wの2次元グリッドがある。
うちK個のセルにはチェスのルークの駒が置かれている。

ここでQ個のクエリが与えられる。
各クエリはグリッド中の矩形領域を示す。
領域内のセルのうち、領域内のルークで1手で到達可能なセルはいくつあるか。

解法

矩形領域のサイズをR*Cとする。
うち、ルークが1個以上ある行がR'行、1個以上ある列がC'行あったとする。
するとルークが1手で到達できないセルは(R-R')*(C-C')なので、R*Cからそれを引けば解となる。

あとはR'とC'をそれぞれ求めればよい。
これは独立に求めることができる。

以下C'の求め方を考える。
領域の上端と下端を管理し、各列において上端と下端の間に何個のルークがあるかを管理しよう。
BITを併用し、1個以上ルークがある列に1をセットすることで、列の区間においてルークがある列の数を高速に数え上げることができる。
上端と下端はMo's Algorithmを使いながら1ずつずらしていくとよい。

縦横を逆にするとR'も同様に求められる。

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;}
};

int H,W,K,Q;
int X[101010],Y[101010];
vector<int> RR[303030];
vector<int> RC[303030];
int U[303030],L[303030],D[303030],R[303030];
const int DI=200;
vector<pair<int,int>> evUD[200], evLR[200];
int NC[303030],NR[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K>>Q;
	FOR(i,K) {
		cin>>Y[i]>>X[i];
		RR[Y[i]].push_back(X[i]);
		RC[X[i]].push_back(Y[i]);
	}
	FOR(i,Q) {
		cin>>U[i]>>L[i]>>D[i]>>R[i];
		D[i]++;
		R[i]++;
		evUD[U[i]/DI].push_back({D[i],i});
		evLR[L[i]/DI].push_back({R[i],i});
	}
	FOR(i,200) if(evUD[i].size()) {
		BIT<int,16> bt;
		ZERO(bt.bit);
		sort(ALL(evUD[i]));
		int cnt[30303]={};
		
		int UU=i*DI,DD=i*DI;
		FORR(e,evUD[i]) {
			while(DD<e.first) {
				FORR(r,RR[DD]) if(++cnt[r]==1) bt.add(r,1);
				DD++;
			}
			while(UU<U[e.second]) {
				FORR(r,RR[UU]) if(--cnt[r]==0) bt.add(r,-1);
				UU++;
			}
			while(U[e.second]<UU) {
				UU--;
				FORR(r,RR[UU]) if(++cnt[r]==1) bt.add(r,1);
			}
			NC[e.second]=bt(R[e.second]-1)-bt(L[e.second]-1);
		}
	}
	FOR(i,200) if(evLR[i].size()) {
		BIT<int,16> bt;
		ZERO(bt.bit);
		sort(ALL(evLR[i]));
		int cnt[30303]={};
		
		int LL=i*DI,RR=i*DI;
		FORR(e,evLR[i]) {
			while(RR<e.first) {
				FORR(r,RC[RR]) if(++cnt[r]==1) bt.add(r,1);
				RR++;
			}
			while(LL<L[e.second]) {
				FORR(r,RC[LL]) if(--cnt[r]==0) bt.add(r,-1);
				LL++;
			}
			while(L[e.second]<LL) {
				LL--;
				FORR(r,RC[LL]) if(++cnt[r]==1) bt.add(r,1);
			}
			NR[e.second]=bt(D[e.second]-1)-bt(U[e.second]-1);
		}
	}
	
	FOR(i,Q) {
		cout<<(R[i]-L[i])*(D[i]-U[i])-(R[i]-L[i]-NC[i])*(D[i]-U[i]-NR[i])<<endl;
	}
	
	
}

まとめ

方針は割とすぐに思いついたけど、最初計算量が心配になってしばらく唸ってた。
その後幅・高さが10^5より小さ目なことに気が付いてなんとか通した。