AtCoder ARC #141 : E - Sliding Edge on Torus

問題設定がややこしい。
https://atcoder.jp/contests/arc141/tasks/arc141_e

問題

N^2個の頂点からなる無向グラフを考える。
0以上N未満の値i,jを用いて、(i,j)で1つの頂点を差すものとする。

以下のクエリを順次行い、その都度、連結成分の個数を求めよ。

• 整数A,B,C,Dが与えられる。0≦k＜Nに対し、((A+k)%N,(B+k)%N)と((C+k)%N,(D+k)%N)の間に辺を張る。

解法

(i,j)→(i-j,i)と座標変換すると、クエリはU,V,Pに対し(U,k)と(V,(P+k)%N)間に辺を張るように言い換えられる。
以下、座標変換後の座標(i,j)を、i行目j列目の点と呼ぶ。
この時iごとにオフセットH[i]を定め、(i,j)→(i,j+H[i])と座標変換しても解には影響しない。

そこでまずいったんクエリを走査し、新たに異なる行同士が連結されるとき、P=0とみなせるようにオフセットを定めよう。

あとは、1行あたり何個の連結成分に分解されるかを保持しながら、再度クエリをたどろう。
この値をG(i)とする。

• 新たに異なる行U,V同士が連結される場合
  • G(U)=G(V)=GCD(G(U),G(V))となる。
• すでに行同士でいえば連結であるU,Vを対象とする場合。
  • G(U)=G(V)=GCD(G(U),P,N)となる。

int N,Q;
int A[202020],B[202020],C[202020],D[202020];
int H[202020];
vector<pair<int,int>> E[202020];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<202020> uf;
int G[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,Q) {
		cin>>A[i]>>B[i]>>C[i]>>D[i];
		A[i]=(A[i]-B[i]+N)%N;
		C[i]=(C[i]-D[i]+N)%N;
		B[i]=(D[i]-B[i]+N)%N;
		swap(B[i],C[i]);
		
		if(uf[A[i]]==uf[B[i]]) {
			D[i]=1;
		}
		else {
			E[A[i]].push_back({B[i],N-C[i]});
			E[B[i]].push_back({A[i],C[i]});
			uf(A[i],B[i]);
			D[i]=0;
		}
	}
	
	MINUS(H);
	FOR(i,N) if(H[i]==-1) {
		H[i]=0;
		queue<int> Q;
		Q.push(i);
		while(Q.size()) {
			int cur=Q.front();
			Q.pop();
			FORR2(e,d,E[cur]) if(H[e]==-1) {
				H[e]=(H[cur]+d)%N;
				Q.push(e);
			}
		}
	}
	
	uf.reinit(N);
	ll ret=1LL*N*N;
	FOR(i,N) G[i]=N;
	
	FOR(i,Q) {
		if(D[i]==0) {
			x=uf[A[i]];
			y=uf[B[i]];
			ret-=G[x];
			ret-=G[y];
			G[x]=G[y]=__gcd(G[x],G[y]);
			uf(x,y);
			ret+=G[x];
			
		}
		else {
			x=uf[A[i]];
			y=uf.count(A[i]);
			ret-=G[x];
			k=(H[B[i]]-H[A[i]]+C[i]+N)%N;
			G[x]=__gcd(__gcd(G[x],k),N);
			ret+=G[x];
		}
		cout<<ret<<endl;
	}
	
	
}

まとめ

解法を知ってしまうと難しくないが、これを初見で考察するのは結構厳しいな。