题意
记$sum$为一个多重集的所有元素的和
对于$sum$的每一个数位，如果多重集中至少存在一个元素的同一数位与$sum$的此数位相同，我们称这个多重集是平衡的，否则称它是不平衡的
给出一个数组，有两种操作
1.单点修改
2.询问一个区间中所有不平衡的多重集的$sum$中的最小值
数据范围：$1 \le n,m \le 2 \cdot 10^5,1 \le a_i \le 10^9$
题解
首先通过给出的样例猜想：$sum$的每一位上只能对应有$1$个非$0$的数字
容易证明：若同一位上存在$2$个及以上非$0$数字，想要使$sum$中的对应位与其中一个相等，肯定需要进位；而进位后下一位又与$sum$中它的对应位不等，再次需要进位；以此类推，总位数一定会超过$sum$的总位数，矛盾
反之，若一个多重集是不平衡的，那它一定有某一位上存在$2$个及以上非$0$的数字；作为这个多重集的子集，我们只需要考虑该位上最小的$2$个元素的和；而对于其它数位，以同样的方式记录该值，最后的答案即为区间的最小值
inline void init(int v){
int t=v;
for(int i=1;i<L && t;i++,t/=10)
if(t%10!=0)
mi[i]=Min(mi[i],v);
}因为取$min$满足区间和性质，可以用线段树维护；具体方法是：线段树的节点维护该区间的答案与该区间的每个数位上非$0$的数的最小值，合并区间时用同一位的最小值的和去更新区间的答案
注意回答询问的时候也需要合并答案，可以将区间合并重载为$+$，方便使用
inline node operator + (const node& x){
node res;
res.w=Min(w,x.w);
for(int i=1;i<L;i++){
res.mi[i]=Min(mi[i],x.mi[i]);
if(mi[i]<INF && x.mi[i]<INF)
res.w=Min(res.w,mi[i]+x.mi[i]);
}
return res;
}代码：
#include<iostream>
#include<cstdio>
#include<memory.h>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
const int N=2e5+10;
const int L=10;
const int INF=2e9;
int n,m,op,x,y;
int a[N];
template <typename T>
inline T Min(T a,T b){
return a<b?a:b;
}
struct node{
int w,mi[L];
inline node(){
w=INF;
for(int i=1;i<L;i++)
mi[i]=INF;
}
inline void init(int v){
int t=v;
for(int i=1;i<L && t;i++,t/=10)
if(t%10!=0)
mi[i]=Min(mi[i],v);
}
inline node operator + (const node& x){
node res;
res.w=Min(w,x.w);
for(int i=1;i<L;i++){
res.mi[i]=Min(mi[i],x.mi[i]);
if(mi[i]<INF && x.mi[i]<INF)
res.w=Min(res.w,mi[i]+x.mi[i]);
}
return res;
}
} T[N<<2];
inline void pushUp(int rt){
T[rt]=T[ls]+T[rs];
}
void build(int rt,int l,int r){
if(l==r){
T[rt].init(a[l]);
return ;
}
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushUp(rt);
}
void update(int rt,int l,int r,int p,int k){
if(l==r){
T[rt]=node();
T[rt].init(k);
return ;
}
int mid=l+r>>1;
if(p<=mid)
update(ls,l,mid,p,k);
else update(rs,mid+1,r,p,k);
pushUp(rt);
}
node query(int rt,int l,int r,int L,int R){
if(l>=L && r<=R){
return T[rt];
}
node res;
int mid=l+r>>1;
if(L<=mid)
res=res+query(ls,l,mid,L,R);
if(R>mid)
res=res+query(rs,mid+1,r,L,R);
return res;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,1,n);
for(;m--;){
scanf("%d%d%d",&op,&x,&y);
if(op==1)
update(1,1,n,x,y);
else{
int t=query(1,1,n,x,y).w;
printf("%d\n",t<INF?t:-1);
}
}
return 0;
}