「StOI-1」小Z的旅行

emmm..终于ac了,这里介绍一下标程做法,大佬的分治做法我也看不太懂,码风完全不一样.
标程就是从后往前计算贡献,算出贡献的付出,最后保留的贡献就是f[n].

#include <bits/stdc++.h>
typedef long long ll;
const ll mod=998244353;
const int N=5e5+5;
struct vv{
    ll h,id;//高度和位子.
}w[N];
ll n,dis[N],g[N],f[N],sum[2][N];//第1维维护个数,第二维维护权值.

ll qp(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)    res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }return res;
}

ll iv(ll x) { return qp(x,mod-2); }

bool cmp(vv a,vv b)  { return a.h<b.h;  }

ll lowbit(ll x)  { return x&(-x); }

void add(ll pos,ll val,int op)
{
    while(pos<=n)
    {
        sum[op][pos]+=val;
        pos+=lowbit(pos);
    }
}

ll query(ll pos,int op)
{
    ll res=0;
    while(pos)
    {
        res+=sum[op][pos];
        pos-=lowbit(pos);
    }return res;
}

ll ask(ll pos)//查询前面所有点到这个点的距离.
{
    ll res=0;
    //询问在它前面的距离.
    res=((res+query(pos-1,0)*pos-query(pos-1,1))%mod+mod)%mod;
    //询问在它后面的距离.
    res=((res+query(n,1)-query(pos,1)-(query(n,0)-query(pos,0))*pos)%mod+mod)%mod;
    return res;
}

signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&w[i].h);
        w[i].id=i;
    }
    std::sort(w+1,w+1+n,cmp);
    //进行dp.
    int cnt=0;//统计前面所有的平均值.
    for(int i=1;i<=n;)
    {
        int j=i,now=0;//单纯统计当前转移的g[i]平均值.
        while(w[i].h==w[j].h)   j++;
        for(int k=i;k<j;k++)
        {
            dis[k]=(ask(w[k].id)%mod+mod)%mod;
            g[k]=((cnt+dis[k])%mod+mod)%mod;
            g[k]=((g[k]*iv(i-1))%mod+mod)%mod;
            now=((now+g[k])%mod+mod)%mod;
        }
        for(int k=i;k<j;k++)    {int pos=w[k].id;add(pos,1,0);add(pos,pos,1);}
        for(int k=i;k<j;k++)
        {
            ll odd=((now-g[k]+ask(w[k].id)-dis[k])%mod+mod)%mod;
            f[k]=((iv(j-2)*(i-1)%mod)*g[k]%mod+iv(j-2)*odd%mod+mod)%mod;
            cnt=((cnt+f[k])%mod+mod)%mod;
        }
        //概率dp都是倒过来dp的.
        i=j;
    }
    printf("%lld\n",f[n]);
}