康托（Cantor）展开

#include bits/stdc++.h //随时记得取模，尽可能降低WA的概率
#define P 998244353
#define N 1000009
using namespace std;
int n,ans=,a[N],sum[N ];
long long f[N];//这道题内存限制只有31.25MB，第一次全开了long long发现MLE，第二次全开了int爆WA，最后部分开了long long才压内存过
void Update(int rt,int l,int r,int x,int c,int fg)//fg是flag，标记
{
if(l==r l==x)
{
if(fg==) sum[rt]+=c;//如果是插入，sum就加c
else sum[rt]-=c;//如果是删除，sum就减c
return;
}
int mid=(l+r) ;
if(x =mid) Update(rt ,l,mid,x,c,fg);
else Update(rt |,mid+,r,x,c,fg);
sum[rt]=sum[rt ]+sum[rt |];
int Query(int rt,int l,int r,int x,int y)
{
if(l==x r==y) return sum[rt];
int mid=(l+r) ;
if(y =mid) return Query(rt ,l,mid,x,y);
else if(x mid) return Query(rt |,mid+,r,x,y);
else return Query(rt ,l,mid,x,mid)+Query(rt |,mid+,r,mid+,y);
}
int main(){
memset(sum,,sizeof(sum));
scanf("%d",
f[]=;//注意
for(int i=;i i++) f[i]=f[i-]%P*i%P;//计算阶乘
for(int i=;i i++)
{
scanf("%d", a[i]);
Update(,,n,a[i],,);//将每一个数插入到权值线段树中
}
for(int i=;i i++)
{
if(a[i]==)//如果a[i]==1，那么该数一定对答案没有贡献，直接删除
{
Update(,,n,a[i],,);
continue;
}
ans=(ans+Query(,,n,,a[i]-)%P*f[n-i]%P)%P;//更新答案
Update(,,n,a[i],,);//删除这个数
}
printf("%d\n",(ans+P)%P);
return ;
}