题目

给出一个长度为 $n$ 的 $k$ 进制数，可能含有前导 $0$，你需要实现以下 $4$ 种操作，共 $m$ 次。

• 1 x y：将第 $x$ 位上的数改为 $y$；
• 2 l r：将第 $l$ 位到第 $r$ 位升序排列；
• 3 l r：将第 $l$ 位到第 $r$ 位降序排列；
• 4 l r：求第 $l$ 位到第 $r$ 位所组成的 $k$ 进制数转为 $10$ 进制数的结果，结果对 $998244353$ 取模。

分析

看到排序，一眼盯榛，鉴定为春春线段树。开 $k$ 个线段树就好了，求操作 $4$ 也不难想，有 t[p].val=t[p<<1].val*pow(k,t[p<<1|1].r-t[p<<1|1].l+1)+t[p<<1|1].val 的关系。

代码

const int N = 5e4 + 4;
const ll mod = 998244353ll;

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

int n, m, k;
char a[N];
int kpow[N], divkm1;

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

struct node {
	int val, len;
};

struct SegmentTree {
	struct Tree {
		int l, r, lzy, cnt, val;
	}t[N << 2];
	int base;
	void Init(int k){
		base = k;
		Build(1, 1, n);
	}
	void Build(int p, int l, int r) {
		t[p].lzy = -1;
		t[p].l = l, t[p].r = r;
		if (t[p].l == t[p].r) {
			t[p].cnt = (a[l] - '0') == base;
			t[p].val = t[p].cnt * base;
			return ;
		}
		int mid = (t[p].l + t[p].r) >> 1;
		Build(p << 1, l, mid);
		Build(p << 1 | 1, mid + 1, r);
		t[p].cnt = (t[p << 1].cnt + t[p << 1 | 1].cnt) % mod;
		t[p].val = (1ll * t[p << 1].val * kpow[t[p << 1 | 1].r - t[p << 1 | 1].l + 1] % mod + t[p << 1 | 1].val) % mod;
	}
	void pushdown(int p) {
		if (t[p].lzy == -1) return;
		t[p << 1 | 1].cnt = (t[p << 1 | 1].r - t[p << 1 | 1].l + 1) * t[p].lzy;
		t[p << 1].cnt = (t[p << 1].r - t[p << 1].l + 1) * t[p].lzy;
		t[p << 1 | 1].val = t[p].lzy * 1ll * (kpow[t[p << 1 | 1].r - t[p << 1 | 1].l + 1] - 1 + mod) % mod * divkm1 % mod * base % mod;
		t[p << 1].val = t[p].lzy * 1ll * (kpow[t[p << 1].r - t[p << 1].l + 1] - 1 + mod) % mod * divkm1 % mod * base % mod;
		t[p << 1].lzy = t[p << 1 | 1].lzy = t[p].lzy;
		t[p].lzy = -1;
	}
	void ModifyPoint(int p, int x, bool val) {
		if (t[p].l == t[p].r) {
			t[p].cnt = val;
			t[p].val = val * base;
			return ;
		}
		pushdown(p);
		int mid = (t[p].l + t[p].r) >> 1;
		if (x <= mid) ModifyPoint(p << 1, x, val);
		else ModifyPoint(p << 1 | 1, x, val);
		t[p].cnt = (t[p << 1].cnt + t[p << 1 | 1].cnt) % mod;
		t[p].val = (1ll * t[p << 1].val * kpow[t[p << 1 | 1].r - t[p << 1 | 1].l + 1] % mod + t[p << 1 | 1].val) % mod;
	}
	void ModifyRange(int p, int l, int r, bool val) {
		if (l <= t[p].l && t[p].r <= r) {
			t[p].cnt = (t[p].r - t[p].l + 1) * val;
			t[p].val = val * 1ll * (kpow[t[p].r - t[p].l + 1] - 1 + mod) % mod * divkm1 % mod * base % mod;
			t[p].lzy = val;
			return;
		}
		pushdown(p);
		int mid = (t[p].l + t[p].r) >> 1;
		if (l <= mid) ModifyRange(p << 1, l, r, val);
		if (r > mid) ModifyRange(p << 1 | 1, l, r, val);
		t[p].cnt = (t[p << 1].cnt + t[p << 1 | 1].cnt) % mod;
		t[p].val = (1ll * t[p << 1].val * kpow[t[p << 1 | 1].r - t[p << 1 | 1].l + 1] % mod + t[p << 1 | 1].val) % mod;
	}
	int QueryCount(int p, int l, int r) {
		if (l <= t[p].l && t[p].r <= r) {
			return t[p].cnt;
		}
		pushdown(p);
		int mid = (t[p].l + t[p].r) >> 1;
		int ans = 0;
		if (l <= mid) ans += QueryCount(p << 1, l, r);
		if (r > mid) ans += QueryCount(p << 1 | 1, l, r);
		return ans;
	}
	node QueryValue(int p, int l, int r) {
		if (l <= t[p].l && t[p].r <= r) {
			return (node){t[p].val, t[p].r - t[p].l + 1};
		}
		pushdown(p);
		int mid = (t[p].l + t[p].r) >> 1;
		node a, b;
		bool f1 = 0, f2 = 0;
		if (l <= mid) a = QueryValue(p << 1, l, r), f1 = 1;
		if (r > mid) b = QueryValue(p << 1 | 1, l, r), f2 = 1;
		if (f1 && f2) return (node) {(a.val * 1ll * kpow[b.len] % mod + b.val) % mod, a.len + b.len};
		if (f1) return (node) {a.val, a.len};
		if (f2) return (node) {b.val, b.len};
		return (node) {0, 0};
	}
}t[10];

int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	n = Read(), m = Read(), k = Read();
	kpow[0] = 1;
	for (int i = 1; i <= n; i++) kpow[i] = 1ll * kpow[i - 1] * k % mod;
	divkm1 = qpow(k - 1, mod - 2);
	scanf ("%s", a + 1);
	for (int i = 0; i < k; i++) t[i].Init(i);
	for (; m--; ) {
		int o = Read(), l = Read(), r = Read();
		if (o == 1) {
			for (int i = 0; i < k; i++) t[i].ModifyPoint(1, l, 0);
			t[r].ModifyPoint(1, l, 1);
			continue;
		}
		if (o == 2) {
			int nowl = l;
			for (int i = 0; i < k; i++) {
				int len = t[i].QueryCount(1, l, r);
				t[i].ModifyRange(1, l, r, 0);
				t[i].ModifyRange(1, nowl, nowl + len - 1, 1);
				nowl = nowl + len;
			}
			continue;
		}
		if (o == 3) {
			int nowl = l;
			for (int i = k - 1; i >= 0; i--) {
				int len = t[i].QueryCount(1, l, r);
				t[i].ModifyRange(1, l, r, 0);
				t[i].ModifyRange(1, nowl, nowl + len - 1, 1);
				nowl = nowl + len;
			}
			continue;
		}
		if (o == 4) {
			int ans = 0;
			for (int i = 0; i < k; i++) ans = (ans + 1ll * t[i].QueryValue(1, l, r).val) % mod;
			printf ("%d\n", ans);
		}
	}
	return 0;
}