P8576 15pts WA 2,3,15 MLE 6~14

#include <bits/stdc++.h>
#define LL long long
#define mxn 100000
#define mxk 320

using namespace std;

const int N = 100010, M = 10000010, K = 326, mod = 998244353, K_ = N / (K - 10) + 10;

int n, q;
int a[N], pos[N];
int L[K_], R[K_], t;
int fac[M], inv[N];
int p[N], col_rt[N];
int sum[K_], mul[K_];
int fac_[N][K], inv_[N][K];
struct Pie
{
	int h, cnt;
} li[K_][N];

inline int find(int x)
{
	if (x == p[x]) return x;
	return p[x] = find(p[x]);
}

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

inline void remake(int id)
{
	sum[id] = 0;
	mul[id] = 1;
	for (int i = L[id]; i <= R[id]; i ++ )
	{
		if (!li[id][a[i]].h)
		{
			li[id][a[i]].h = i;
			li[id][a[i]].cnt = 1;
			p[i] = i;
			col_rt[i] = a[i];
		}
		else
		{
			li[id][a[i]].cnt ++ ;
			p[i] = li[id][a[i]].h;
		}
		(sum[id] = 1ll * sum[id] % mod + 1ll * a[i] % mod) %= mod;
		(mul[id] = 1ll * mul[id] % mod * 1ll * inv[a[i]] % mod) %= mod;
	}
}

inline void init()
{
	fac[0] = inv[0] = 1;
	for (int i = 1ll * 1; i <= 1e7; i ++ ) fac[i] = 1ll * (LL)fac[i - 1] % mod * 1ll * i % mod;
	inv[mxn] = quick_power(fac[mxn] % mod, mod - 2) % mod;
	for (int i = mxn - 1; i; i -- ) inv[i] = 1ll * (LL)inv[i + 1] % mod * 1ll * (i + 1) % mod;
	for (int i = 1; i <= mxn; i ++ )
	{
		fac_[i][0] = inv_[i][0] = 1;
		for (int j = 1; j <= mxk; j ++ )
			fac_[i][j] = 1ll * (LL)fac_[i][j - 1] % mod * 1ll * fac[i] % mod,
			inv_[i][j] = 1ll * (LL)inv_[i][j - 1] % mod * 1ll * inv[i] % mod;
	}
	int len = sqrt(n);
	t = len ? n / len : n;
	for (int i = 1; i <= t; ++ i)
        L[i] = R[i - 1] + 1, R[i] = i * len;
    if (t * len < n) t ++ , L[t] = R[t - 1] + 1, R[t] = n;
    for (int i = 1; i <= t; ++ i)
        for (int j = L[i]; j <= R[i]; ++ j)
            pos[j] = i;
    for (int i = 1; i <= t; i ++ ) remake(i);
}

inline void modify(int id, int l, int r, int x, int y)
{
	for (int i = L[id]; i <= R[id]; i ++ ) 
		a[i] = col_rt[find(i)], li[id][a[i]] = {0, 0}, p[i] = 0;
	for (int i = l; i <= r; i ++ ) a[i] = a[i] == x ? y : a[i];
	remake(id);
}

inline void modify_(int id, int x, int y)
{
	int ct = li[id][x].cnt;
	(sum[id] = 1ll * sum[id] % mod + 1ll * (y - x) % mod * 1ll * ct % mod) %= mod;
	(mul[id] = 1ll * mul[id] % mod * 1ll * inv_[y][ct] % mod * 1ll * fac_[x][ct] % mod) % mod;
	li[id][y].cnt += li[id][x].cnt;
	if (!li[id][y].h) li[id][y].h = li[id][x].h, col_rt[li[id][y].h] = y;
	else p[li[id][x].h] = li[id][y].h;
	li[id][x] = {0, 0};
}

inline void update(int l, int r, int x, int y)
{
	int p = pos[l], q = pos[r];
	if (p == q) modify(p, l, r, x, y);
	else
	{
		modify(p, l, R[p], x, y);
		modify(q, L[q], q, x, y);
		for (int i = p + 1; i < q; i ++ )
			modify_(i, x, y);
	}
}

inline int query(int l, int r)
{
//	for (int i = 1ll * l; i <= r; i ++ ) cout << find(i) << ' ';
//	cout << '\n'; 
	int sm = 0, ml = 1;
	int p = pos[l], q = pos[r];
	if (p == q)
	{
		for (int i = 1ll * l; i <= r; i ++ )
			(sm = 1ll * sm % mod + 1ll * col_rt[find(i)] % mod) %= mod,
			(ml = 1ll * ml % mod * 1ll * inv[col_rt[find(i)]] % mod) %= mod;
	}
	else
	{
//		cout << R[p] << '\n';
//		return 0; 
		for (int i = l; i <= R[p]; i ++ )
			(sm = 1ll * sm % mod + 1ll * col_rt[find(i)] % mod) %= mod,
			(ml = 1ll * ml % mod * 1ll * inv[col_rt[find(i)]] % mod) %= mod;
		for (int i = L[q]; i <= r; i ++ )
			(sm = 1ll * sm % mod + 1ll * col_rt[find(i)] % mod) %= mod,
			(ml = 1ll * ml % mod * 1ll * inv[col_rt[find(i)]] % mod) %= mod;
		for (int i = p + 1; i < q; i ++ )
			(sm = 1ll * sm % mod + 1ll * sum[i] % mod) %= mod,
			(ml = 1ll * ml % mod * 1ll * mul[i] % mod) %= mod;
	}
//	cout << sm << ' ' << ml << '\n';
	return 1ll * fac[sm] * 1ll * ml % mod;
}

signed main()
{
	cin >> n >> q;
	for (int i = 1; i <= n; i ++ ) cin >> a[i];
	
    init();
    int opt, l, r, x, y;
    while (q -- )
    {
    	scanf("%d%d%d", &opt, &l, &r);
    	if (opt & 1) scanf("%d%d", &x, &y), update(l, r, x, y);
    	else cout << query(l, r) << '\n';
	}
	
	return 0;
}
//zi yin hei hong cha
//ikbc c87  (*)
//xuanpai pd98
//jingdongjingzao k8 pro