P8576 「DTOI-2」星之界题解

Daidly · 2022-12-22 12:35:14 · 题解

这题卡了我好久，分块题一般极其难调，细节巨多。

首先询问的式子可以化简：

\prod_{i=l}^rC_{\sum_{j=l}^ra_j}^{a_i}=\frac{sum(l,r)!}{\prod_{i=l}^r(a_i!)}

需要维护区间求和，区间阶乘之积，由于 \sum a_i\leq 10^7，可以先预处理 10^7 以内的阶乘和 10^5 以内的阶乘的逆元。

考虑分块，如何支持区间值的改变？对于每一块内值相同的放在一个集合中。可以发现经过一些操作之后，集合的个数会越来越多，也就是有初始值不同的集合合并。

用并查集维护初始值相同的集合，记 f_i 表示下标为 i 的元素的集合编号，我们可以建立一个虚点作为集合的代表，也可以直接使用块内第一个元素，这里使用第二种，较为简便。

对于修改操作，散块直接更新块内值，然后统计修改重构。整块我们考虑合并（若块内有 x）：若块内无 y，则直接将块内第一个元素的值改为 y，并把“块内第一个值为 y 的下标”更新成 x（因为此时块内值为 x 的全员变成了 y）；若块内有 y，我们需要把代表 x 的点的父亲设为第一个 y。此外，还需要开个桶维护块内元素个数，维护块内和，已经块内阶乘之积的逆元。最后，清空有关 x 的桶和第一个 x 出现的下标（清空块内有关 x 的数据）。

这类题很容易某些东西忘记更新或忘记清空，一定要注意。

对于询问操作，散块暴力获取值统计，整块利用维护的值计算即可。

有点卡空间，用 int，但如果一直卡可能是函数出了问题（例如没清空导致栈空间爆掉）。

代码如下：


#include<bits/stdc++.h>
using namespace std;

inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}

void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10^48);
}

const int N=1e5+5,SUM=1e7+5,mod=998244353,S=330;

int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=1ll*ans*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return ans;
}

int n,q,a[N],f[N],bel[N];
int fac[SUM],invfac[N];
int mul_invfac[N/S+5],R[N/S+5],sum[N/S+5],invpow[N][S+5],facpow[N][S+5];
int fir[N/S+5][N],t[N/S+5][N];

inline int find(int x){
    return (x==f[x])?x:f[x]=find(f[x]);
}

inline void init(int maxn){
    fac[0]=invfac[0]=1;
    for(int i=1;i<=maxn;++i)fac[i]=1ll*fac[i-1]*i%mod;//1e7 
    invfac[N-5]=qpow(fac[N-5],mod-2);
    for(int i=N-6;i>=1;--i)invfac[i]=1ll*invfac[i+1]*(i+1)%mod;//1e5即可 
    for(int i=0;i<=N-5;++i){//预处理，可以去掉log 
        invpow[i][0]=facpow[i][0]=1;
        for(int j=1;j<=S;++j){
            invpow[i][j]=1ll*invpow[i][j-1]*invfac[i]%mod;
            facpow[i][j]=1ll*facpow[i][j-1]*fac[i]%mod;
        }
    }
}

inline void remake(int k){
    mul_invfac[k]=1,sum[k]=0;
    for(int i=R[k-1]+1;i<=R[k];++i){
        t[k][a[i]]++;
        if(t[k][a[i]]==1)fir[k][a[i]]=i;
        f[i]=fir[k][a[i]];
        sum[k]+=a[i];
        mul_invfac[k]=1ll*mul_invfac[k]*invfac[a[i]]%mod;
    }
}

void update(int k){
    for(int i=R[k-1]+1;i<=R[k];++i){
        a[i]=a[find(i)];
        fir[k][a[i]]=t[k][a[i]]=0;//清空 
    }
}

inline void modify(int l,int r,int x,int y){
    if(bel[l]==bel[r]){
        update(bel[l]);//判断散块前要先获取a[i]的真实值 
        for(int i=l;i<=r;++i)if(a[i]==x)a[i]=y;
        remake(bel[l]);//重构此块 
        return;
    }
    if(l!=R[bel[l]-1]+1){
        update(bel[l]);
        for(int i=l;i<=R[bel[l]];++i)if(a[i]==x)a[i]=y;
        remake(bel[l]);
        l=R[bel[l]]+1;
    }
    if(r!=R[bel[r]]){
        update(bel[r]);
        for(int i=R[bel[r]-1]+1;i<=r;++i)if(a[i]==x)a[i]=y;
        remake(bel[r]);
        r=R[bel[r]-1];
    }
    for(int i=bel[l];i<=bel[r];++i){
        if(fir[i][x]){
            if(fir[i][y])f[fir[i][x]]=fir[i][y];//合并x和y 
            else fir[i][y]=fir[i][x],a[fir[i][x]]=y;//直接改 
            sum[i]+=(y-x)*t[i][x];
            mul_invfac[i]=1ll*mul_invfac[i]*facpow[x][t[i][x]]%mod*invpow[y][t[i][x]]%mod;
            //这里注意由于维护的是逆元，所以乘x的阶乘和y阶乘的逆元 
            t[i][y]+=t[i][x];
            t[i][x]=fir[i][x]=0;//这里一定要注意两个都要清空 
        }
    }
}

inline int qry(int l,int r){
    int Sum=0,invMul=1,tmp;
    if(bel[l]==bel[r]){
        for(int i=l;i<=r;++i)a[i]=a[find(i)],Sum+=a[i],invMul=1ll*invMul*invfac[a[i]]%mod;
        return 1ll*fac[Sum]*invMul%mod;
    }
    if(l!=R[bel[l]-1]+1){
        for(int i=l;i<=R[bel[l]];++i)a[i]=a[find(i)],Sum+=a[i],invMul=1ll*invMul*invfac[a[i]]%mod;
        l=R[bel[l]]+1;
    }
    if(r!=R[bel[r]]){
        for(int i=R[bel[r]-1]+1;i<=r;++i)a[i]=a[find(i)],Sum+=a[i],invMul=1ll*invMul*invfac[a[i]]%mod;
        r=R[bel[r]-1];
    }
    for(int i=bel[l];i<=bel[r];++i){
        Sum+=sum[i],invMul=1ll*invMul*mul_invfac[i]%mod;
    }
    return 1ll*fac[Sum]*invMul%mod;
}

signed main(){
    n=read(),q=read();
    init(1e7);
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=n;++i)bel[i]=(i+S-1)/S;
    for(int i=1;i<=n/S;++i)R[i]=i*S;
    if(n%S)R[bel[n]]=n;
    for(int i=1;i<=bel[n];++i)remake(i);
    int opt,l,r,x,y;
    while(q--){
        opt=read(),l=read(),r=read();
        if(opt==1){
            x=read(),y=read();
            if(x==y)continue;//特判，否则在整块修改时会清空x 
            modify(l,r,x,y);
        }else print(qry(l,r)),puts("");
    }
    return 0;
}

如果觉得有帮助可以点个赞，谢谢。

P8576 「DTOI-2」星之界 题解

P8576 「DTOI-2」星之界题解