TopCoder SRM 840 : Div1 Easy Div2 Hard Postcards

EasyでもMediumでもコーナーケース落としてしんどい。
https://community.topcoder.com/stat?c=problem_statement&pm=17876

問題

N個の町があり、i番の町にはi人が住んでいる。
以下、Y個の道路建設計画が与えられる。
各計画ではある2つの町をつなぐ道路が設置される。

それぞれ道路後、各人は道路をたどって移動できる範囲の町の町人に1通ずつ手紙を送る。
各タイミングで送る手紙の総和を求めよ。

解法

初期状態における手紙の送付数を求めた後、道路が1個設置されるごとに差分がどうなるかを考えよう。
これは道路が設置される街を座標圧縮したうえで、Union-Findで連結成分内の町人数をカウントしていくとよい。
途中、連結成分内の町人数が2^32を超えることがあるので注意。

const ll mo=1000000007;
ll A[202020],B[202020];

ll C[402020];
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;
	}
};
ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}
class Postcards {
	public:
	int count(int N, int Y, int seed) {
		ll state = seed;
		int i;
		UF<402020> uf;
		vector<int> V;
		FOR(i,Y) {
			state = (state * 1103515245 + 12345)%(1LL<<31);
			A[i] = state % N;
			state = (state * 1103515245 + 12345)%(1LL<<31);
			B[i] = state % N;
			V.push_back(A[i]);
			V.push_back(B[i]);
		}
		sort(ALL(V));
		V.erase(unique(ALL(V)),V.end());
		ll ret=0;
		ll pat=1LL*N*(N+1)%mo*(2*N+1)%mo*modpow(6)-1LL*N*(N+1)/2%mo;
		pat=(pat%mo+mo)%mo;
		
		
		FOR(i,V.size()) C[i]=V[i]+1;
		FOR(i,Y) {
			ll a=lower_bound(ALL(V),A[i])-V.begin();
			ll b=lower_bound(ALL(V),B[i])-V.begin();
			a=uf[a];
			b=uf[b];
			if(a!=b) {
				pat-=(C[a]*(C[a]-1)+C[b]*(C[b]-1))%mo;
				C[a]=C[b]=(C[a]+C[b])%mo;
				uf(a,b);
				pat+=C[a]*(C[a]-1);
				pat=(pat%mo+mo)%mo;
			}
			ret+=pat%mo;
			
		}
		return ret%mo;
	}
}

まとめ

本番見事に注意不足で落とした。