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

Автор rotavirus, история, 5 лет назад, По-английски

Looking at the "Mo-based solution" of problem 1000F - One Occurrence in editorial, I noticed the author used some sqrt-decomposition to find any element in the set, but the author could do this in O(1) time using the data structure i'll describe right now.

The set which can contain integers from 1 to $$$n$$$ is stored as two arrays of length $$$O(n)$$$:

type set struct {
    index []int
    val []int
    size int
}

func newSet(n int) set {
    return set{make([]int,1+n),make([]int,1+n),0}
}

func (s *set) Size() int {
    return s.size
}

Inserting into the set:

func (s *set) Insert(x int) error {
    n := len(s.index)-1
    if x<1 || x>n {
        return errors.New("inappropriate value to insert")
    }
    if s.index[x] != 0 {
        return errors.New("value already exists in the set")
    }
    
    s.size++
    s.val[s.size] = x
    s.index[x] = s.size
    
    return nil
}

Erasing from the set:

func (s *set) Erase(x int) error {
    n := len(s.index)-1
    if x<1 || x>n {
        return errors.New("inappropriate value to erase")
    }
    if s.index[x] == 0 {
        return errors.New("value already doesn't exist in the set")
    }
    
    i := s.index[x]
    if i == s.size {
        s.val[s.size] = 0
        s.index[x] = 0
        s.size--
    } else {
        y := s.val[s.size]
        s.val[s.size] = 0
        s.index[y] = i
        s.val[i] = y
        s.index[x] = 0
        s.size--
    }
    return nil
}

Finding an element in the set:

func (s *set) Find (x int) bool {
    n := len(s.index)-1
    if x<1 || x>n {
        return false
    }
    return s.index[x]>0
}

Iterating over the set:

func (s *set) ToArray() []int {
    return s.val[1:1+s.size]
}

func (s *set) ValueAt(i int) int {
    return s.val[i-1]
}

However this set doesn't store values in the ascending order like the standard RB-tree set does.

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

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

Wow, this guy just invented an array and a linked list! Such an advanced data structure! Congratulations!