0. 题目一句话总结

我们有 $n$ 个滑块，$q$ 个操作。 操作执行顺序是全排列，共 $q!$ 种。 求所有排列结束后每个滑块的位置之和，对 $10^9+7$ 取模。

---

1. 核心变换：$b_i = a_i - i$（最关键）

定义

$$b_i = a_i - i$$

• $a_i$：滑块 $i$ 的真实位置
• $b_i$：转换后的相对位置

为什么要这样变？

原约束：滑块必须保持顺序

$$a_1 < a_2 < \dots < a_n$$

代入后变成：

$$b_1 \le b_2 \le \dots \le b_n$$

✅ $b$ 数组永远非递减 ✅ 所有“推动/挤压”的复杂物理规则全部消失

---

2. 操作在 $b$ 数组上的等价规则（英文题解核心）

对滑块 $pos$ 执行操作，设目标值为 $x$：

1. 设置 $b_{pos} = x$
2. 左边所有元素：$b_i = \min(b_i, b_{pos})$
3. 右边所有元素：$b_i = \max(b_i, b_{pos})$

也就是说：

• 左边受 $\boldsymbol{\min}$ 影响
• 右边受 $\boldsymbol{\max}$ 影响
• 自己被赋值

---

3. 核心贡献法思路（英文题解）

最终 $b_i$ 的值，由最后一次有效操作决定。

我们只需要计算：

$$ans_i = \sum_{op} \left( val_{op} \times P(op \text{ 是最后一次有效操作}) \right) $$

最后答案乘上 $q!$（所有排列）。

---

4. 操作分类（对单个滑块 $i$）

一个操作只会是三种之一：

1. $\boldsymbol{b_i = \max(b_i, x)}$
2. $\boldsymbol{b_i = \min(b_i, x)}$
3. $\boldsymbol{b_i = x}$（直接赋值）

---

5. 最后有效操作规则

设最终值为 $b_e$：

• 最后一步一定是 $x = b_e$ 的操作
• 如果是 $\max$：前面必须满足 $b_i < b_e$
• 如果是 $\min$：前面必须满足 $b_i > b_e$
• 如果是赋值：无前置条件

---

6. 代码完整详细解释（逐段对应题解）

6.1 常量与预处理

const long long mod = 1e9+7;
long long a[5000], ans[5000];
long long tt[5001], inv[5001];  // 阶乘、逆元

• tt[i] = i!：总排列数
• inv[i]：模逆元，用于算概率

6.2 操作结构体（按 x 排序）

struct apos {
    long long id, x;
    bool operator<(apos a, apos b) {
        return a.x < b.x;
    }
} ap[5000];

✅ 对应题解：将操作按 x 排序

6.3 输入转换为 $b$ 数组

for(i=0;i<n;i++) {
    cin >> a[i];
    a[i] -= i;   // 变成 b 数组
}
for(i=0;i<p;i++) {
    cin >> ap[i].id >> ap[i].x;
    ap[i].id--;
    ap[i].x -= ap[i].id;  // 操作也转成 b 空间
}
sort(ap, ap + p);

6.4 若滑块不受任何操作影响

flag = 0;
for(j=0;j<p;j++) {
    if(ap[j].id <= i && ap[j].x >= a[i]) flag = 1;
    if(ap[j].id >= i && ap[j].x < a[i]) flag = 1;
}
if(!flag) {
    ans[i] = a[i] + i;
    continue;
}

✅ 对应题解：never touched → 保持初始值

6.5 统计左右有效操作数

cl = 0; cr = 0;
for(j=0;j<p;j++)
    if(ap[j].id <= i) cr++;

• cl：当前左边有效操作数
• cr：当前右边有效操作数

6.6 枚举每个操作作为最后一步

for(j=0;j<p;j++) {
    if(ap[j].id <= i) cr--;

    // 情况1：操作作用在 i 自己身上
    if(ap[j].id == i)
        ans[i] = (ans[i] + (ap[j].x + i) * inv[cl + cr + 1]) % mod;

    // 情况2：操作在 i 左边（min 类）
    if(ap[j].id < i) {
        if(cl ==0 && cr ==0 && a[i] <= ap[j].x)
            ans[i] = (ans[i] + ap[j].x + i) % mod;
        else
            ans[i] += ... * cl % mod;
    }

    // 情况3：操作在 i 右边（max 类）
    if(ap[j].id > i) {
        if(cl ==0 && cr ==0 && a[i] > ap[j].x)
            ans[i] = (ans[i] + ap[j].x + i) % mod;
        else
            ans[i] += ... * cr % mod;
    }

    if(ap[j].id >= i) cl++;
}

✅ 对应题解：

• 左边操作 → $\min$ 约束
• 右边操作 → $\max$ 约束
• 自身操作 → 赋值

6.7 最终答案 = 期望 × q!

cout << ans[x] * tt[p] % mod << ' ';

---

7. 时间复杂度

$$O(nq)$$

$n,q \le 5000$，完美通过。

---

8. 完整可直接提交代码

#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
long long a[5000],ans[5000],tt[5001],inv[5001];
struct apos{
	long long id;
	long long x;
	friend bool operator<(apos a,apos b){
		return a.x<b.x;
	}
}ap[5000];
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int T,flag;
	long long n,m,p,q,x,i,j,cl,cr;
	tt[0]=1;
	for(i=1;i<=5000;i++)tt[i]=tt[i-1]*i%mod;
	inv[1]=1;
	for(i=2;i<=5000;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	for(cin>>T;T>0;T--)
	{
		cin>>n>>m>>p;
		for(i=0;i<n;i++)
		{
			cin>>a[i];
			a[i]-=i;
		}
		for(i=0;i<p;i++)
		{
			cin>>ap[i].id>>ap[i].x;
			ap[i].id--;
			ap[i].x-=ap[i].id;
		}
		sort(ap,ap+p);
		for(i=0;i<n;i++)
		{
			flag=0;
			for(j=0;j<p;j++)
			{
				if(ap[j].id<=i&&ap[j].x>=a[i])flag=1;
				if(ap[j].id>=i&&ap[j].x<a[i])flag=1;
			}
			if(!flag)
			{
				ans[i]=a[i]+i;
				continue;
			}
			ans[i]=0;
			cl=0;
			cr=0;
			for(j=0;j<p;j++)
			{
				if(ap[j].id<=i)cr++;
			}
			for(j=0;j<p;j++)
			{
				if(ap[j].id<=i)cr--;
				if(ap[j].id==i)ans[i]=(ans[i]+(ap[j].x+i)*inv[cl+cr+1])%mod;
				if(ap[j].id<i)
				{
					if(cl==0&&cr==0&&a[i]<=ap[j].x)ans[i]=(ans[i]+ap[j].x+i)%mod;
					else ans[i]=(ans[i]+(ap[j].x+i)*inv[cl+cr+1]%mod*inv[cl+cr]%mod*cl)%mod;
				}
				if(ap[j].id>i)
				{
					if(cl==0&&cr==0&&a[i]>ap[j].x)ans[i]=(ans[i]+ap[j].x+i)%mod;
					else ans[i]=(ans[i]+(ap[j].x+i)*inv[cl+cr+1]%mod*inv[cl+cr]%mod*cr)%mod;
				}
				if(ap[j].id>=i)cl++;
			}
		}
		for(int x = 0;x < n;x ++)
		{
			cout<<ans[x]*tt[p]%mod<<' ';
		}
		cout<<'\n';
	}
	return 0;
}

---

9. 极简记忆版

1. $b_i = a_i - i$ 消去物理规则
2. 操作等价于：左 $\min$，右 $\max$，自己赋值
3. 最后一次操作决定结果
4. 求每个操作成为最后一步的概率
5. 答案 = 期望 × $q!$