Sum Queries? (Codeforces 1217E)
Tags: Greedy, data structures

Let's define a balanced multiset the following way. Write down the sum of all elements of the multiset in its decimal representation. For each position of that number check if the multiset includes at least one element such that the digit of the element and the digit of the sum at that position are the same. If that holds for every position, then the multiset is balanced. Otherwise it's unbalanced.For example, multiset $$$\{20, 300, 10001\}$$$ is balanced and multiset $$$\{20, 310, 10001\}$$$ is unbalanced:   The red digits mark the elements and the positions for which these elements have the same digit as the sum. The sum of the first multiset is $$$10321$$$, every position has the digit required. The sum of the second multiset is $$$10331$$$ and the second-to-last digit doesn't appear in any number, thus making the multiset unbalanced.You are given an array $$$a_1, a_2, \dots, a_n$$$, consisting of $$$n$$$ integers.You are asked to perform some queries on it. The queries can be of two types:  $$$1~i~x$$$ — replace $$$a_i$$$ with the value $$$x$$$;  $$$2~l~r$$$ — find the unbalanced subset of the multiset of the numbers $$$a_l, a_{l + 1}, \dots, a_r$$$ with the minimum sum, or report that no unbalanced subset exists. Note that the empty multiset is balanced.For each query of the second type print the lowest sum of the unbalanced subset. Print -1 if no unbalanced subset exists.

Input: The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the number of elements in the array and the number of queries, respectively.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i < 10^9$$$).Each of the following $$$m$$$ lines contains a query of one of two types:  $$$1~i~x$$$ ($$$1 \le i \le n$$$, $$$1 \le x < 10^9$$$) — replace $$$a_i$$$ with the value $$$x$$$;  $$$2~l~r$$$ ($$$1 \le l \le r \le n$$$) — find the unbalanced subset of the multiset of the numbers $$$a_l, a_{l + 1}, \dots, a_r$$$ with the lowest sum, or report that no unbalanced subset exists. It is guaranteed that there is at least one query of the second type.

Output: For each query of the second type print the lowest sum of the unbalanced subset. Print -1 if no unbalanced subset exists.

Note: All the subsets of multiset $$$\{20, 300, 10001\}$$$ are balanced, thus the answer is -1.The possible unbalanced subsets in the third query are $$$\{20, 310\}$$$ and $$$\{20, 310, 10001\}$$$. The lowest sum one is $$$\{20, 310\}$$$. Note that you are asked to choose a subset, not a subsegment, thus the chosen elements might not be adjancent in the array.The fourth query includes only the empty subset and subset $$$\{20\}$$$. Both of them are balanced.The last query includes the empty subset and the subsets $$$\{20\}$$$, $$$\{20\}$$$ and $$$\{20, 20\}$$$. Only $$$\{20, 20\}$$$ is unbalanced, its sum is $$$40$$$. Note that you are asked to choose a multiset, thus it might include equal elements.

Sample Inputs:
4 5
300 10001 20 20
2 1 3
1 1 310
2 1 3
2 3 3
2 3 4

Sample Outputs:
-1
330
-1
40

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]

class segtree:

    def __init__(self, init, func, ide):
        self.n = len(init)
        self.func = func
        self.ide = ide
        self.size = 1 << (self.n - 1).bit_length()
        self.tree = [self.ide for i in range(2 * self.size)]
        for i in range(self.n):
            self.tree[self.size + i] = init[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.func(self.tree[2 * i], self.tree[2 * i | 1])

    def update(self, k, x):
        k += self.size
        self.tree[k] = x
        k >>= 1
        while k:
            self.tree[k] = self.func(self.tree[2 * k], self.tree[k * 2 | 1])
            k >>= 1

    def get(self, i):
        return self.tree[i + self.size]

    def query(self, l, r):
        l += self.size
        r += self.size
        l_res = self.ide
        r_res = self.ide
        while l < r:
            if l & 1:
                l_res = self.func(l_res, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_res = self.func(self.tree[r], r_res)
            l >>= 1
            r >>= 1
        return self.func(l_res, r_res)

    def debug(self, s=10):
        print([self.get(i) for i in range(min(self.n, s))])
(n, q) = map(int, input().split())
a = list(map(int, input().split()))

def tuple_to_int(L, R):
    return (L << 31) + R

def int_to_tuple(x):
    L = x >> 31
    R = x & mask
    return (L, R)

def ope(L, R):
    (L0, L1) = int_to_tuple(L)
    (R0, R1) = int_to_tuple(R)
    if L0 <= R0:
        return tuple_to_int(L0, min(R0, L1))
    else:
        return tuple_to_int(R0, min(R1, L0))
mask = (1 << 31) - 1
inf = (1 << 31) - 1
E = tuple_to_int(inf, inf)
b = a.copy()
segs = []
for i in range(9):
    c = [E] * n
    for j in range(n):
        if b[j] % 10 != 0:
            c[j] = tuple_to_int(a[j], inf)
        b[j] //= 10
    segs.append(segtree(c, ope, E))
for _ in range(q):
    (t, x, y) = map(int, input().split())
    if t == 1:
        x -= 1
        a[x] = y
        for i in range(9):
            if y % 10 != 0:
                segs[i].update(x, tuple_to_int(a[x], inf))
            else:
                segs[i].update(x, E)
            y //= 10
    else:
        ans = inf
        l = x - 1
        r = y - 1
        for i in range(9):
            (p, q) = int_to_tuple(segs[i].query(l, r + 1))
            ans = min(ans, p + q)
        if ans == inf:
            ans = -1
        print(ans)

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]

class segtree:

    def __init__(self, init, func, ide):
        self.n = len(init)
        self.func = func
        self.ide = ide
        self.size = 1 << (self.n - 1).bit_length()
        self.tree = [self.ide for i in range(2 * self.size)]
        for i in range(self.n):
            self.tree[self.size + i] = init[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.func(self.tree[2 * i], self.tree[2 * i | 1])

    def update(self, k, x):
        k += self.size
        self.tree[k] = x
        k >>= 1
        while k:
            self.tree[k] = self.func(self.tree[2 * k], self.tree[k * 2 | 1])
            k >>= 1

    def get(self, i):
        return self.tree[i + self.size]

    def query(self, l, r):
        l += self.size
        r += self.size
        l_res = self.ide
        r_res = self.ide
        while l < r:
            if l & 1:
                l_res = self.func(l_res, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_res = self.func(self.tree[r], r_res)
            l >>= 1
            r >>= 1
        return self.func(l_res, r_res)

    def debug(self, s=10):
        print([self.get(i) for i in range(min(self.n, s))])
(n, q) = map(int, input().split())
a = list(map(int, input().split()))

def tuple_to_int(L, R):
    return (L << 31) + R

def int_to_tuple(x):
    L = x >> 31
    R = x & mask
    return (L, R)

def ope(L, R):
    (L0, L1) = int_to_tuple(L)
    (R0, R1) = int_to_tuple(R)
    if L0 <= R0:
        return tuple_to_int(L0, min(R0, L1))
    else:
        return tuple_to_int(R0, min(R1, L0))
mask = (1 << 31) - 1
inf = (1 << 31) - 1
E = tuple_to_int(inf, inf)
b = a.copy()
segs = []
ANS = []
for i in range(9):
    c = [E] * n
    for j in range(n):
        if b[j] % 10 != 0:
            c[j] = tuple_to_int(a[j], inf)
        b[j] //= 10
    segs.append(segtree(c, ope, E))
for _ in range(q):
    (t, x, y) = map(int, input().split())
    if t == 1:
        x -= 1
        a[x] = y
        for i in range(9):
            if y % 10 != 0:
                segs[i].update(x, tuple_to_int(a[x], inf))
            else:
                segs[i].update(x, E)
            y //= 10
    else:
        ans = inf
        l = x - 1
        r = y - 1
        for i in range(9):
            (p, q) = int_to_tuple(segs[i].query(l, r + 1))
            ans = min(ans, p + q)
        if ans == inf:
            ans = -1
        ANS.append(ans)
print(*ANS, sep='\n')

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def segment_tree(n, a):
    i = 2
    while True:
        if i >= n * 2:
            tree = [inf] * i
            break
        else:
            i *= 2
    l = len(tree) // 2
    for i in range(l, l + len(a)):
        tree[i] = a[i - l]
    for i in range(l - 1, 0, -1):
        tree[i] = min(tree[2 * i], tree[2 * i + 1])
    return tree

def update(i, x, tree):
    i += len(tree) // 2
    tree[i] = x
    i //= 2
    while True:
        if i == 0:
            break
        tree[i] = min(tree[2 * i], tree[2 * i + 1])
        i //= 2
    return

def get_min(s, t, tree):
    s += len(tree) // 2
    t += len(tree) // 2
    ans = inf
    while s <= t:
        if s % 2 == 0:
            s //= 2
        else:
            ans = min(ans, tree[s])
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans = min(ans, tree[t])
            t = (t - 1) // 2
    return ans
(n, m) = map(int, input().split())
a = [0] + list(map(int, input().split()))
inf = 3 * pow(10, 14)
b = [[inf] for _ in range(10)]
for i in range(1, n + 1):
    c = a[i] * (n + 1) + i
    x = list(str(a[i]))
    x.reverse()
    for j in range(len(x)):
        if int(x[j]):
            b[j].append(c)
        else:
            b[j].append(inf)
    for j in range(len(x), 10):
        b[j].append(inf)
tree = [segment_tree(n + 3, b[i]) for i in range(10)]
ans = []
for _ in range(m):
    (t, i, x) = map(int, input().split())
    if t == 1:
        c = x * (n + 1) + i
        y = list(str(x))
        y.reverse()
        for j in range(len(y)):
            if int(y[j]):
                update(i, c, tree[j])
            else:
                update(i, inf, tree[j])
        for j in range(len(y), 10):
            update(i, inf, tree[j])
        a[i] = x
    else:
        (l, r) = (i, x)
        ans0 = inf
        p = 1
        for i in range(10):
            if 2 * p >= ans0:
                break
            p *= 10
            mi1 = get_min(l, r, tree[i])
            if not mi1 ^ inf:
                continue
            mi1 %= n + 1
            mi2 = min(get_min(l, mi1 - 1, tree[i]), get_min(mi1 + 1, r, tree[i]))
            if not mi2 ^ inf:
                continue
            mi2 %= n + 1
            ans0 = min(ans0, a[mi1] + a[mi2])
        ans0 = (ans0 + 1) % (inf + 1) - 1
        ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))