### starkkk's blog

By starkkk, history, 7 years ago,

101466K - Random Numbers Can any one give me a hint? Thank you!

• -6

 » 7 years ago, # |   0 It can be solved using a segment tree :)
 » 7 years ago, # |   0 SpoilerLet’s solve another problem. You are given an array v of length N, where each element is a vector of length k.Answer two types of queries:S(i, j): Output vi + vi + 1 + vi + 2 + ... + vj.M(i, a1, a2, ..., ak): Set vi to (vi1 + a1, vi2 + a2, ..., vik + ak).This problem can be solved using a binary indexed tree.Let's reduce the original problem to this using these two observations:1. Every number Ti in the tree can always be represented as 2a1 × 3a2 × 5a3 × 7a4 × 11a5 × 13a6. Therefore we could store a vector Hi = {a1, a2, a3, a4, a5, a6} in the tree instead of the number itself (Calculating the original number, counting its divisors, and multiplying it with another number using this representation is left as an exercise to the reader).2. We can reduce subtree queries to range queries on an array using the Euler tour technique.