kmjp's blog

競技プログラミング参加記です

Codeforces ECR #062 : F. Extending Set of Points

Codeforces

ECRの後半は、方針が立っても実装が重いものが多い気がするなぁ。
https://codeforces.com/contest/1140/problem/F

問題

２次元座標上で、格子点の位置に点を追加・削除するクエリが与えられる。

今ある点の集合をSとする。
３点が、軸に平行な長方形の３頂点に位置するとき、残る１点をSに追加する、という処理をそれ以上点が増えなくなるまで続けた場合を仮定し、その状態の点の集合をE(S)とする。
Sの変化に対し、E(S)を随時答えよ。

解法

まず、点の追加だけの場合を考える。
X座標とY座標に対応する点群からなる二部グラフを考える。
Sへの点の追加とは、X座標とY座標に対応する辺が追加されるものだとみなそう。

このグラフにおいて、長さ３のパスがあった場合、それは問題に示す３頂点の組み合わせがあることに相当する。
よってE(S)に対応するグラフを考えると、そのパスの両端を結ぶ辺を追加することに相当する。
また、E(S)が変化なくなるまで辺を増やすと、結局Sに対応するグラフにおける連結成分では、要素間にフルメッシュで辺が張られることになる。
よって、各連結成分に対し、(X座標に対応する点の数)と(Y座標に対応する点の数)の積の総和が解となる。

なので、点の追加クエリだけなら、UnionFindを使い、そこに(X座標に対応する点の数)と(Y座標に対応する点の数)を持つようにしてその積和を更新していけば、解ける。

この上で削除クエリを考えよう。
削除の順番は追加順とは異なるので、良くある巻き戻し可能なUnion-Findは使えない。
そこで、その点が追加されている区間を時系列で考える。

そこでSegTreeを考える。このSegTreeはクエリ実行順の時間をKeyとし、そのNodeにその時間の間有効である辺を載せることにする。
つまり、１個の辺が有効な区間を、SegTreeを用いて複数の時間区間に分割することにする。
あとはこのSegTree上をDFS順で辿るようにすれば、巻き戻し可能なUnion-Findで処理できる。

なお、このテクはyukicoderのwikiに記載済みとcamypaperさんから教えていただきました。知らんかった…。
Decomposable searching problem - オフラインの場合 Wiki - yukicoder

int Q;
int X[303030],Y[303030];
ll cur;
map<pair<int,int>,int> m;
ll ret[(1<<19)+5];

template<int um> class UF_pop {
	public:
	vector<int> par,rank,Xs,Ys; vector<vector<int>> hist;
	UF_pop() {par=rank=Xs=Ys=vector<int>(um,0); for(int i=0;i<um;i++) par[i]=i;
		for(int i=0;i<300000;i++) Xs[i]=1,Ys[i+300000]=1;
	}
	void reinit() {int i; FOR(i,um) rank[i]=0,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):operator[](par[x]);}
	void pop() {
		if(hist.size()) {
			auto a=hist.back();
			hist.pop_back();
			par[a[0]]=a[1]; rank[a[0]]=a[2]; Xs[a[0]]=a[3]; Ys[a[0]]=a[4];
			par[a[5]]=a[6]; rank[a[5]]=a[7]; Xs[a[5]]=a[8]; Ys[a[5]]=a[9];
			cur-=1LL*(Xs[a[0]]+Xs[a[5]])*(Ys[a[0]]+Ys[a[5]]);
			cur+=1LL*Xs[a[0]]*Ys[a[0]]+1LL*Xs[a[5]]*Ys[a[5]];
		}
	}
	void operator()(int x,int y) {
		x=operator[](x); y=operator[](y);
		hist.push_back({x,par[x],rank[x],Xs[x],Ys[x],y,par[y],rank[y],Xs[y],Ys[y]});
		if(x==y) return;
		if(rank[x]<rank[y]) par[x]=y;
		else rank[x]+=(rank[x]==rank[y]), par[y]=x;
		cur-=1LL*Xs[x]*Ys[x]+1LL*Xs[y]*Ys[y];
		cur+=1LL*(Xs[x]+Xs[y])*(Ys[x]+Ys[y]);
		Xs[x]=Xs[y]=Xs[x]+Xs[y];
		Ys[x]=Ys[y]=Ys[x]+Ys[y];
	}
};
UF_pop<606060> uf;

template<int NV> class SegTree_2 {
public:
	vector<vector<pair<int,int>>> ev;
	SegTree_2(){ev.resize(NV*2);};
	
	void update(int x,int y, pair<int,int> e,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			ev[k].push_back(e);
		}
		else if(l < y && x < r) {
			update(x,y,e,l,(l+r)/2,k*2);
			update(x,y,e,(l+r)/2,r,k*2+1);
		}
	}
	
	void dfs(int k=1,int L=0,int R=NV) {
		int num=0;
		FORR(e,ev[k]) {
			if(uf[e.first]!=uf[e.second]) {
				uf(e.first,e.second);
				num++;
			}
		}
		if(L+1==R) {
			ret[L+1]=cur;
		}
		else {
			dfs(k*2,L,(L+R)/2);
			dfs(k*2+1,(L+R)/2,R);
		}
		while(num--) uf.pop();
	}
};
SegTree_2<1<<19> st;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	FOR(i,Q) {
		cin>>X[i]>>Y[i];
		X[i]--;
		Y[i]--;
		Y[i]+=300000;
		if(m.count({X[i],Y[i]})) {
			st.update(m[{X[i],Y[i]}],i,{X[i],Y[i]});
			m.erase({X[i],Y[i]});
		}
		else {
			m[{X[i],Y[i]}]=i;
		}
	}
	FORR(e,m) {
		st.update(e.second,Q+1,e.first);
	}
	st.dfs();
	
	FOR(i,Q) cout<<ret[i+1]<<" ";
	cout<<endl;
	
}

まとめ

本番も削除ができない…とずっと唸ってました。