Here's the problem (IMO 2013 Problem 1): Assume that k and n are two positive integers. Prove that there exist positive integers m1, ... , mk such that
Think:
Spoiler 0How is this related to segtrees?
Spoiler 1Could you reformulate the "fraction multiplication" into something that is more similar to something related to segtrees?
Spoiler 2Treat the fractions as ranges of denominator to numerator — of course, you may multiply a common number. Does it already look closer to something done with segtrees?
Spoiler 3Yes, each thing on the RHS may be taken as ranges. But you need the range length (including start, but not end) to be a divisor of the numerator. Hmmm now how could we do this?
Spoiler 4Let's try to make all range lengths powers of two (note: for example, the range length of [4,8] is 8-4=4).
Mega SpoilerWhat happens when you do a range sum query?
Here's a generalization, which is much easier once you've found the segtree solution to the above problem. Assume that k and n are two positive integers. Prove that there exist positive integers m1, ... , mk such that
Unable to parse markup [type=CF_TEX]
is an integer and
l < = log2(k) + 1.