Блог пользователя dario-dsa

SPOJ Kquery
Автор dario-dsa, 11 лет назад, По-английски

KQUERY
Can anyone help me to solve this problem? I have trouble to put it in BIT way on thinking.
Thanks

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

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

it can be solved by sorting the query list by k in descending order (same go for array A)

then with each query we add those element from A which is greater than k to it original position in the BIT (you need to keep track of those element which is already added so the total number of update is n (the reason we sort A))

then it retrun to a basic problem of adding element and counting the number of element in range :p

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

    Can you give me a little bit more information?

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

    well, let sort A in descending order and B[i] be the position of A[i] in the original array , we will solve from the query with greatest k to the query with smallest k

    now we have query (i, j, k), let x be the number such as all element 1..x from A is added to the tree (BIT), set by 0 at first

    then we add all the element A[j] such as j > x and A[j] > k to the tree (at B[i]) element j <= x is already added so ignore them

    assign x as the greatest j we found above

    all the element added into the tree so far is greater than k so the only thing left is to count the number of element added in range (i, j)

    is this enough for an explaination I wonder ? :p

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

    First I have created a segment tree and each query I assigned ascending order sorted array in a range, then applying the binary search for counting greater than K values but I am getting TLE.
    Note. I have ascending order sorted array so I tried to mid of the right side first, but I am getting TLE.
    Bellow, I have attached my code.
    Do you have any suggestions, please? Tanks
    https://ideone.com/HOs945

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

      You answer each query in $$$O(\log^2 n)$$$ which is too high for this problem. You can improve it to $$$O(\log n)$$$ by storing all queries, answering them in a nicer order and then printing all answers.

      Try to understand this or this.

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

        But it should not show TLE.Total complexity will be 4*n + q*ln^2(n) which woudl be 2.1*1e7 steps

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

Actually, we can solve this problem with a more "classic" way : let's build a segment tree, with a sorted subarray in every vertex. Then we can divide [l, r] into subsegments, and do a Binary Search on subsegments. O(logN ^ 2) for the query.

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

Check this code http://mohamedmosamin.wordpress.com/2013/09/03/spoj-3266-k-query-kquery/. Use it the same idea that shows lazycode97

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

Create a large area in which you are going to store both the queries (represented by their k values) and the numbers of the original array. Now sort this array in non-increasing order (remember to store the original positions in a separate array).

Suppose that you have a segment tree (initially all zeros).

Now scan the array from left to right. If the current number was a number in the original array, update it's value to 1 (in the segment tree). If the current number (call it x) is a query then we know that all numbers greater than x have been inserted in the segment tree because we sorted the array (so all intervals that contain it have been updated); execute a range sum query to get the answer.

Queries were scrambled when we sorted the array, so you need to print them in the order they were given.

The time limit for this problem is tight (1500 ms). Use a Fenwick tree and use static arrays instead of vectors.

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

I get WA on this problem, but i don't know why.. Can someone please help me ?

here is my implementation

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

    You can solve this problem using segment tree with vectors. At every node, you store a sorted vector in segment tree.

    Here is my implementation using segment tree with vectors

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

      Bro i think your code is for a similarly named problem KQUERYO. that code will probably not work here due to stricter time limits.

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

Before going into the solution, consider this: For every query, count the number of element which are less than or equal to k,let us call it X. our answer for every query will be j-i+1-X

Now, to calculate the value of X:- - Declare an array A of size n. Initially all values zero. - Store the indexes of all the integers in a 2-D vector V. There can be at most n distinct integers. - Store all the queries in a vector and sort it according to k(ascending order). - Now iterate over query vector and for every number less than or equal to k, update the array for all the indexes stored in V for corresponding number. - Count the sum of elements in array A from i to j. X=sum(l,r) by Range sum query using segment tree or BIT. - Answer to each query=**j-i+1-X**

My code

→ Ответить