Codeforces #1048 : Div1. D. Antiamuny and Slider Movement

これは解き切れず…。
https://codeforces.com/contest/2138/problem/D

問題

長さMの数直線上に、N個のブロックがあり、それぞれの初期位置A[i]が与えられる。
各ブロックのサイズは1である。

ここでQ個のクエリが行われる。
各クエリqは、I[q]個目のブロックを、位置X[q]に移動させるものである。
その際、ブロックを右に動かす場合、途中にあるブロックは押されて同様に右に動く。
同じく、ブロックを左に動かす場合、途中にあるブロックは押されて同様に左に動く。

クエリの順番を入れ替え、Q!通りの順番を考える。
i番目のブロックについて、Q!通りのクエリ順の実行後の最後の位置の総和を答えよ。

解法

ブロックのサイズが1だと思うとややこしいので、あらかじめサイズを0に圧縮してB[i]=A[i]-iとした数列Bの増減を考える。
クエリでB[l]をXまで増やす方向に移動する場合、l＜jに対しB[j]=max(B[j],X)となる。減らす場合も同じような処理が行われる。

各ブロック・各位置に対し、その位置またはその右側にとどまるケースを数え上げて行こう。
その階差を取れば各位置にとどまるケースを数え上げられる。

int T,N,M,Q;
int A[5050];
int X[5050],V[5050];
ll dp[5050];
const ll mo=1000000007;

const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
ll comb(ll N_, ll C_) {
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
int okd[5050],ngd[5050],noned[5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;

	cin>>T;
	while(T--) {
		cin>>N>>M>>Q;
		
		
		FOR(i,N) {
			cin>>A[i];
			A[i]-=i+1;
		}
		FOR(i,Q) {
			cin>>X[i]>>V[i];
			V[i]-=X[i];
			X[i]--;
		}
		
		vector<int> Xs;
		FOR(j,Q) Xs.push_back(V[j]);
		sort(ALL(Xs));
		Xs.erase(unique(ALL(Xs)),Xs.end());
		FOR(i,N) {
			int push=0;
			//一切動かない
			FOR(j,Q) {
				if(X[j]==i) push++;
				if(X[j]<i&&V[j]>A[i]) push++;
				if(X[j]>i&&V[j]<A[i]) push++;
			}
			
			if(push==0) {
				cout<<fact[Q]*(A[i]+i+1)%mo<<" ";
				continue;
			}
			
			ZERO(okd);
			ZERO(ngd);
			ZERO(noned);
			
			FOR(k,Q) {
				if(X[k]==i) {
					ngd[0]++;
					x=lower_bound(ALL(Xs),V[k])-Xs.begin();
					ngd[x]--;
					okd[x]++;
				}
				if(X[k]<i) {
					ngd[0]++;
					x=lower_bound(ALL(Xs),V[k])-Xs.begin();
					ngd[x]--;
					noned[x]++;
				}
				if(X[k]>i) {
					noned[0]++;
					x=lower_bound(ALL(Xs),V[k])-Xs.begin();
					noned[x]--;
					okd[x]++;
				}
			}
			
			
			
			FOR(j,Xs.size()) {
				okd[j+1]+=okd[j];
				ngd[j+1]+=ngd[j];
				noned[j+1]+=noned[j];
				
				if(ngd[j]==0) {
					if(A[i]<=Xs[j] || okd[j]) dp[j]=fact[Q];
					else dp[j]=0;
				}
				else if(okd[j]==0) {
					dp[j]=0;
				}
				else {
					// noneは影響しない
					// ngはokの後に来ない
					dp[j]=comb(Q,noned[j])*fact[noned[j]]%mo*comb(Q-noned[j]-1,ngd[j])%mo*fact[ngd[j]]%mo*fact[okd[j]]%mo;
					if(j+1==Xs.size()) assert(dp[j]==fact[Q]);
				}
			}
			ll ret=0;
			for(j=Xs.size()-1;j>=0;j--) {
				if(j) (dp[j]+=mo-dp[j-1])%=mo;
				(ret+=dp[j]*(Xs[j]+i+1))%=mo;
			}
			
			
			cout<<ret<<" ";
		}
		cout<<endl;
		
		
		
	}
}

まとめ

大きさのあるブロックを動かす問題、Codeforcesに多いイメージ。