/* 定义：多重集s的元素和是sum，对于sum的第i位为x，如果s里找不到第i位也是x的元素，那么称这个多重集为bad， 现在给定一个 序列a 两种操作 1 i x：将序列第i个元素改为x 2 l r: a[l..r]组成的多重集中，找一个和最小的bad子集，如果没有这样的子集，输出-1 如果集合中有两个数A，B在某一位都不为0，那么这个集合必定为bad，那么在区间[l..r]里找一个最小的bad集合，必定是两个数之和 我们只要找在该区间最小的两个在某一位都不为0的数即可 线段树每个结点开数组Min[10][2]维护a[l..r]里第i位不为0的最小和次小数 */ #include<bits/stdc++.h> using namespace std; #define N 200005 #define INF 0x3f3f3f3f3f #define ll long long ll n,a[N],m; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 struct Node{ll x[10][2];}t[N<<2]; ll buf[10]; void calc(ll x){ for(int i=0;i<10;i++) buf[i]=x%10,x/=10; } Node merge(Node a,Node b){ Node res; for(int i=0;i<10;i++) res.x[i][0]=res.x[i][1]=INF; for(int i=0;i<10;i++){ ll m1=a.x[i][0],m2=b.x[i][0]; res.x[i][0]=min(m1,m2); res.x[i][1]=max(m1,m2); res.x[i][1]=min(res.x[i][1],a.x[i][1]); res.x[i][1]=min(res.x[i][1],b.x[i][1]); } return res; } void build(int l,int r,int rt){ if(l==r){ calc(a[l]); for(int i=0;i<10;i++){ if(buf[i])t[rt].x[i][0]=a[l]; else t[rt].x[i][0]=INF; t[rt].x[i][1]=INF; } return; } int m=l+r>>1; build(lson);build(rson); t[rt]=merge(t[rt<<1],t[rt<<1|1]); } void update(ll pos,ll v,int l,int r,int rt){ if(l==r){ calc(v); for(int i=0;i<10;i++){ if(buf[i])t[rt].x[i][0]=v; else t[rt].x[i][0]=INF; t[rt].x[i][1]=INF; } return; } int m=l+r>>1; if(pos<=m)update(pos,v,lson); else update(pos,v,rson); t[rt]=merge(t[rt<<1],t[rt<<1|1]); } Node query(ll L,ll R,ll l,ll r,ll rt){ if(L<=l && R>=r)return t[rt]; int m=l+r>>1; Node res; for(int i=0;i<10;i++) res.x[i][0]=res.x[i][1]=INF; if(L<=m)res=merge(res,query(L,R,lson)); if(R>m)res=merge(res,query(L,R,rson)); return res; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; build(1,n,1); while(m--){ ll op,l,r; scanf("%lld%lld%lld",&op,&l,&r); if(op==1) update(l,r,1,n,1); else { Node t=query(l,r,1,n,1); ll ans=INF; for(int i=0;i<10;i++) ans=min(ans,t.x[i][0]+t.x[i][1]); if(ans>=INF)puts("-1"); else cout<<ans<<' '; } } }