数学、动态规划、线段树
将长度为 $n$ 的排列 $a$ 转化为长度为 $n-1$ 的 $01$ 序列，若 $\min\limits_{j=1}^{i-1} a_j < a_i$ 则转化后序列的第 $i-1$ 位为 $1$，否则为 $0$。猜测转化后序列每一位对答案的贡献相互独立。
打表找到规律，记 $p_i$ 为转化后的序列第 $i$ 位是 $1$ 的方案数，令 $p_0 = 0$，有：
$$p_i = p_{i-1} + \frac{n!}{2} \times \frac{1}{\sum_{j=1}^{i} j} = p_{i-1} + \frac{n!}{2} \times \frac{1}{\frac{(1+i)i}{2}} = p_{i-1} + \frac{n!}{i(i+1)}$$
设计 $dp_{i}$ 为将第 $i$ 个 $1$ 变成 $0$ 的同时完成前 $i$ 位的期望步数。
$$dp_{i} =1 + \sum_{j=1}^{i} \frac{p_j dp_j + (n!-p_j)}{n!}$$
$$= 1 + \sum_{j=1}^{i-1} \frac{p_j dp_j + (n!-p_j)}{n!} + \frac{p_i dp_i + (n! - p_i)}{n!}$$
$$= 1 + \sum_{j=1}^{i-1} \frac{p_j dp_j + (n!-p_j)}{n!} + \frac{p_i dp_i}{n!} + \frac{n! - p_i}{n!}$$
$$dp_i - \frac{p_i}{n!} dp_i = 1 + \sum_{j=1}^{i-1} \frac{p_j dp_j + (n!-p_j)}{n!} + \frac{n! - p_i}{n!}$$
$$\frac{n! - p_i}{n!} dp_i = 1 + \sum_{j=1}^{i-1} \frac{p_j dp_j + (n!-p_j)}{n!} + \frac{n! - p_i}{n!}$$
$$dp_i = \frac{n!}{n! - p_i} \left( 1 + \sum_{j=1}^{i-1} \frac{p_j dp_j + (n!-p_j)}{n!} + \frac{n! - p_i}{n!} \right)$$
$$dp_i = \frac{n!}{n! - p_i} \left( 1 + \sum_{j=1}^{i-1} \frac{p_j dp_j + (n!-p_j)}{n!} \right) + 1$$
然后不知道为啥这个 $dp_i$ 要加上 $i+1$ 才是对的，但毕竟 $p$ 都是打表发现的，我做题的时候也没手段验证正确性。
对于给定序列，若其转化后的第 $i$ 位为 $1$，则答案加上 $dp_i$，否则答案加上 $1$，注意答案的初始值为 $1$，因为每次加入第一个元素都要花费一次操作。
使用 $pre_i$ 表示 $\min\limits_{j=1}^{i} a_i$ 的值，当且仅当 $pre_{i-1} > pre_{i}$ 时转化后序列第 $i$ 位为 $0$，使用陈亮舟的康师傅冰力十足冰红茶线段树维护转化后的序列和答案。
实际上可以令 $dp_1 = 1$ ，然后把 $p$ 向右偏移一位再计算，这样线段树叶节点 $[l,r]$ 就可以直接用 $dp_l$ 的值。代码里 $p,dp$ 都向左偏移了一位，因此把 $sum$ 的初始值为 $1$，线段树叶节点用的是 $dp_{l-1}$ 的值。
虽然不知道为啥对，但是代码写出来过了。
使用 $m$ 表示交换操作次数，由于 $n,m$ 同阶，时间复杂度 $O(n \log^2 n)$。
#include<bits/stdc++.h>
using namespace std;
constexpr int mod=1'000'000'007;
struct Segment{int l,r,k;long long w;}s[800'005];
long long fac,p[200'005],dp[200'005];
int n,m,a[200'005];
long long inv(long long x){
long long ret=1ll;
for(int i=mod-2;i;i>>=1){
if(i&1) ret=ret*x%mod;
x=x*x%mod;
}
return ret;
}
long long query(int u,int k){
if(s[u].l==s[u].r) return (s[u].k<k)*s[u].w;
if(s[u*2].k>=k) return query(u*2+1,k);
return s[u].w-s[u*2].w+query(u*2,k);
}
void pushup(int u){
s[u].k=min(s[u*2].k,s[u*2+1].k);
s[u].w=s[u*2].w+query(u*2+1,s[u*2].k);
}
void build(int u,int l,int r){
s[u].l=l,s[u].r=r;
if(l==r){
s[u].k=a[l];
s[u].w=dp[l-1]-1;//维护答案减量
return;
}
build(u*2,l,(l+r)/2);
build(u*2+1,(l+r)/2+1,r);
pushup(u);
}
void update(int u,int p,int k){
if(s[u].l==s[u].r) return s[u].k=k,void();
if(p<=s[u*2].r) update(u*2,p,k);
else update(u*2+1,p,k);
pushup(u);
}
inline int answer(){
static const long long sum=accumulate(dp,dp+n,0ll);
int ret=((sum-s[1].w)%mod+mod)%mod;
return ret;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m,fac=1ll;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) fac=fac*i%mod;
for(int i=1;i<=n-1;i++) p[i]=(p[i-1]+fac*inv(i)%mod*inv(i+1))%mod;
for(int i=1;i<=n-1;i++){
static long long sum=1ll;
dp[i]=(fac*inv(fac-p[i])%mod*sum%mod+1)%mod;
dp[i]=(dp[i]+i+1)%mod;
sum=(sum+(p[i]*dp[i]%mod+fac-p[i])*inv(fac))%mod;
}
dp[0]=1ll;//方便建树
build(1,1,n);
cout<<answer()<<'\n';
for(int i=1;i<=m;i++){
static int x,y;
cin>>x>>y;
swap(a[x],a[y]);
update(1,x,a[x]),update(1,y,a[y]);
cout<<answer()<<'\n';
}
return 0;
}题解的推导方法是，记 $f_i$ 为把前 $i$ 块石块随机打乱后，期望把这些石块按顺序堆成高塔的天数。首先 $f_i$ 需要把前 $i-1$ 块石块搭好，然后再用一天放上第 $i$ 块石头，然后有有 $\frac{1}{i}$ 的概率不会倒塌，因此得到递推式。
$$f_i = f_{i-1} + 1 + \frac{i-1}{i} f_i$$
$$\frac{1}{i} f_i = f_{i-1} + 1$$
$$f_i = i (f_{i-1} + 1)$$
用 $f$ 算出来的答案要加上 $n$，因为 $f$ 不包含把开始状态的每个石头堆上去的天数。
时间复杂度还是 $O(n \log^2 n)$。
#include<bits/stdc++.h>
using namespace std;
constexpr int mod=1'000'000'007;
struct Segment{int l,r,k;long long w;}s[800'005];
int n,m,a[200'005],f[200'005];
long long query(int u,int k){
if(s[u].l==s[u].r) return (s[u].k<k)*s[u].w;
if(s[u*2].k>=k) return query(u*2+1,k);
return s[u].w-s[u*2].w+query(u*2,k);
}
void pushup(int u){
s[u].k=min(s[u*2].k,s[u*2+1].k);
s[u].w=s[u*2].w+query(u*2+1,s[u*2].k);
}
void build(int u,int l,int r){
s[u].l=l,s[u].r=r;
if(l==r) return s[u].k=a[l],s[u].w=f[l],void();
build(u*2,l,(l+r)/2),build(u*2+1,(l+r)/2+1,r);
pushup(u);
}
void update(int u,int p,int k){
if(s[u].l==s[u].r) return s[u].k=k,void();
if(p<=s[u*2].r) update(u*2,p,k);
else update(u*2+1,p,k);
pushup(u);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) f[i]=1ll*i*(f[i-1]+1)%mod;
build(1,1,n);
long long sum=(accumulate(f+1,f+n+1,0ll)+n)%mod;
cout<<((sum-s[1].w)%mod+mod)%mod<<'\n';
for(int i=1;i<=m;i++){
static int x,y;
cin>>x>>y;
swap(a[x],a[y]);
update(1,x,a[x]);
update(1,y,a[y]);
cout<<((sum-s[1].w)%mod+mod)%mod<<'\n';
}
return 0;
}