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

How to solve this problem?
Автор besher, 10 лет назад, По-английски

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.

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

»
10 лет назад, # |
← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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.)

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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.

→ Ответить