AtCoder ABC #179 : F - Simplified Reversi

ACLは前提なのかどうなのか。
https://atcoder.jp/contests/abc179/tasks/abc179_f

問題

N*Nの盤面で行う制限付きリバーシを考える。
中央部(N-2)*(N-2)の領域は黒石が置かれており、最下段と最右列は白石で埋まっている。
ここで、最左列と最上段のうち、左上角以外のマスに白石を置くクエリが与えられる。
このリバーシでは、縦または横で白石に挟まれた黒石が白石になるとする。

最終的に何個黒石が残るか求めよ。

解法

区間に対し最小値を更新し、点に対しその最小値を得るSegTreeを2つ作ろう。
一つは各列における白石のある最上段を管理し、もう一つは各段における白石のある最差列を管理する。
上または左に置いた白石によりどこの白石との間が反転するか、このSegTreeによって求まる。
そしたら反転した黒石数を計上しつつ、もう片方のSegTreeを適宜更新しよう。

int N,Q;

template<class V,int NV> class SegTree_2 {
public:
	V nolink;
	vector<V> val;
	SegTree_2(){val.resize(NV*2); clear(); nolink=1<<30;};
	void clear() { for(int i=0;i<NV*2;i++) val[i]=1<<20; }
	
	V getval(int k) {
		int e=k+NV;
		V ret=nolink;
		while(e>=1) ret=min(ret,val[e]), e/=2;
		return ret;
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) val[k]=min(val[k],v);
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
		}
	}
};

SegTree_2<int,1<<20> Xs,Ys;



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	Xs.update(1,N,N);
	Ys.update(1,N,N);
	ll ret=1LL*(N-2)*(N-2);
	
	while(Q--) {
		cin>>i>>x;
		
		if(i==1) {
			y=Ys.getval(x);
			ret-=y-2;
			Xs.update(1,y,x);
		}
		else {
			y=x;
			x=Xs.getval(y);
			ret-=x-2;
			Ys.update(1,x,y);
		}
	}
	
	cout<<ret<<endl;
	
	
}

まとめ

危うくオ〇ロと書きそうになってしまった、あれ商標だったね。
これ最小値が階段状になるのでmapでも解けなくはないけど、ACLは使う前提なのかな？