orlon.'s blog

Problem involving segment tree with offline queries
By orlon., history, 7 years ago, In English

I was trying out segment tree problems and had some confusions in understanding the solutions for problems involving segment tree with offline queries.

Here are two problems GQR and 301D - Yaroslav and Divisors, for which I was referring to solutions GQR_AC and 36281412 respectively.

If anyone could help me understand these solutions in detail, it would be a great help.

Thanks!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help me?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

From what I understand on the question from codeforces, the solution goes something like this: Considering the numbers are different and they are <=2*10^5, he keeps an array in which he keeps the pos[i]= the position of number i in the array. Then, he takes an X from 1 to N and updates positions pos[X], pos[2*X], pos[3*X]... After these updates he then finds the answers for his queries.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "After these updates he then finds the answers for his queries." Can you please elaborate how he found the answer to the queries? This is the part I specifically didn't understand.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Using an Erathosthene's sieve-like technique, he will find all pairs (x,y) so that a[x]%a[y]=0 or a[y]%a[x]=0. Now for each query he has to find the number of pairs fully contained within the interval. This is done with a segment tree as such: go from i=1->n. If a pair is of the form (x,i) with x<=i, then update on position x in the segment tree. If there is a query of the form (x,i) then solve the query. If you need proof that this works, send a message.

      → Reply