Official

G - Balance Update Query Editorial by en_translator


Prefetch the queries to enumerate the possible value of card scores in ascending order: \(d_1,d_2,\ldots,d_k\) (coordinate compression), and use a Fenwick tree (or a segment tree) whose \(i\)-th element corresponds to \(d_i\) to process the queries.
Specifically, use the following two Fenwick trees: one to manage the number of cards of each score, and the other to manage the product of the number and score of cards of each score. The query of the \(1\)-st and \(2\)-nd kinds are easy to handle with. As for the \(3\)-rd, first find the minimum \(l\) such that the sum of \([l, k)\) in \(X\) does not exceed \(x\), then add the sum of \([l, k)\) in \(Y\) to the answer. Finally choose the others from \(d_{l-1}\) to find the desired value.
We now analyze the complexity. In the worst case, each query requires a binary search, which in turn calls retrieve queries of the Fenwick tree, so it costs \(\mathrm{O}(N (\log N)^2)\) time. With a binary search trick on a segment tree (which is available as \(\mathrm{min\_left}\) in AtCoder Library), it drops to \(\mathrm{O}(N \log N)\).

posted:
last update: