World CodeSprint 13 : E. Competitive Teams

これも平方分割の一種なのかな。
https://www.hackerrank.com/contests/world-codesprint-13/challenges/competitive-teams

問題

N人の人が、初期状態では１人でチームを構成している。
以下のクエリを順次処理せよ。

• 指定された２人が属するチームが異なるなら、マージする。
• 整数Cが与えられる。人数差がC以上になるチーム対の総数を答えよ。

解法

マージ処理はUnion-Findでいいとして、人数毎のチーム数をmapで処理しよう。
するとmapのエントリ数は高々O(√N)通りである。
後者のクエリはmapの要素に対し尺取り法を使えばO(√N)で解けるので、結局O(Q√N)で解ける。

int N,M;
map<int,int> V;

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 i; FOR(i,um) 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;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	V[1]=N;
	G=N;
	while(M--) {
		cin>>i;
		if(i==1) {
			cin>>x>>y;
			if(uf[x]!=uf[y]) {
				
				j=uf.count(x)+uf.count(y);
				if(--V[uf.count(x)]==0) V.erase(uf.count(x));
				if(--V[uf.count(y)]==0) V.erase(uf.count(y));
				G--;
				uf(x,y);
				V[uf.count(x)]++;
			}
		}
		else {
			int c;
			cin>>c;
			ll ret=0;
			if(c) {
				auto it=V.begin();
				int r=0;
				FORR(v,V) {
					while(it->first<=v.first-c) {
						r+=it->second;
						it++;
					}
					ret+=1LL*v.second*r;
				}
				
			}
			else {
				ret=1LL*G*(G-1)/2;
			}
			cout<<ret<<endl;
		}
	}
}

まとめ

このパターンの平方分割？はしばしば見るね。