Hello everybody,
Today was the second day of RMI(Romanian master of informatics) and I participated onsite. It took me a couple of hours to solve two of the problems and then I had whole three to tackle the last one. Alas, it turned out to be too difficult for me to get more than 10-20 points.
The short statement of the problem is simply :
Support 2 types of queries on an array of size N:
1) Given "L R" find greatest common divisor of all numbers from index L to R, that is gcd(a[L], a[L+1],..., a[R])
2) Given "L R k" update the array in the following way:
a[L]+=k
a[L+1]+=2*k
...
a[R]+=(R-L+1)*k
There are up to 100,000 numbers and queries with time limit of 1s and memory limit of 128MB. The initial numbers are up to 200,000,000 and in each query of type 2 we can have k up to 200,000,000 (resulting in numbers becoming as big as 10^18).
Query problems are usually my favourite but I couldn't come up with anything here. The queries just seem very different. If someone has some solution, please share.
Key observation in this problem is that gcd(x1, ..., xn) = gcd(x1, x2 - x1, x3 - x2, ..., xn - xn - 1). It is quite easy to understand : if all xi are divisible by d, then all xi + 1 - xi are divisible by d, if xi + 1 - xi are divisible by d, then their prefix sum x1 + (x2 - x1) + ... + (xi + 1 - xi) = xi + 1 is divisible by d.
First, you can keep ai in segment tree with operations "add arithmetic progression on segment" and "request i-th element". For simplicity, I'll assume r > l + 3 later, other cases are solved easily when we have such segment tree.
Second, gcd(al, ..., ar) = gcd(al, al + 1 - al, al + 2 - al + 1, ..., ar - ar - 1) = gcd(al, gcd(al + 1 - al, al + 2 - al + 1, ..., ar - ar - 1)).
Let's say bi + 1 = ai + 1 - ai. Let's forget about existence of a for a moment and reformulate statement in new variables: in first operation we need to calculate gcd on segment, thanks to above equality, in second operation we need to add k to some segment of b, and add - (r - l + 1)k to some other position of b. So we can use segment tree on bi in similar fashion to find bl + 1 = al + 1 - al. But gcd(bl + 1, ..., br) = gcd(bl + 1, gcd(bl + 2 - bl + 1, ..., br - br - 1). So if ci + 1 = bi + 1 - bi, then we need to calculate gcd(cl + 2, ..., cr). But when we add some value to segment of b not more than two values of c change, so we can use usual segment tree for "change single value" and "calculate gcd on segment" for c.
The answer is gcd(gcd(al, bl + 1), gcd(cl + 2, ..., cr)), which can be calculated using described segment trees easily.
I got it, thanks a lot!
During the competition I thought about differences but found that gcd(al, al + 1...ar) is not always the gcd of differences, so I dropped the idea. Didn't realise you have to add al to the differences to get the correct gcd.