Ladies and Gentlemen, please help me -> problem.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
4 | adamant | 160 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
8 | Dominater069 | 154 |
8 | nor | 154 |
Ladies and Gentlemen, please help me -> problem.
Name |
---|
Let's first forget about given array, imagine it's filled with zeroes. Now, you only need to find out how much was added to i-th position.
Let's do a following trick: store not how much was added to the i-th position, but how much was added to all positions, divisable by i. Let's store it in some array called add[i]. Now notice that add[l..r] += x is exactly the second type of queries we need to process.
The only thing we have to figure out is how to answer the first type of queries. It's quite simple. Let vector divisors[i] be all divisors of number i. Now, to find answer, you just have to do answer += add[x], for all x in divisors[i], and then asnwer += a[i], where a[i] is value of i-th position in initial array. You can estimate amount of divisors of i like i^(1/3) * 2 (it's a well known fact).
Complexity of this solution will be O(n^(1/3)) for first query and O(sqrt(n)) for second if you use sqrt-decomposition, and O(n^(1/3) * log n) for first query and O(log n) for second if you use segment tree/fenwick tree.
Here's my solution: http://pastebin.com/MNfqHFD0
You can actually get to sqrt(N) for update and cuberoot(N) for query if you use sqrt decomposition for processing range updates. http://ideone.com/W3LNJJ
Thank you too =) I heard, that this problem can be solved in O(q * log(N)). If you know, can you share solution idea?
I'll give it a bit more time but I can't think of a solution that fast :(
Good job)
Thank you.