Educational Codeforces Round 72 (Rated for Div. 2) E. Sum Queries? (线段树)

题目链接
大意：给你n个数，支持修改和查询操作
查询一个和最小的集合，使得该集合不平衡(就是不满足：集合的和的所有位上的数字等于集合中的至少一个数的同位)

思路：显然我们要找到某一位上存在两个不为0的最小数，这两个数加起来就是答案。
显然我们要拆分每一位建10颗线段树。具体做法：把每个数拆开，看每一位是多少，如果是0，那么贡献就是无穷大，否则就是原本的数。
修改就算重新拆一下数往上但点更新即可。。。
然后我们查询就是查10颗线段树上的前2小数的和。
细节见代码：

#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define LL long long
#define SZ(X) X.size()
#define pii pair<int,int>
#define ALL(X) X.begin(),X.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 2e5 + 11;
const LL inf = 1e15;
int n, a[N], m;
LL t[10][N << 2];
#define mid (l+r>>1)
#define ls o<<1
#define rs o<<1|1
LL b[10][N];
LL A[10][N << 2], B[10][N << 2];
void build(int s, int o, int l, int r) {
    if (l == r) {
        A[s][o] = b[s][l];
        B[s][o] = inf;
        return ;
    }
    build(s, ls, l, mid);
    build(s, rs, mid + 1, r);
    A[s][o] = min(A[s][ls], A[s][rs]);
    B[s][o] = min(B[s][ls], B[s][rs]);
    B[s][o] = min(B[s][o], max(A[s][ls], A[s][rs]));
    return ;
}
void up(int s, int o, int l, int r, int pos, LL d) {
    if (l == r) {
        A[s][o] = d;
        B[s][o] = inf;
        return ;
    }
    if (pos <= mid)up(s, ls, l, mid, pos, d);
    else up(s, rs, mid + 1, r, pos, d);
    A[s][o] = min(A[s][ls], A[s][rs]);
    B[s][o] = min(B[s][ls], B[s][rs]);
    B[s][o] = min(B[s][o], max(A[s][ls], A[s][rs]));
    return ;
}
pair<LL, LL> get(int s, int o, int l, int r, int x, int y) {
    if (x <= l && y >= r) {
        return {A[s][o], B[s][o]};
    }
    pair<LL, LL>ans = {inf, inf};
    if (x <= mid) {
        pair<LL, LL>res = get(s, ls, l, mid, x, y);
        ans = res;
    }
    if (y > mid && A[s][rs] < ans.se) {
        pair<LL, LL>res = get(s, rs, mid + 1, r, x, y);
        LL x = ans.fi, y = ans.se;
        ans.se = min(y, res.se);
        ans.se = min(ans.se, max(x, res.fi));
        ans.fi = min(x, res.fi);
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        int T = a[i];
        for (; cnt < 10; cnt++) {
            if (T % 10 == 0) {
                b[cnt][i] = inf;
            } else b[cnt][i] = a[i];
            T /= 10;
        }
    }
    for (int i = 0; i < 10; i++)build(i, 1, 1, n);
    for (int i = 1; i <= m; i++) {
        int l, r, z;
        scanf("%d%d%d",&l,&r,&z);
        if (l == 1) {
            LL Z = z;
            for (int j = 0; j < 10; j++) {
                if (Z % 10 == 0) {
                    b[j][r] = inf;
                    up(j, 1, 1, n, r, inf);
                } else {
                    b[j][r] = z;
                    up(j, 1, 1, n, r, z);
                }
                Z /= 10;
            }
        } else {
            LL can = 1e18;
            for (int i = 0; i < 10; i++) {
                auto res = get(i, 1, 1, n, r, z);
                LL ch = res.fi + res.se;
                can = min(can, ch);
            }
            printf("%d\n", (can >= inf ? -1 : can) );
        }
    }
    return 0;
}