Sum Queries? CodeForces

Sum Queries? CodeForces - 1217E (线段树)

题意：

定义一个集合为(balanced)的，当且仅当集合内数字之和的每个十进制位，都与集合中某个数该位相同。否则，称该集合为(unbalanced)的。

给定一个长度为(n)的序列，(q)次询问一个区间内数字之和最小的(unbalanced)集合，输出数字之和。若没有输出(-1)。

(n,q<=200000)。

题解：

可以发现，如果存在(unbalanced)集合，那么最小的一定是只两个数组成的集合。这两个数存在一个十进制位不都为(0)。

建立十棵线段树，维护每个位置上该位非(0)的区间最小值，更新最小值时更新答案。如果查询时，如果区间需要分开查询，不要忘了分开之后的多个区间之间的数也是会相互影响的，应该枚举每个十进制位，将多个区间的最小值合并来更新答案。

时间复杂度(O(10×(n+m)log(n)))。

代码：

#include <bits/stdc++.h>
#define fopi freopen("in.txt", "r", stdin)
#define fopo freopen("out.txt", "w", stdout)
using namespace std;
const int inf = 2e9 + 10;
const int maxn = 2e5 + 10;

struct Node {
    int l, r, Min[12];
}t[maxn*4];
int Ans[maxn*4], a[maxn], tmp[maxn];
int ans;

void push_up(int id) {
    Ans[id] = inf;
    for (int i = 1; i <= 10; i++) {
        if (t[id*2].Min[i] < inf && t[id*2+1].Min[i] < inf)
            Ans[id] = min(Ans[id], t[id*2].Min[i] + t[id*2+1].Min[i]);
        t[id].Min[i] = min(t[id*2].Min[i], t[id*2+1].Min[i]);
    }
    Ans[id] = min(Ans[id], min(Ans[id*2], Ans[id*2+1]));
}

void build(int id, int l, int r) {
    Ans[id] = inf;
    t[id].l = l, t[id].r = r;
    if (l == r) {
        int res = a[l];
        for (int i = 1; i <= 10; i++) {
            if (res % 10 == 0) t[id].Min[i] = inf;
            else t[id].Min[i] = a[l];
            res /= 10;
        }
        return;
    }
    int mid = (l+r) / 2;
    build(id*2, l, mid), build(id*2+1, mid+1, r);
    push_up(id);
}

void update(int id, int l, int x) {
    if (t[id].l == l && t[id].r == l) {
        int res = x;
        for (int i = 1; i <= 10; i++) {
            if (res % 10 == 0) t[id].Min[i] = inf;
            else t[id].Min[i] = x;
            res /= 10;
        }
        return;
    }
    int mid = (t[id].l + t[id].r) / 2;
    if (l <= mid) update(id*2, l, x);
    else update(id*2+1, l, x);
    push_up(id);
}

void query(int id, int l, int r) {
    if (l <= t[id].l && r >= t[id].r) {
        for (int i = 1; i <= 10; i++) {
            if (tmp[i] < inf && t[id].Min[i] < inf) {
                ans = min(ans, tmp[i] + t[id].Min[i]);
            }
            tmp[i] = min(tmp[i], t[id].Min[i]);
        }
        ans = min(ans, Ans[id]);
        return;
    }
    int mid = (t[id].l + t[id].r) / 2;
    if (r <= mid) query(id*2, l, r);
    else if (l > mid) query(id*2+1, l, r);
    else query(id*2, l, mid), query(id*2+1, mid+1, r);
}

int n, m, res;
int main() {
    //fopi;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if (op == 1) update(1, x, y);
        else {
            for (int i = 1; i <= 10; i++) tmp[i] = inf;
            ans = inf;
            query(1, x, y);
            printf("%d
", ans >= inf ? -1 : ans);
        }
    }
}