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

· · 题解

发现还没有cdq的做法，特来贡献一种

泥萌的权值线段树，树状数组都好高级呀

本蒟蒻不会数据结构，就只能离线做了。

康托展开还是一样的，将每个询问离线下来

最后cdq分治

其实就是一个裸的cdq

#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define RG register
#define gi getint()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
IL int getint()
{
    RG int xi=0;
    RG char ch=gc;
    bool f=0;
    while(ch<'0'||ch>'9')ch=='-'?f=1:f,ch=gc;
    while(ch>='0'&&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;
    return f?-xi:xi;
}
template<typename T>
IL void pi(T k,char ch=0)
{
    if(k<0)k=-k,putchar('-');
    if(k>=10)pi(k/10,0);
    putchar(k%10+'0');
    if(ch)putchar(ch);
}
typedef long long ll;
const int mod=998244353,N=1e6+10;
int jc[N];
struct Query{
    int type,id,v;
    bool operator < (const Query & k)const{
        return id==k.id?type<k.type:id<k.id;
    }
}Q[N<<1],tmp[N<<1];
int a[N],tot,atot;
int ans[N];
void cdq(int L,int R)
{
    if(R-L<=1)return;
    int M=(L+R)>>1;
    cdq(L,M),cdq(M,R);
    int l=L,r=M,t=L,sum=0;
    while(l<M&&r<R)
        if(Q[l]<Q[r])
        {
            if(Q[l].type==1)sum+=Q[l].v;
            tmp[t++]=Q[l++];
        }
        else 
        {
            if(Q[r].type==2)ans[Q[r].v]+=sum;
            tmp[t++]=Q[r++];
        }
    while(l<M)tmp[t++]=Q[l++];
    while(r<R)
    {
        if(Q[r].type==2)ans[Q[r].val]+=sum;
        tmp[t++]=Q[r++];
    }
    for(int i=L;i<R;i++)Q[i]=tmp[i];
}
int main(void)
{
    int n=gi;
    jc[0]=1;
    for(int i=1;i<=n;++i)jc[i]=(1ll*i*jc[i-1])%mod,Q[tot++]=(Query){1,i,1};
    for(int i=1,k;i<=n;++i)Q[tot++]=(Query){2,k=gi,i},Q[tot++]=(Query){1,k,-1};
    cdq(0,tot);
    ll ret=1;
    for(int i=1;i<=n;++i)(ret+=(1ll*(ans[i]-1)*jc[n-i])%mod)%=mod;
    cout<<ret;
    return 0;
}