题目就是给定一个 $n$ 位的 $k$ 进制数 $a$（可以有前导 $0$），定义 $a$ 从左往右数的第 $i$ 位为 $a_i$。现在需要支持以下四种操作：

1 x y：将 $a_x$ 改成 $y$。

2 l r：将 $a_l \sim a_r$ 升序排序。

3 l r：将 $a_l \sim a_r$ 降序排序。

4 l r：查询 $a_l \sim a_r$ 组合起来的数转 $10$ 进制后对 $998244353$ 取模的结果。

样例输入：

8 4 3
20112021
1 2 2
2 2 7
3 1 4
4 1 7

样例输出：

1808

数据范围：

$1 \leq n,m \leq 5 \times 10^4,2 \leq k \leq 10,1 \leq x \leq n,0 \leq y < k,1 \leq l \leq r \leq n$。

代码：

#include<bits/stdc++.h>
#define N 100000
#define M 400000
#define K 10
#define mod 998244353
#define ls d << 1
#define rs d << 1 | 1
#define int1 long long
using namespace std;
int1 n,m,k,op,x,y,aa[N + 5],p[N + 5],q[N + 5];//p[i]=(在k进制下1后面跟i个0),q[i]=(在k进制下的k个1) 
char ch;
struct Segment_Tree{
	int1 cnt[K + 5],sum,len,tag;//sum是这一段k进制数的和，cnt[i]是这一段里面数字i出现了几次，len是这段区间的长度，tag是懒标记
} a[M + 5];
void push_up(int1 d){
	for(int1 i = 0; i < k; i++){
		a[d].cnt[i] = a[ls].cnt[i] + a[rs].cnt[i];
	}
	a[d].sum = (a[ls].sum * p[a[rs].len] % mod + a[rs].sum) % mod;
	a[d].len = a[ls].len + a[rs].len;
	return ;
}
void build(int1 d,int1 l,int1 r){//建树 
	if(l == r){
		for(int1 i = 0; i < k; i++){
			a[d].cnt[i] = (aa[l] == i);
		}
		a[d].sum = aa[l];
		a[d].len = 1;
		return ;
	}
	int1 mid = (l + r) >> 1;
	build(ls,l,mid);
	build(rs,mid + 1,r);
	push_up(d);
	return ;
}
void f(int1 d,int1 s){//打标记 
	a[d].tag = s;
	for(int1 i = 0; i < k; i++){
		a[d].cnt[i] = (a[d].len * (s == i));
	}
	a[d].sum = q[a[d].len] * s % mod;
	return ;
}
void push_down(int1 d){
	if(a[d].tag){
		f(ls,a[d].tag);
		f(rs,a[d].tag);
		a[d].tag = 0;
	}
	return ;
}
void change(int1 d,int1 l,int1 r,int1 x,int1 y,int1 s){//区间修改 
//	cout<< "change:" << d << " " << l << " " << r << " " << x << " " << y << endl;
	if(l >= x && r <= y){
		f(d,s);
		return ;
	}
	push_down(d);
	int1 mid = (l + r) >> 1;
	if(x <= mid){
		change(ls,l,mid,x,y,s);
	}
	if(y > mid){
		change(rs,mid + 1,r,x,y,s);
	}
	push_up(d);
	return ;
}
void right_change(int1 d,int1 l,int1 r,int1 x,int1 y,int1 s){
	if(x <= y){
		change(d,l,r,x,y,s);
	}
	return ;
}
Segment_Tree query(int1 d,int1 l,int1 r,int1 x,int1 y){//区间查询 
//	cout<< "query:" << d << " " << l << " " << r << " " << x << " " << y << endl;
	if(l >= x && r <= y){
		return a[d];
	}
	push_down(d);
	int1 mid = (l + r) >> 1;
	Segment_Tree dd,ll,rr;
	for(int1 i = 0; i < k; i++){
		dd.cnt[i] = ll.cnt[i] = rr.cnt[i] = 0;
	}
	dd.sum = dd.len = ll.sum = ll.len = rr.sum = rr.len = 0;
	if(x <= mid){
		ll = query(ls,l,mid,x,y);
	}
	if(y > mid){
		rr = query(rs,mid + 1,r,x,y);
	}
	for(int1 i = 0; i < k; i++){
		dd.cnt[i] = ll.cnt[i] + rr.cnt[i];
	}
	dd.sum = (ll.sum * p[rr.len] % mod + rr.sum) % mod;
	dd.len = ll.len + rr.len;
	return dd;
}
int main(){//校内oj，提交要开文件读写 
	freopen("ksystem.in","r",stdin);
	freopen("ksystem.out","w",stdout);
	cin >> n >> m >> k;
	p[0] = 1;
	for(int1 i = 1; i <= n; i++){
		p[i] = p[i - 1] * k % mod;
		q[i] = (q[i - 1] * k + 1) % mod;
//		cout<< p[i] << " " << q[i] << endl;
		cin >> ch;
		aa[i] = ch ^ 48;
	}
	build(1,1,n);
	while(m--){
		cin >> op >> x >> y;
		if(op == 1){//单点修改 
			change(1,1,n,x,x,y);
		}else if(op == 2){//排序本质上还是修改
			int1 sum = 0;
			Segment_Tree owo = query(1,1,n,x,y);
			for(int1 i = 0; i < k; i++){
				right_change(1,1,n,x + sum,x + sum + owo.cnt[i] - 1,i);
				sum += owo.cnt[i];
			}
		}else if(op == 3){//只不过是区间修改 
			int1 sum = 0;
			Segment_Tree owo = query(1,1,n,x,y);
			for(int1 i = k - 1; i >= 0; i--){
				right_change(1,1,n,x + sum,x + sum + owo.cnt[i] - 1,i);
				sum += owo.cnt[i];
			}
		}else{//区间查询 
			cout<< query(1,1,n,x,y).sum << endl;
		}
	}
	return 0;
}

WA声一片，大佬救命QAQ