数列a由n个数字组成，下标从1到n，进行q次操作。操作有两种：1.将ai中的数字x改为y，i∈[l,r]；2.求∑ai，i∈[l,r]。
比如，将11984381中的8改为4，就变为了11944341。再将4改为1，就变为了11911311。
1≤n≤105，1≤q≤105，1≤l≤r≤n，1≤ai≤109，0≤x≤9，1≤y≤9。
数据保证ai没有前导0。
不难想到按位建10颗线段树，存储每位数字为i的区间的贡献，最终答案为∑i * sum(i)
问题在于lazy标记的下放，放的不好比暴力算法还多一个log
一个很巧妙的方法是lazy[i]标记表示当前区间内的数位i全部变成lazy[i],那么pushdown的操作就是每次更新下层结点，然后将本层结点初始化，即lazy[i] = i的操作来删除下放标记，pushup就只需更新区间和即可。
总的来说 本题的难点为lazy标记不太好想 写起来似乎也不太好写
#include<bits/stdc++.h> int read(){ int x = 0,f = 1; char c = getchar(); while(c < '0' || c > '9'){ if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9'){ x = x * 10 + c - '0'; c = getchar(); } return x * f; } #define LL long long const int maxn = 1e5 + 10; int N,M; int a[maxn]; struct Tree{ LL sum[10]; int to[10]; void init(){ for(int i = 0 ; i < 10; i ++) sum[i] = 0; } }tree[maxn << 2]; void Pushup(int t){ tree[t].init(); for(int i = 0 ; i < 10; i ++){ tree[t].sum[tree[t << 1].to[i]] += tree[t << 1].sum[i]; tree[t].sum[tree[t << 1 | 1].to[i]] += tree[t << 1 | 1].sum[i]; } } LL tmp[10]; void Pushdown(int t){ for(int i = 0 ; i < 10; i ++){ tree[t << 1].to[i] = tree[t].to[tree[t << 1].to[i]]; tree[t << 1 | 1].to[i] = tree[t].to[tree[t << 1 | 1].to[i]]; } for(int i = 0 ; i < 10; i ++) tmp[i] = 0; for(int i = 0 ; i < 10; i ++) tmp[tree[t].to[i]] += tree[t].sum[i]; for(int i = 0 ; i < 10; i ++) tree[t].sum[i] = tmp[i]; for(int i = 0 ; i < 10; i ++) tree[t].to[i] = i; } void Build(int t,int l,int r){ for(int i = 0 ; i < 10; i ++) tree[t].to[i] = i; if(l == r){ LL b = 1; int x = a[l]; while(x){ tree[t].sum[(x % 10)] += b; b *= 10; x /= 10; } return; } int m = l + r >> 1; Build(t << 1,l,m); Build(t << 1 | 1,m + 1,r); Pushup(t); } void update(int t,int l,int r,int x,int y,int L,int R){ int m = L + R >> 1; if(l <= L && R <= r){ for(int i = 0 ; i <= 9; i ++) if(tree[t].to[i] == x) tree[t].to[i] = y; return; } Pushdown(t); if(r <= m) update(t << 1,l,r,x,y,L,m); else if(l > m) update(t << 1 | 1,l,r,x,y,m + 1,R); else{ update(t << 1,l,m,x,y,L,m); update(t << 1 | 1,m + 1,r,x,y,m + 1,R); } Pushup(t); } LL query(int t,int l,int r,int L,int R){ int m = L + R >> 1; if(l <= L && R <= r){ LL ans = 0; for(int i = 0 ; i <= 9; i ++) ans += tree[t].to[i] * tree[t].sum[i]; return ans; } Pushdown(t); if(r <= m) return query(t << 1,l,r,L,m); else if(l > m) return query(t << 1 |1,l,r,m + 1,R); return query(t << 1,l,m,L,m) + query(t << 1 | 1,m + 1,r,m + 1,R); } int main(){ scanf("%d%d",&N,&M); for(int i = 1; i <= N ; i ++) a[i] = read(); Build(1,1,N); while(M--){ int op = read(),l = read(),r = read(); if(op == 1){ int x = read(),y = read(); update(1,l,r,x,y,1,N); }else{ printf("%lld ",query(1,l,r,1,N)); } } return 0; }