JOI 2024/2025 二次予選 : E - 衝突 (Collision)

これは言い換えに気付くまでは難しいな。
https://atcoder.jp/contests/joi2025yo2/tasks/joi2025_yo2_e

問題

長さLの池があり、ランナーが時計回りに回る。
以下の(N+Q)個のクエリに順次答えよ。

• 指定の位置から指定の速度で走るランナーが追加または削除される。
• そのつど、時間Tの間ランナーが走ったとき、衝突の回数を求めよ。なお、クエリ毎にランナーの位置は初期化される。

解法

まずランナーを速度順にソートしておく。
ランナーの追加に対し、衝突回数は以下の加減算で求められる。

• 追加したランナーの時間Tにおける周回数と、他のランナーの時間Tにおける周回数の差
• 初期状態のランナーの位置の転倒数
• 時刻T後のランナーの位置の転倒数

転倒数を高速に求められるよう、平方分割をしておく。
あらかじめランナーを√N+Q個のブロックに分けておき、ブロック内にいるランナーの、周回数の総和と、初期位置・時刻T後の位置を昇順にソートした数列を持っておくと、ブロック毎の周回数の差や転倒数をまとめて計算できる。

ll N,L,T,Q;

ll A[101010],S[101010],D[101010],E[101010];
const ll mo=1000000007;

int delid[101010];
int id[101010],rid[101010];
const int DI=350;
int alive[DI*DI];
int num[DI+1];
vector<int> As[DI+1],Es[DI+1];
ll DS[DI+1];
ll ret=0;

void add(int v) {
	int p=rid[v];
	int block=v/DI;
	int i;
	FOR(i,block) {
		(ret+=D[p]*num[i]-DS[i])%=mo;
		ret-=lower_bound(ALL(As[i]),A[p]+1)-As[i].begin();
		ret+=lower_bound(ALL(Es[i]),E[p]+1)-Es[i].begin();
	}

	for(i=block+1;i<DI;i++) {
		(ret+=DS[i]-D[p]*num[i])%=mo;
		ret-=As[i].end()-lower_bound(ALL(As[i]),A[p]);
		ret+=Es[i].end()-lower_bound(ALL(Es[i]),E[p]);
	}
	for(i=block*DI;i<(block+1)*DI;i++) if(alive[i]) {
		if(i<v) {
			if(A[rid[i]]<=A[p]) ret--;
			if(E[rid[i]]<=E[p]) ret++;
			ret+=D[p]-D[rid[i]];
		}
		else {
			if(A[rid[i]]>=A[p]) ret--;
			if(E[rid[i]]>=E[p]) ret++;
			ret+=D[rid[i]]-D[p];
		}
	}
	alive[v]=1;
	As[block].push_back(A[p]);
	Es[block].push_back(E[p]);
	sort(ALL(As[block]));
	sort(ALL(Es[block]));
	(DS[block]+=D[p])%=mo;
	num[block]++;
}
void del(int v) {
	int p=rid[v];
	int block=v/DI;
	alive[v]=0;
	int i,x;

	FOR(i,block) {
		(ret-=D[p]*num[i]-DS[i])%=mo;
		ret+=lower_bound(ALL(As[i]),A[p]+1)-As[i].begin();
		ret-=lower_bound(ALL(Es[i]),E[p]+1)-Es[i].begin();
	}

	for(i=block+1;i<DI;i++) {
		(ret-=DS[i]-D[p]*num[i])%=mo;
		ret+=As[i].end()-lower_bound(ALL(As[i]),A[p]);
		ret-=Es[i].end()-lower_bound(ALL(Es[i]),E[p]);
	}
	for(i=block*DI;i<(block+1)*DI;i++) if(alive[i]) {
		if(i<v) {
			if(A[rid[i]]<=A[p]) ret++;
			if(E[rid[i]]<=E[p]) ret--;
			ret-=D[p]-D[rid[i]];
		}
		else {
			if(A[rid[i]]>=A[p]) ret++;
			if(E[rid[i]]>=E[p]) ret--;
			ret-=D[rid[i]]-D[p];
		}
	}

	alive[v]=0;
	FOR(i,As[block].size()) if(As[block][i]==A[p]) {
		swap(As[block][i],As[block].back());
		As[block].pop_back();
		sort(ALL(As[block]));
		break;
	}
	FOR(i,Es[block].size()) if(Es[block][i]==E[p]) {
		swap(Es[block][i],Es[block].back());
		Es[block].pop_back();
		sort(ALL(Es[block]));
		break;
	}
	(DS[block]+=mo-D[p])%=mo;
	num[block]--;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L>>T;
	vector<pair<int,int>> Ss;
	map<pair<int,int>,int> ids;
	FOR(i,N) cin>>A[i];
	FOR(i,N) {
		cin>>S[i];
		ids[{A[i],S[i]}]=i;
		Ss.push_back({S[i],i});
	}
	MINUS(delid);
	cin>>Q;
	FOR(i,Q) {
		cin>>A[i+N]>>S[i+N];
		if(ids.count({A[i+N],S[i+N]})) {
			delid[i+N]=ids[{A[i+N],S[i+N]}];
			ids.erase({A[i+N],S[i+N]});
		}
		else {
			ids[{A[i+N],S[i+N]}]=i+N;
			Ss.push_back({S[i+N],i+N});
		}
	}
	FOR(i,N+Q) {
		D[i]=(A[i]+S[i]*T)/L%mo;
		E[i]=(A[i]+S[i]*T)%L;
	}
	sort(ALL(Ss));
	FOR(i,Ss.size()) {
		rid[i]=Ss[i].second;
		id[Ss[i].second]=i;
	}
	
	FOR(i,N+Q) {
		if(delid[i]==-1) {
			add(id[i]);
		}
		else {
			x=delid[i];
			del(id[x]);
			
		}
		
		
		if(i>=N) cout<<(ret%mo+mo)%mo<<endl;
	}
	
}

まとめ

位置関係の面倒くささを、転倒数で置き換えて考えるのは賢いな。
この言い換えは今後も使えそうなので覚えておこう。