besher's blog

How to solve this problem?
By besher, 9 years ago, In English

Given n numbers and m queries

each number a[i] satisfy this condition: 1<=a[i]<=N

there are two types of queries:

1 idx val : set the value of a[idx] to val : 1<=val<=N

2 l r : the answer is "yes" if there is a repeated value in the interval from l to r otherwise : the answer is "no".

n,m<=10^5

thanks in advance.

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

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

I think you can solve it using segment tree; On every node calculate maximum repeating value on segment; If there is repeating value print "yes" otherwise "no"

UPD: Also wrong as this idea.)

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

The idea here is to maintain an array b, where b[i] equals the maximal j such that j < i and a[j] == a[i] (if there's no such j then b[i] = -1).
If max(b[l], b[l + 1], ..., b[r]) >= l then there's a repeated value.
You can easily update b when a is updated.
Thus a segment tree (or something else) can be used to solve this problem.

→ Reply