ATofighi's blog

find how many numbers in subsequence a[l]...a[r] equal to K
By ATofighi, history, 9 years ago, In English

Hi,

Can anyone help me with this problem?

You are given an array with n integers a1, a2, ..., an , a integer K and m queries.

There are two types of query:

  1. give you two integers l and r and ask you to print how many number of integers al, al + 1, ..., ar which equal to K.

  2. give you three integers l, r and v and ask you to add the value of al, al + 1, ..., ar by v.

You should print the answer of the first queries.

Thanks, Sorry for my bad English!

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

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

Do you know how to solve the second type of queries ?

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

    It can be done with segment trees (Lazy propagation). but I don't have a good idea to solve both types of queries.

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

I've proposed such a problem for a contest several years ago. After a long discussing with IGMs I strongly believe (but still have no proof) that this problem can be solved only be SQRT-decomposition in .

Basic idea: split an array into several chunks of size , for each chunk store a multiset of numbers in it and a (lazy-propagated) value which should be added to each of them.

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

    Why no proof? What's wrong with this solution?

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

      still have no proof) that this problem can be solved only be SQRT-decomposition

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

I think we can do it using segment tree. Store at each Node Merge Sorted array of its children with two extra variables one for lazy and let the other be named to_subtract.

Use Lazy propagation!

At each query instead of finding K you have to find the frequency of number = K-to_subtract . This can be done in O(LOG N ) using upper bound and lower bound on the saved array as it was sorted once!

Note : during the process we never change the array! So the complexity will be O(Log N ^ 2)

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

    Your code fails on this case: N = 4, and array is {1, 1, 1, 1}.
    First query is +1 in [1, 2].
    Second is number of 1s in [1, 4].
    Your idea will print 4 instead of 2.

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

      Yeah you are right! I was thinking of same query as the update operation!

      We will have to update the array ! So the approach is totally useless !

      → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it -7 Vote: I do not like it

As far as I know it is impossible to solve general problem in O(n * log(n)).(I remember that Haghani said that is impossible, but not I'm not sure).

But it can solved in O(n * sqrt(n)) easily.also if you have an array of K's you can done it in O(n * sqrt(n) * k).

But there is one case of problem that can be solved in O(n * log(n)) if we know that K is always smaller(or greater) than all of ai s. keep in segment node a pair: {frequency_of_minimum,minimum}.

→ Reply