Sum Queries?
Contest: Educational Codeforces Round 72 (Rated for Div. 2)
Difficulty rating: 2300
Tags: data structures, greedy, implementation, math

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 format:
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 format:
For each query of the second type print the lowest sum of the unbalanced subset. Print -1 if no unbalanced subset exists.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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.

Example input:
4 5
300 10001 20 20
2 1 3
1 1 310
2 1 3
2 3 3
2 3 4

Example output:
-1
330
-1
40

Editorial:
We are given the definition of the balanced multiset but let's instead fix the criteria to determine if the multiset is unbalanced.
Take an empty multiset and start adding numbers to it until it becomes unbalanced. Empty set to the set of one number is trivial. Now for the second number. If there is some position such that both numbers have non-zero digits in it, then the multiset becomes unbalanced (let these be non-zero digits $$$d_1$$$ and $$$d_2$$$, then $$$d_1 + d_2$$$ can be neither $$$d_1$$$, nor $$$d_2$$$).
After that let's prove that you can never make an unbalanced multiset balanced again by adding numbers to it. Let there be such multisets $$$a$$$ and $$$b$$$ such $$$a$$$ is unbalanced, $$$b$$$ is balanced and $$$a \subset b$$$. Take a look at the lowest position which has non-zero digits in several numbers from $$$b$$$. The sum of these digits should be equal to at least one of them modulo $$$10$$$ (to satisfy the condition of balance). That can only mean their sum is greater or equal to $$$10$$$, thus is make a carry to the next position. The sum of digits on the next position plus carry should also be equal to some digit of them, thus pushing some other carry value to the next one. And so on until the carry makes it to the position greater than any position in any of the numbers. But the carry is non-zero and there is no number with any non-zero digit in this position. That makes our assumption incorrect.
After all, it implies that any unbalanced multiset of size greater than two has an unbalanced multiset of size two.
The problem now got reduced to: find a pair of numbers $$$a_i$$$ and $$$a_j$$$ such that $$$l \le i < j \le r$$$, there is at least one position such that both $$$a_i$$$ and $$$a_j$$$ have non-zero digits on it and $$$a_i + a_j$$$ is minimal possible.
That can be easily maintained in a segment tree. Let a node corresponding to the interval $$$[l; r)$$$ keep the best answer on an interval (the sum of such a pair) and an array $$$min\_by\_digit[i]$$$ — the smallest number on an interval $$$[l; r)$$$ which has a non-zero digit at position $$$i$$$ or $$$\infty$$$ if none exists.
The update is easy. Iterate over the digits of a new number and update the values in the array $$$min\_by\_digit$$$ in the corresponding nodes.
The merge is done the following way: push the best answers from children to the parent and then iterate over the positions and try to combine the smallest numbers at each one from the left child and the right child.
Idea-wise this is the same as storing a segtree and calculating the answer by each position separately.
However, these approaches differ by a huge constant factor performance-wise. The former one accesses the memory in a much more cache-friendly way. You might want to take that as a general advice on implementing multiple segtrees.
Overall complexity: $$$O((n + m) \cdot \log n \cdot \log_{10} MAXN)$$$.