definitely_not_bu1th4nh's blog

By definitely_not_bu1th4nh, history, 6 years ago, In English

Hi there, I have this problem: Given an array A of integers. You need to operate three kinds of online query:

  • Insert an element X at position i in the array
  • Delete element at position i in the array
  • Answer the maximum element and the index of maximum element in range [l, r]

Constraints:

  • Q = number of queries — less than or equal 100000
  • N = number of elements — less than or equal 100000
  • X, A[i] is less than or equal 1000000000

I don't know which data structure is the most suitable for solving this problem. Can you help me with this and explain how to use that data structure?

Thank you.

UPD: This is online query problem.

UPD2: I've added tags for the blog entry.

| Write comment?
»
6 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

I think that you can use segment tree for solve this problem. You can store for each node in the segment tree a pair with the maximum element in the range and the index of the element in array. For delete the element in position x you can insert -(1LL<<60LL) in the position x.You can read about segment tree in https://www.google.com.br/amp/s/www.geeksforgeeks.org/segment-tree-set-2-range-maximum-query-node-update/amp/

»
6 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Treap, maybe...

»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Treaps with implicit keys.

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

if forced to query online:

use splay tree to maintain<location, value, max>, sort as first element(location)

max = this node's whole subtree's max value.

for query we splay (location)r to root and then splay (location)l to root.

and then answer = max{ root.value, root.right_son.value, root.right_son.left_son.max }

(last line is working by Balanced Binary Tree's properties)

if l or r not exist just find x>=l and y<=r to query them.

if not forced query online:

sort all locations which used by query, insert or delete.

replace locations as their rank after sort

and just solve it by segment tree

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by definitely_not_bu1th4nh (previous revision, new revision, compare).

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by definitely_not_bu1th4nh (previous revision, new revision, compare).

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

sqrt