Codeforce 1217E - Sum Queries

Posted on In Views:

题目链接：Codeforce 1217E

首先我们考虑一个Balanced Multiset总和的每个位置可能存在两种情况：

  • 总和\(s_i\)就是这个集合内某个数字\(x\)的第\(i\)位，除了\(x\)之外的其余数字的第\(i\)位均为\(0\)
  • 总和\(s_i\)就是这个集合内某个数字\(x\)的第\(i\)位，但是不满足除了\(x\)之外的其余数字的第\(i\)位均为\(0\)，所以\(\sum x_i \bmod 10 = s_i\)，这种情况下一定会产生进位
  • 经过分析可以知道第二种情况是不可能的，我们可以这样反证：如果第\(i\)位置是这种情况，第\(i+1\)位是会接受到第\(i\)位的进位，那么第\(i+1\)位就不可能是第一种情况，即第\(i+1\)位会产生进位，以此类推，最前面一位也会产生进位，假设这个进位的位置为\(p\)，这显然是不符合定义的，因为原集合当中\(p\)位置都是\(0\)，故不可能成立。

因此我们可以得到一个推论，任何一个Unbalanced Multiset，无论怎么添加元素，这个集合依旧是Unbalanced。那么我们要找一个和最小的Unbalanced Multiset，其实也就是找一个两个元素的集合，使得这两个元素不满足上述的第一类情况。简而言之，对于每个询问，我们需要找到一组\((a_i,a_j)\)，满足\(l \leq i < j \leq r\)，使得第一类Balanced条件被破坏，最小的\(a_i+a_j\)就是问题的答案。

考虑用线段树维护区间的一些信息。我们可以把一个十进制数按位置拆分，对于要维护的区间用一个长度为\(\lceil \log_{10} \max\{ a_i \} \rceil\)的数组来记录区间内的数中，那些不为\(0\)的位置被哪些数使用，这些数的最小值是多少。接着还需要一个变量来维护区间最小的\(a_i+a_j\)。在Push-Up操作的时候，第一个数组很好维护，我们考虑如何维护第二个量，这里记录为\(f_o\)，首先\(f \leq \min \{ f_l, f_r \}\)，\(f_o\)、\(f_l\)和\(f_r\)分别是线段树当前的根、左子树和右子树维护的\(a_i+a_j\)的值，这意味着在左半个区间选择两个或者在右半个区间选择两个，当然我们也可以在左区间选择一个，右区间选择一个，这个时候就要用我们维护的第一个量来更新第二个量，详见代码。

渐进时间复杂度\(O((n+m)\log n \times \lceil \log_{10} \max\{ a_i \} \rceil)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 200000 + 5;
const int MAX_S = 10;
const int INF = INT_MAX;
int tree[MAX_N * 4][MAX_S], opt[MAX_N * 4];
inline int ls(int o) {
    return o << 1;
}
inline int rs(int o) {
    return o << 1 | 1;
}
inline void pushUp(int o) {
    opt[o] = min(opt[ls(o)], opt[rs(o)]);
    for (int i = 0; i < 10; ++i) {
        tree[o][i] = min(tree[ls(o)][i], tree[rs(o)][i]);
        if (tree[ls(o)][i] != INF && tree[rs(o)][i] != INF) {
            opt[o] = min(opt[o], tree[ls(o)][i] + tree[rs(o)][i]);
        }
    }
}
void build(int o, int l, int r) {
    if (l == r) {
        opt[o] = INF;
        for (int i = 0; i < 10; ++i) {
            tree[o][i] = INF;
        }
        return;
    }
    int mid = (l + r) >> 1;
    build(ls(o), l, mid);
    build(rs(o), mid + 1, r);
    pushUp(o);
}
void update(int o, int l, int r, int pos, int val) {
    if (l == r) {
        int v = val;
        for (int i = 0; i < 10; ++i) {
            int u = v % 10;
            if (!u) tree[o][i] = INF;
            else tree[o][i] = val;
            v /= 10;
        }
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) update(ls(o), l, mid, pos, val);
    else update(rs(o), mid + 1, r, pos, val);
    pushUp(o);
}
struct Node {
    int uOpt, uT[MAX_S];
    Node() {
        for (int i = 0; i < 10; ++i) uT[i] = INF;
        uOpt = INF;
    }
};
Node query(int o, int l, int r, int L, int R) {
    if (L <= l && r <= R) {
        Node u;
        for (int i = 0; i < 10; ++i) {
            u.uT[i] = tree[o][i];
        }
        u.uOpt = opt[o];
        return u;
    }
    int mid = (l + r) >> 1;
    if (R <= mid) return query(ls(o), l, mid, L, R);
    if (L > mid) return query(rs(o), mid + 1, r, L, R);
    Node uL = query(ls(o), l, mid, L, R), uR = query(rs(o), mid + 1, r, L, R);
    Node u;
    u.uOpt = min(uL.uOpt, uR.uOpt);
    for (int i = 0; i < 10; ++i) {
        u.uT[i] = min(uL.uT[i], uR.uT[i]);
        if (uL.uT[i] != INF && uR.uT[i] != INF) u.uOpt = min(u.uOpt, uL.uT[i] + uR.uT[i]);
    }
    return u;
}
int n, m;
int a[MAX_N];
int main() {
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), update(1, 1, n, i, a[i]);
    for (int i = 1; i <= m; ++i) {
        int op, u, v;
        scanf("%d%d%d", &op, &u, &v);
        if (op == 1) update(1, 1, n, u, v);
        else {
            Node ans = query(1, 1, n, u, v);
            if (ans.uOpt == INF) puts("-1");
            else printf("%d\n", ans.uOpt);
        }
    }
    return 0;
}