Блог пользователя cylo

What can be the most efficient solution for this?

Автор cylo, история, 5 лет назад, По-английски

Given n integer coordinates of the form (x, y) and Q queries in which a pair (a, b) is given. For each query output the number of coordinates whose x<=a AND y<=b.

Q<100000 N<1000 1<= x, y, a, b <= 1000

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

2D partial sum DP will do the job. DP[i][j] - the number of points with x <= i and y <= j. The recurrence is easy. DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1].

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks :)

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      How to solve if there is query is of OR form i.e. (x<=a || y<=b)?

      → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        Using 2D prefix sum you could actually answer any query of type — "How many points exists in range xi <= x <= xf && yi <= y <= yf." After building your 2D Prefix Table you would need to get the sum in a given rectangle. That can be done using the following formula: dp[xf][yf] — dp[xf][yi — 1] — dp[xi — 1][yf] + dp[xi — 1] + dp[yi — 1].

        → Ответить
»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

sort by X, fenwick tree by Y, NlogN

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    $$$Q \log N$$$ or how do you answer queries?

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Of course, N in my message is (N+Q)

      → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I am stuck in a similiar problem actually. And 2D Prefix Sum can't be done due to Memory restrictions. Could you explain a little further how Sorting + Fenwick would work ? If I sorted by X and the Fenwick by Y, how would I be sure that the corresponding Y in the Fenwick belong to the points in the range [0 — X] ? Thanks !

        → Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You can strengthen the problem into an online version: dynamically insert and query. For that, use 2D BIT.

→ Ответить