题解 AT3956 【[AGC023E] Inversions】

jun头吉吉 · 2022-01-14 12:36:28 · 题解

题意

给出一个长度为 n 的序列 A_i，问所有 P_i\le A_i 的 1\sim n 的排列的逆序对的个数和是多少。

题解

搬运一下官方题解

令 cnt[k] 表示 \sum [A_i\ge k]-(n-k) ，也就是数字 k 还剩下的合法位置数，最后的合法序列数就是 S=\prod_{1\le i\le n}cnt[i]。如果有一个 cnt[i] 为 0 就可以直接输出 0 跑路了。否则我们可以统计每一对 i<j 的贡献。

首先考虑 A_i\le A_j 的的答案，我们希望 i 位置上的数大于 j 位置上的数，因此我们可以先强制让 A_j\leftarrow A_i，然后发现 i 比 j 大和 i 比 j 小的方案数是一样多的，并且会发现 k\in[A_i+1,A_j] 的 cnt[k] 都会减 1。因此我们不妨设 D[k]=\sum_{i=1}^n(cnt[i]-1)/cnt[i]，然后贡献就是 \frac12S\times D[A_j]/D[A_i]。

我们枚举 j，然后维护一个前缀的 1/D[A_i] 之和，然后查询的时候就直接询问 [1,A_j] 就可以得到 \sum D[A_j]/D[A_i] 了。但是还有一个问题是可能 D[A_i],D[A_j] 的值都是 0 但是其实 [A_i+1,A_j] 的积是不为 0 的。为了解决这个问题，我们可以把 D[k] 写成 D[k]\times 0^{x[k]}，然后 [l+1,r] 的积不为 0 就等价于 x[l]=x[r]。而 x[k] 显然又是单调不降的，所以我们可以只查询与 x[A_j] 相等的这一部分，x[A_i]<x[A_j] 也就意味着 [A_i+1,A_j] 会出现 0，然后就肯定没有合法方案。

现在来考虑 A_i>A_j 的情况，我们发现我们刚刚的分析有些就没法用了。考虑正难则反，让 A_i\leftarrow A_j 然后跑上面的算法就是 i,j 是顺序对的情况，用 S 减去这个就是逆序对的贡献数了。

代码

想清楚了就非常好写。

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pc putchar
#define chkmx(a,b) (a)=max((a),(b))
#define chkmn(a,b) (a)=min((a),(b))
#define fi first
#define se second
using namespace std;
template<class T>
void read(T&x){x=0;char c=getchar();bool f=0;for(;!isdigit(c);c=getchar())f^=c=='-';for(;isdigit(c);c=getchar())x=x*10+c-'0';if(f)x=-x;}
template<class T,class ...ARK>void read(T&x,ARK&...ark){read(x);read(ark...);}
template<class T>void write(T x){if(x<0)pc('-'),x=-x;if(x>=10)write(x/10);pc(x%10+'0');}
template<class T,class ...ARK>void write(T x,ARK...ark){write(x);pc(' ');write(ark...);}
template<class ...ARK>void writeln(ARK...ark){write(ark...);pc('\n');}
typedef long long ll;
#define lowbit(x) ((x)&-(x))
const int mod=1e9+7;
struct mint{
    int x;
    mint(int o=0){x=o;}
    mint&operator+=(mint a){return(x+=a.x)%=mod,*this;}
    mint&operator-=(mint a){return(x+=mod-a.x)%=mod,*this;}
    mint&operator*=(mint a){return(x=1ll*x*a.x%mod),*this;}
    mint&operator^=(int b){mint a=*this;x=1;while(b)(b&1)&&(*this*=a,1),a*=a,b>>=1;return*this;}
    mint&operator/=(mint a){return*this*=(a^=mod-2);}
    friend mint operator+(mint a,mint b){return a+=b;}
    friend mint operator-(mint a,mint b){return a-=b;}
    friend mint operator*(mint a,mint b){return a*=b;}
    friend mint operator/(mint a,mint b){return a/=b;}
};
const int N=2e5+100;
int n,a[N],cnt[N],x[N],lst[N];
mint D[N],S;
template<class T>struct BIT{
    T tree[N];
    void clear(){memset(tree,0,sizeof tree);}
    void add(int x,T val){for(;x<=n;x+=lowbit(x))tree[x]+=val;}
    T qry(int x){T res=0;for(;x;x-=lowbit(x))res+=tree[x];return res;}
    T qry(int l,int r){return qry(r)-((l==0)?0:qry(l-1));}
};
BIT<int>ct;
BIT<mint>sm;
signed main(){
    read(n);
    for(int i=1;i<=n;i++)read(a[i]),cnt[a[i]]++;
    for(int i=n;i;i--)cnt[i]+=cnt[i+1];
    for(int i=1;i<=n;i++)cnt[i]-=n-i,cnt[i]==0&&(puts("0"),exit(0),1);
    D[0]=1,x[0]=0;S=1;
    for(int i=1;i<=n;i++){
        D[i]=D[i-1]/cnt[i];S*=cnt[i];
        if(cnt[i]==1)x[i]=x[i-1]+1;
        else x[i]=x[i-1],D[i]*=cnt[i]-1;
        //writeln(i,cnt[i],D[i].x,x[i]);
    }
    for(int i=1;i<=n;i++)
        if(x[i]==x[i-1])lst[i]=lst[i-1];
        else lst[i]=i;
    mint ans=0;
    //考虑 i<j,Ai<=Aj 的情况
    //贡献为 S/2 D[Aj]/D[Ai]
    for(int j=1;j<=n;j++){
        ans+=S/2*D[a[j]]*sm.qry(lst[a[j]],a[j]);
        sm.add(a[j],1/D[a[j]]);
    }
    //再考虑 i<j,Ai>Aj 的情况
    //正难则反考虑不满足就 S - S/2 D[Ai]/D[Aj]
    sm.clear();
    for(int i=n;i;i--){
        ans+=S*ct.qry(1,a[i]-1)-S/2*D[a[i]]*sm.qry(lst[a[i]],a[i]-1);
        sm.add(a[i],1/D[a[i]]);ct.add(a[i],1);
    }
    write(ans.x);
}