Difficult query problem

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

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.

Comments (2)

Write comment?

Kaban-5

9 years ago, # |

← Rev. 5 →

+34

Key observation in this problem is that

Unable to parse markup [type=CF_TEX]

. It is quite easy to understand : if all x_i are divisible by d, then all

are divisible by d, if

are divisible by d, then their prefix sum

is divisible by d.

First, you can keep a_i in segment tree with operations "add arithmetic progression on segment" and "request i-th element". For simplicity, I'll assume

later, other cases are solved easily when we have such segment tree.

Second,

Let's say

. 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

to some other position of b. So we can use segment tree on b_i in similar fashion to find

. But

. So if

, then we need to calculate

. 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

, which can be calculated using described segment trees easily.

→ Reply

Enchom

9 years ago, # ^ |

I got it, thanks a lot!

During the competition I thought about differences but found that

is not always the gcd of differences, so I dropped the idea. Didn't realise you have to add a_l to the differences to get the correct gcd.

Enchom's blog