If we keep the dials in a data structure, then to make the solution efficient enough, each update and query operation will have to run in sub-linear time.

One way to achieve this is to group adjacent dials into buckets containing about ~\sqrt N~ dials each. For each bucket, we keep track of how many times each digit appears in the bucket. The asymptotic running time is ~\mathcal O(M \sqrt N)~ and the algorithm can pass in time if carefully implemented.

By using a different data structure, we can reduce the time to ~\mathcal O(\log N)~ per query.

Imagine a binary tree in which every leaf represents one dial. Every node in the tree contains ~10~ numbers – how many times each digit appears in dials contained in the subtree rooted at that node. The root node of this tree contains information about all the dials. There are about ~2N~ nodes total.

Consider first how to perform a query in this tree. Given an interval ~[A, B]~ we want to count how many dials in the interval are displaying each digit. We start from the root node and use the following recursive algorithm:

• If all dials in the subtree of the current node are contained in ~[A, B]~, return the ~10~ numbers contained in this node.
• If the dials ~[A, B]~ are entirely contained in the left or right child of the current node, then move to that node (the other node is of no interest).
• Otherwise (some of the dials ~[A, B]~ are in the left subtree, and some in the right subtree), recursively query both subtrees and add the results together.

This procedure really splits the query interval into subintervals whose lengths decrease exponentially, using as large subintervals as possible. The time complexity is ~\mathcal O(\log N)~.

To keep the entire tree updated, the update operation would need to be linear, because for example, when Luka clicks all the dials, the entire tree would need to be updated.

To remedy this, we can use lazy propagation – when an update operation would update the entire subtree rooted at some node, don't actually do this, but instead increase a "laziness" counter in that node. When another update or query operation would visit one of the node's children, only then propagate the counter to the children.