自动搬运

查看原文

来自洛谷，原作者为

	Daidly 竹杖芒鞋轻胜马，谁怕？一蓑烟雨任平生。

搬运于2025-08-24 22:40:19，当前版本为作者最后更新于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;
}

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