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

Unique Range Query
Автор mr_warlock, история, 5 часов назад, По-английски

I am stuck on this following problem:

Statement:

Given an array of size n and have to do q queries.

Query are---

Type-1) Update index k with value v.

Type-2) Print the unique count in range [L..R] which are less than v;

Constraints:

1<=n,q<=100000
1<=v<=1000000000
1<=k<=n
1<=L<=R<=n

Thanks for reading the problem. It will be really helpful if you can give me a solution.

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

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

I'm also struggling with questions that has to do with subsequence/segment L..R. Any solution will really be appreciated. Thanks!

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

O(n^2logn) idea: store at each block a set of what's the values in [iBS, (i+1)BS] and for each previous blocks the set difference, at each query you add the result of the block and for the next you add the result of it minus of previous and other previous etc, ig this can be optimized to nsqrtlogn and we only store power of two sizes somehow? but i don't really see it, we can do update and query in O(sqrtn) but we're forced to build the structure in O(n^2).

edit 2: even without updates i realized this is stupid, you can just O(nlogn) query by making a set each time and updating in O(1), works in O(nqlogn), sorry for the stupidity

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

    Thanks for your time.

    I think the solution is related to combination of merge sort tree and order set. But I couldn't come with a optimized solution.

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

Build a segment tree over the array, and in every node of that tree hold a splay tree of elements belonging to that segment. The updates as well as the queries are now trivial and will work in O(n*logn*logn). The memory usage of this solution will be O(n*logn). With clever implementation it should AC.

→ Ответить