DreamingBoy's blog

By DreamingBoy, history, 8 years ago, In English

Ladies and Gentlemen, please help me -> problem.

  • Vote: I like it
  • +4
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thank you too =) I heard, that this problem can be solved in O(q * log(N)). If you know, can you share solution idea?

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I'll give it a bit more time but I can't think of a solution that fast :(

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it
  • Let Ai be the initial value of element i.
  • With a sieve-like loop, make a list of all divisors for numbers  ≤ 300000. Let Dx be the list of divisors for number x.
  • Let Ui be the total updates performed to element i. Notice that adding d to all Ui in a range [l, r] is the same as adding d to Ul and subtracting d from Ur + 1, and then working with prefix sums. This can be done efficiently in O(logN) with a BIT.
  • Now, the answer to queries of the second type for a certain element i is , which works in .
C++ Code