题解 P5367 【【模板】康托展开】

zrzluck99 · 2019-05-14 08:27:19 · 题解

这里来一波线段树解

关于康托展开的表达式楼上巨佬已经说的很清楚了，这里的问题就是如何维护每一个数在此时的 rank。

这里我们用到了权值线段树，将权值作为区间维护。线段树每个叶子节点初始化为1，每处理一个数 x，就把 [x,x] 置为 0，这样查询 [1,x-1] 的和就可以在 log(n) 的时间内得到 rank(x)-1 了。

以下代码（线段树已经简化到连 lazy 标记都不用了）：

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define MOD 998244353
#define MAX_ARR 1000001
typedef long long ll;

ll read(){
    ll s=0,w=1; char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') w=-1; ch=getchar();}
    while (ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    return s*w;
}

ll st[4*MAX_ARR],a[MAX_ARR],fact[MAX_ARR],ans=0;
int n;

void build(ll root,ll l,ll r){
    if (l==r){
        st[root] = 1; return;
    }
    ll mid = (l+r)/2;
    build(root*2,l,mid); build(root*2+1,mid+1,r);
    st[root] = st[root*2]+st[root*2+1];
}

void update(ll root,ll l,ll r,ll x){
    if (l>x||r<x) return;
    if (l==r&&l==x) {st[root] = 0; return;}
    ll mid = (l+r)/2;
    update(root*2,l,mid,x); update(root*2+1,mid+1,r,x);
    st[root] = st[root*2]+st[root*2+1];
}

ll query(ll root,ll l,ll r,ll ql,ll qr){
    if (l>qr||r<ql) return 0;
    if (l>=ql&&r<=qr) return st[root];
    ll mid = (l+r)/2;
    return query(root*2,l,mid,ql,qr)+query(root*2+1,mid+1,r,ql,qr);
}

int main(){
    ios::sync_with_stdio(false);
    n = read();
    for (int i=n-1;i>=0;i--) a[i] = read();
    fact[0] = 1;
    for (int i=1;i<=n;i++) fact[i] = (fact[i-1]*i)%MOD;
    build(1,1,n);
    for (int i=n-1;i>=0;i--){
        update(1,1,n,a[i]);
        ans = (ans+(query(1,1,n,1,a[i]-1)*fact[i])%MOD)%MOD;
    }
    printf("%lld\n",ans+1);
    return 0;
}