Olek's blog

Help on segment tree problem
By Olek, history, 9 years ago, In English

Hello guys,
I have been looking for problems related to segment tree and found this: https://www.urionlinejudge.com.br/judge/en/problems/view/1511

I worry in just into code the segment tree and not I heed me by the fact that the query is not a rectangular range(manhattan distance from point).

Does anyone have any tips related to queries like this?

With changes in the query logic in tree work or need something more?

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

Comments Comments (6)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't think 2D BIT would work here.The form of wanted area is a diamond(but it can be solved by rotating somehow the matrix to make a square).Also BIT has another problem(also for minimum,maximum).You can't erase what you've put in it already.If I change and element from 2 to 5,in update function it wouldn't erase 2,but make gcd(2,5).

I would recommend keeping 1000 seq trees for lines and 1000 for columns(since coordinates are small),answering in O(2000*log(1000)) for a query. This solution doesn't seems to pass all testcases but with some tricks and optimizations,you may get AC.Also take cares of 0's, because 0 isn't netrual element for gcd (like 1 for multiplication).

→ Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

You can use the 2D segment tree for the answer this querys! In this case, you have two solutions:

  1. Rotate the points 45º and answer the querys normaly with a 2d segtree.

  2. Modify the query to answer the querys to manhattan distance from point.

My code with a second option: http://ideone.com/WTxRZ8

In any cases, the complexity per query is O(log²n). :)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Simply magnificent. The two ideas are cool
    Thank you

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I'm in the beginning of the segment tree study, i found very difficult is the idea, but pretty cool. :D If you can help me, just to get this better... You make a segment tree 2d in a single array instead of an matrix that many do, right?

    The update function apparently does not change anything, right?

    The key test is performed on the "valido" function. Can you explain a bit?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      Yes, exactly! I store my segment tree in a single array...

      "no" = position in array tr[] that represents the interval [lx,rx][ly,ry] of my matrix.

      From [lx,rx][ly,ry] we can split this interval in 4 others intervals that i store in (no*4)-2, (no*4)-1, (no*4), (no*4)+1

      You're right, the update function doesn't change.

      The "valido" function checks if the range [li,ri][lj,rj] entirely outside the Hamiltonian distance of point [i,j]. If returns false, the range is outside.

      Is a bit hard explain this function in words, try sketch this part and check every case.

      In query function, the second "if" checks if the range [li,ri][lj,rj] entirely inside the Hamiltonian distance of point [i,j]. In positive case, just return actualy node of tree.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Cool, now it became clear :D
        Thanks you again!!

        → Reply