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

Strange segfault on SPOJ KQUERY
Автор brdy, история, 7 лет назад, По-английски

Here is my AC code: https://hastebin.com/ewobuzater.cpp

It uses offline BIT + sorting.

Here is the strange thing: que[200001] works perfectly fine, but if you change it to que[200000] it will segfault. However, it is zero based indexing and q is at max 200000.

Can anyone think of a case where que[200000] faces out of bound access?

Теги bug
  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

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

Since I am new to this programming will you please explain your solution?

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

    que[] stores the queries

    The idea behind my solution is that instead of solving for each query individually, we sort them in decreasing order of k.

    Now we can change this problem into:

    Which values are greater than k?

    Think about a binary array:

    1 means that the number in the i'th position is greater than k, and 0 means it is not.

    How to find how many is greater from position [i,j]?

    We use some data structures such as segment tree/BIT which gives us range sum in O(logn) and allows us to set a position to 1 in O(logn).

    We can make the observation that if a > b and the value v > a, then v > b.

    Thus, once we go from a higher k to a lower k, the values greater than the higher k will also be greater than the lower k. This is why we sort it in decreasing order.

    We query [l,r] like prefix sums in the bit to count which ones are greater.

    Since queries are not in the order they came in we need another array to store answers.

    Complexity is O(q + nlogn)

    Solution is very similar to classical problem of counting inversions with BIT + sorting.

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

Your operator< returns true for equal elements. sort assumes this is not the case to save some out-of-bounds checks; the extra que element is probably acting as a sentinel. You shouldn't need the extra position if you replace the implementation by return one.k > two.k.

→ Ответить