Codeforces #317 Div1 D. Campus

最初題意を掴むのに手間取った。
http://codeforces.com/contest/571/problem/D

問題

1～N番のN個の学生寮がある。
各寮は1つの大学に属しており、かつ1つの軍の募兵対象となる。
初期状態では、i番の寮はi番の大学に属しており、i番の軍の募兵対象である。
(大学と軍は直接関係ない)

以下の5種類で構成されるQ個のクエリを順に処理せよ。

• A番の大学がB番の大学をマージする。B番の大学に属す寮はすべてA番の大学に属す。
• C番の軍がD番の軍をマージする。D番の軍の募兵対象の寮はすべてC番の軍の募兵対象となる。
• X番の大学の寮に新規に大学生が増える。大学にa個の寮がある場合、各寮にa人ずつ増える。
• Y番の軍が募兵を行い、対象の寮の学生はすべて0人になる。
• 現在Q番の寮にいる学生数を答える。

解法

マージ処理を連続する区間の連結にしたい。
そうすると寮の大学生増加クエリがSegTreeの区間加算で処理できるようになる。

よってまずクエリを先読みして1周し、大学マージクエリを行う。
各大学に属す寮を配列で表現しておき、マージクエリの際は両者を連結するようにする。
その際、小さい方の配列をコピーするテクを用いることで、コピーコストを減らすことができる。
大学マージクエリを処理したのち、各大学の寮を通し番号で1から連番で振り直す。
そうすると、大学に属す寮は常に連番なので、区間で表現できるようになる。

軍のマージクエリについても同様に1周処理して連番を振り直す。

問題は大学と軍のマージの内容は異なるため、連番の振り方も異なることである。
大学に属す寮の連番で寮を表現処理すると、大学生増加クエリはSegTreeで簡単に処理できるが軍の募兵クエリが処理できない。

よってこの問題の学生数を問うクエリを以下のように読み替える。
「最後に募兵されたときの学生数と、クエリ時の学生数の差を求めよ」
こうすると各学生数クエリに対し、最後に募兵されたときの学生数を覚えておけば良くなる。
軍のマージクエリにより連番を求めたのち、もう1周区間の連結で軍のマージクエリを処理していくと、募兵クエリにおいて募兵対象の区間も定まる。

さらに1周、今度は逆順でクエリを処理する。
今度は学生数クエリと募兵クエリを処理する。
学生数クエリに遭遇すると、対象の寮両番号を「直前の募兵クエリ未確定集合」に格納する。
募兵クエリに遭遇すると、募兵対象の区間はすでにわかっているので、「直前の募兵クエリ未確定集合」内に対象の寮があれば、その学生数クエリを覚えておく。

最後にクエリをもう1周する。
大学マージクエリは区間連結するだけだし、大学生増加クエリはSegTreeの区間加算をすればよい。
募兵クエリに対しては、左記の逆順処理でその後に登場する学生数クエリの番号がわかっているので、SegTreeを見て現時点の寮の学生数を学生数クエリ毎に覚えておく。
学生数クエリに対しては、SegTreeを見て現時点の寮の学生数を求めたのち、過去に募兵クエリがあったならその時の学生数を引けばよい。

template<class V, int ME> class BIT_r {
public:
	V bit[2][1<<ME];
	BIT_r(){clear();};
	void clear() {ZERO(bit);};
	
	void update(int entry, V val0, V val1) {
		entry++;
		while(entry <= 1<<ME) bit[0][entry-1]+=val0, bit[1][entry-1] += val1, entry += entry & -entry;
	}
	V total(int entry) {
		int e=entry++;
		V v0=0,v1=0;
		while(entry>0) v0+=bit[0][entry-1], v1+=bit[1][entry-1], entry -= entry & -entry;
		return e*v0+v1;
	}
	void add(int L, int R, V val) { // add val to L<=x<=R
		update(L,val,-val*(L-1));
		update(R+1,-val,val*R);
	}
};

int N,M;
vector<int> UD[505050];
vector<int> MD[505050];
char C[505050];
int X[505050],Y[505050];
int revUD[505050], revMD[505050];
pair<int,int> UDP[505050],MDP[505050];
pair<int,int> reset[505050];
ll ret[505050];
vector<int> PQ[505050];
BIT_r<ll,23> bt;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) UD[i+1].push_back(i+1),MD[i+1].push_back(i+1);
	
	FOR(i,M) {
		cin>>C[i]>>X[i];
		if(C[i]=='U') {
			cin>>Y[i];
			if(UD[X[i]].size()<UD[Y[i]].size()) {
				UD[Y[i]].insert(UD[Y[i]].end(),UD[X[i]].begin(),UD[X[i]].end());
				swap(UD[X[i]],UD[Y[i]]);
			}
			else {
				UD[X[i]].insert(UD[X[i]].end(),UD[Y[i]].begin(),UD[Y[i]].end());
			}
			UD[Y[i]].clear();
		}
		if(C[i]=='M') {
			cin>>Y[i];
			if(MD[X[i]].size()<MD[Y[i]].size()) {
				MD[Y[i]].insert(MD[Y[i]].end(),MD[X[i]].begin(),MD[X[i]].end());
				swap(MD[X[i]],MD[Y[i]]);
			}
			else {
				MD[X[i]].insert(MD[X[i]].end(),MD[Y[i]].begin(),MD[Y[i]].end());
			}
			MD[Y[i]].clear();
		}
	}
	x=y=0;
	for(i=1;i<=N;i++) FORR(r,UD[i]) revUD[r]=++x;
	for(i=1;i<=N;i++) FORR(r,MD[i]) revMD[r]=++y;
	for(i=1;i<=N;i++) UDP[i]={revUD[i],revUD[i]},MDP[i]={revMD[i],revMD[i]};
	FOR(i,M) {
		if(C[i]=='M') {
			assert(MDP[X[i]].second+1==MDP[Y[i]].first || MDP[Y[i]].second+1==MDP[X[i]].first);
			MDP[X[i]].first=min(MDP[X[i]].first,MDP[Y[i]].first);
			MDP[X[i]].second=max(MDP[X[i]].second,MDP[Y[i]].second);
		}
		if(C[i]=='Z') reset[i]=MDP[X[i]];
	}
	set<pair<int,int> > QE;
	for(i=M-1;i>=0;i--) {
		if(C[i]=='Q') QE.insert({revMD[X[i]],i});
		if(C[i]=='Z') {
			for(auto it=QE.lower_bound({reset[i].first,0}); it!=QE.end() && it->first<=reset[i].second;) {
				PQ[i].push_back(it->second);
				QE.erase(it++);
			}
		}
	}
	FOR(i,M) {
		if(C[i]=='U') {
			assert(UDP[X[i]].second+1==UDP[Y[i]].first || UDP[Y[i]].second+1==UDP[X[i]].first);
			UDP[X[i]].first=min(UDP[X[i]].first,UDP[Y[i]].first);
			UDP[X[i]].second=max(UDP[X[i]].second,UDP[Y[i]].second);
		}
		if(C[i]=='Z') {
			FORR(r,PQ[i]) ret[r]=bt.total(revUD[X[r]])-bt.total(revUD[X[r]]-1);
		}
		if(C[i]=='A') {
			bt.add(UDP[X[i]].first,UDP[X[i]].second,UDP[X[i]].second-UDP[X[i]].first+1);
		}
		if(C[i]=='Q') {
			cout<<bt.total(revUD[X[i]])-bt.total(revUD[X[i]]-1)-ret[i]<<endl;
		}
	}
	
}

まとめ

クエリ4周もしたの初めて。