kingofnumbers's blog

need hint to solve a problem
By kingofnumbers, 12 years ago, In English

Hi,

Given an Array with N elements each element have 3 integers Say Ai,Bi,Ci.

you have to answer Q querys given in each query 3 integers X,Y,Z you have to say how many elements in the array satisfy Ai>=X , Bi>=Y Ci<=Z

N,Q<=10^5

I hope you help me or give me a hint, thanks.

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

»
12 years ago, # |
← Rev. 8   Vote: I like it -15 Vote: I do not like it

You have to use segment tree and BS Tree their subtrees' roots being hashed (using perfect hashing !) and finally BS on answers while also balancing the red-black tree, and maintaining the fact that the sum is even if the number of subtrees' nodes are 2^p-1, where p is any prime number.

Also take into account that 64MB stack is not enough to recursively solve the problem. You gotta use an iterative method.

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

Can we use 3-D Binary Indexed Tree? We need to find number of points in the box {x, y, z | 0 <= x <= X, 0 <= y <= Y, 0 <= z <= Z}. To fill the tree we will to update N*log(N)*log(N)*log(N) points in 3-D which can be hashed.

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

You can just sort array (using your own compare function) and use binary search.

To better understanding imagine, that each element has only one integer.

Here is my solution.

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

    I'm afraid your solution is incorrect.

    It gives wrong answer for the test like this:

    1

    2 2 2

    1

    1 1 1

    It should be 0, but your solution outputs 1.

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

      But is it possible algorithm: sort + binary search for the first is greater than or equal? If not, tell why, please.

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

        I'm pretty sure it's impossible. Let's assume that all elements of the array have different a[i]. In this case, binary search will find the first element comparing a[i] only. But it doesn't use any information about b[i] and c[i](I mean that for some elements, a[i] might fit the constrains but b[i] or c[i] might not).

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

          Yes, of course. I understand my mistake. Thank you!

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

    Life of programmers is not that easy :) ,your code gives Wrong Answers

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

There's an offline solution which uses O((N + Q) * log(N + Q) + Q * (log N)^2) time and O(Q + N * log N) space.

Let's assume that each element of the array is a point in 3-D space.

1)At first, shrink all the Y-coordinates.

2)Then build a segment tree for Y-coordinate and store vector with all Z-coordinates of points which are covered by the segment represented by the tree's node. Moreover, keep a Fenwick tree in each node. Initially, all points should be in the tree and each Fenwick tree should contain 1 at all the positions.

3)After that, you may use sweep algorithm line to answer the queries. There should be two types of event: a point disappearing and a query. Events have to be sorted in non-descending order of X-coordinate.

To process the point(X, Y, Z) disappearing event, just modify one element in respective Fenwick tree which represents (Y, Z) point(adding -1 there) in the segment tree.

To process a query event, simply calculate the sum in (Y, 0, MAX_Y, Z) rectangle using the segment tree.

→ Reply