题解：CF2138D Antiamuny and Slider Movement
MaxBlazeResFire
·
·
题解
$\rm Observation2$：这要求不能有太多的可选 $x$。考虑一次操作（以向左为例）$j\rightarrow x$，它对 $i$ 号块位置的影响形如：$x_i\leftarrow\min\{x_i,x-(j-i)\}$，是 $\rm chkmin$ 或者 $\rm chkmax$ 操作的形式。
也即，枚举 $i$ 后，它最终能停到的位置最多有 $q+1$ 种，且观察操作，它每一次的参数都只与操作本身有关。把所有 $x-(j-i)$ 或 $x$ 或 $x+(i-j)$ 记为关键点，拿出来排序，记为新数列 $t_i$。每次操作形如，把 $x_i$ 对特定值 $t_j$ 进行 $\rm chkmin$ 或者 $\rm chkmax$，或者移动到指定位置。
但还是不好计算最终恰好停留在 $t_j$ 上的方案数。考虑转化成对于每个 $j$，计算操作完后 $x_i\leq t_j$ 的方案数，然后做差分求得恰好 $x_i=t_j$ 的方案数。
考虑怎样排列操作序列可以使得最终 $x_i\leq t_j$。把所有 $\rm chkmax$ 操作（有 $A$ 个）与 $\rm chkmin$ 操作（有 $B$ 个），移动到指定位置（有 $C$ 个）按参数各自排序，记 $\rm chkmax$ 操作中参数严格大于 $t_j$ 的有 $a$ 个，$\rm chkmin$ 操作中参数不大于 $t_j$ 的有 $b$ 个，移动到指定位置操作中参数不大于 $t_j$ 的有 $c$ 个，那么在长度为 $q=A+B+C$ 的操作序列中，有 $a+b+C$ 个关键位置，$a+C-c$ 个红色点和 $b+c$ 个绿色点，形如要求最后一个红色点右侧至少有一个绿色点。这个的方案数就很好计算了，无脑一点就是 $\displaystyle\binom{A+B+C}{a+b+C}\binom{a+b+C-1}{a+C-c}(A+B+C-a-b-C)!(a+C-c)!(b+c)!$。
还要根据初始位置的变化，考虑一些方案数为 $q!$ 或 $0$ 的特殊情况。
复杂度 $O(nq\log q)$。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define MAXN 5005
#define int long long
#define mod 1000000007
int n,m,q,pos[MAXN],J[MAXN],X[MAXN],fac[MAXN],inv[MAXN],ifac[MAXN];
int maxx[MAXN],minn[MAXN],sett[MAXN],A,B,C,Xs[MAXN];
int cnta[MAXN],cntb[MAXN],cntc[MAXN],res[MAXN];
inline int Bino( int n , int m ){ return n >= 0 && m >= 0 && n >= m ? fac[n] * ifac[m] % mod * ifac[n - m] % mod : 0; }
inline void chkadd( int &x , int k ){ x += k; if( x >= mod ) x -= mod; }
inline void chkequ( int &x , int k ){ x = k; if( x >= mod ) x -= mod; }
inline void solve(){
scanf("%lld%lld%lld",&n,&m,&q);
for( int i = 1 ; i <= n ; i ++ ) scanf("%lld",&pos[i]);
for( int i = 1 ; i <= q ; i ++ ) scanf("%lld%lld",&J[i],&X[i]);
for( int id = 1 ; id <= n ; id ++ ){
A = B = C = 0;
for( int j = 1 ; j <= q ; j ++ ){
if( J[j] < id ) maxx[++A] = X[j] + ( id - J[j] );
if( J[j] > id ) minn[++B] = X[j] - ( J[j] - id );
if( J[j] == id ) sett[++C] = X[j];
}
int cnt = 0;
for( int i = 1 ; i <= A ; i ++ ) Xs[++cnt] = maxx[i];
for( int i = 1 ; i <= B ; i ++ ) Xs[++cnt] = minn[i];
for( int i = 1 ; i <= C ; i ++ ) Xs[++cnt] = sett[i];
Xs[++cnt] = pos[id];
sort( Xs + 1 , Xs + cnt + 1 );
cnt = unique( Xs + 1 , Xs + cnt + 1 ) - ( Xs + 1 );
for( int i = 1 ; i <= A ; i ++ ) maxx[i] = lower_bound( Xs + 1 , Xs + cnt + 1 , maxx[i] ) - Xs;
for( int i = 1 ; i <= B ; i ++ ) minn[i] = lower_bound( Xs + 1 , Xs + cnt + 1 , minn[i] ) - Xs;
for( int i = 1 ; i <= C ; i ++ ) sett[i] = lower_bound( Xs + 1 , Xs + cnt + 1 , sett[i] ) - Xs;
for( int i = 1 ; i <= cnt ; i ++ ) cnta[i] = cntb[i] = cntc[i] = 0;
for( int i = 1 ; i <= A ; i ++ ) cnta[maxx[i]] ++;
for( int i = 1 ; i <= B ; i ++ ) cntb[minn[i]] ++;
for( int i = 1 ; i <= C ; i ++ ) cntc[sett[i]] ++;
for( int i = 1 ; i <= cnt ; i ++ ){
cnta[i] += cnta[i - 1],cntb[i] += cntb[i - 1],cntc[i] += cntc[i - 1];
int a = A - cnta[i],b = cntb[i],c = cntc[i];
res[i] = Bino( q , a + b + C ) * Bino( a + b + C - 1 , a + C - c ) % mod * fac[q - a - b - C] % mod * fac[a + C - c] % mod * fac[b + c] % mod;
if( pos[id] > Xs[i] && b + c == 0 ) res[i] = 0;
if( pos[id] <= Xs[i] && a + C - c == 0 ) res[i] = fac[q];
}
int Ans = 0;
for( int j = cnt ; j >= 1 ; j -- ){
chkequ( res[j] , res[j] - res[j - 1] + mod );
chkadd( Ans , res[j] * Xs[j] % mod );
}
printf("%lld ",Ans);
}
puts("");
}
signed main(){
fac[0] = 1; for( int i = 1 ; i < MAXN ; i ++ ) fac[i] = fac[i - 1] * i % mod;
inv[1] = 1; for( int i = 2 ; i < MAXN ; i ++ ) inv[i] = ( mod - mod / i ) * inv[mod % i] % mod;
ifac[0] = 1; for( int i = 1 ; i < MAXN ; i ++ ) ifac[i] = ifac[i - 1] * inv[i] % mod;
int testcase; scanf("%lld",&testcase);
while( testcase -- ) solve();
return 0;
}
```