Omega1's blog

Distinct numbers on an interval
By Omega1, history, 9 years ago, In English

I have a question , need fast to do to two types of operations:

update: 1 x y element on position x become y;

query : 2 x y number of distinct numbers from the interval [ x , y ];

How to solve this problem,can someone help me??

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

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

Where is this problem from?

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

    It's a subproblem that I have to solve in problem that was given at regional olympiad.

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

      Can you give the link to the problem?

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

You can solve this problem with segment trees where each node of your segment tree is a set.

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

    Won't be fast enough. it will be O(N*logN) for merging nodes (the sets).

    So then range query will be answered in O(logN*logN*N). Also the building of the tree will be O(N*N*log(N)).

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

take new array.for each element of first array find next index where same element stand,if it is,else use value INF. for query l,r you should answer question: how many elements is greater than r in range (l,r) in new array? it is standart segment tree or other data structure problem,and can be solved in O(n * logn) .for update operation you should change next and previus values of modified element.

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

    What u mean by next index? Can you plz elaborate.

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

      for array: 4,1,4,6,1,6,6

      second array: 3,5,INF,6,INF,7,INF

      for query (4,7) only 2 elements is greater than 7 so answer is 7(as 6,1)

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

    "how many elements is greater than r in range (l,r) in new array? it is standart segment tree or other data structure problem,and can be solved in O(n * logn)"

    How can we do that? Online and O(n * log(n))?

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

      sorry I was wrong,I asked here same question,it can be solved in O(n * log(n)2) .I missed one log(n) :)

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

        Online?

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

          yes

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

            There's a solution which is , and O(n * log(n)2) with treap + segment tree. What is the solution for online and just segment tree? Are you sure about it?

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

              I mean: " it is standart segment tree or other data structure problem" only segment tree can't solve this,but as you say(with your complexity and with this data structures) you can update,and it will be online

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

              Can you describe the way using segment tree + bst?

              I can't figure it.

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

                Without update, solution is segment tree + vector. You need to delete and add to vector, and it have to be sorted. You can use treap for it.

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

MO's algorithm. Since you're not updating the array, offline solution is possible. However, this has n*(sqrt(n)) complexity.

→ Reply