ここによくいるユーザーの誰かの投稿がXで伸びているのを発見(相互確証破壊)

1/2

:: Treap {
  @init() {
    return {len: 0, end: {v: null, id: 1, l: null, r: null, p: null}}
  }
  @empty(a) {return a.len == 0}
  @size(a) {return a.len}
  @begin(a) {
    var res = a.end
    loop {
      if res.l == null break
      res = res.l
    }
    return res
  }
  @end(a) {return a.end}
  @rotateLeft(n) {
    var par = n.p
    if par.p.r == par {par.p.r = n}
    else {par.p.l = n}
    n.p = par.p
    par.r = n.l
    if n.l != null n.l.p = par
    par.p = n
    n.l = par
    return null
  }
  @rotateRight(n) {
    var par = n.p
    if par.p.r == par {par.p.r = n}
    else {par.p.l = n}
    n.p = par.p
    par.l = n.r
    if n.r != null n.r.p = par
    par.p = n
    n.r = par
    return null
  }
  @insert(a,v) {
    if a.len == 0 {
      a.len += 1
      let val = {v: v, id: Math:rnd(), l: null, r: null, p: a.end}
      a.end.l = val
      return val
    }
    var tmp = a.end.l
    var insertRight = false
    loop {
      if tmp.v == v return tmp
      if v < tmp.v {
        if tmp.l == null {
          insertRight = false
          break
        }
        tmp = tmp.l
      }
      else {
        if tmp.r == null {
          insertRight = true
          break
        }
        tmp = tmp.r
      }
    }
    a.len += 1
    let id = Math:rnd()
    var val = {v: v, id: id, l: null, r: null, p: tmp}
    if insertRight {
      tmp.r = val
    }
    else {
      tmp.l = val
    }
    loop {
      if val.id < val.p.id break
      if val.p.r == val {rotateLeft(val)}
      else {rotateRight(val)}
    }
    return val
  }
  @erase(a,v) {
    if a.len == 0 return false
    var val = a.end.l
    loop {
      if v == val.v break
      if v < val.v {
        if val.l == null return false
        val = val.l
      }
      else {
        if val.r == null return false
        val = val.r
      }
    }
    a.len -= 1
    val.id = -1
    loop {
      if val.l == null {
        if val.r == null break
        else rotateLeft(val.r)
      }
      else {
        if val.r == null rotateRight(val.l)
        else {
          if val.l.id < val.r.id rotateLeft(val.r)
          else rotateRight(val.l)
        }
      }
    }
    if val.p.r == val val.p.r = null
    else val.p.l = null
    return true
  }
}

2/2

:: Treap {
  @find(a,v) {
    if a.len == 0 return a.end
    var val = a.end.l
    loop {
      if v == val.v break
      if v < val.v {
        if val.l == null return a.end
        val = val.l
      }
      else {
        if val.r == null return a.end
        val = val.r
      }
    }
    return val
  }
  @lowerBound(a,v) {
    var res = a.end
    if a.len == 0 return res
    var val = a.end.l
    loop {
      if val.v < v {
        if val.r == null break
        val = val.r
      }
      else {
        res = val
        if val.l == null break
        val = val.l
      }
    }
    return res
  }
  @upperBound(a,v) {
    var res = a.end
    if a.len == 0 return res
    var val = a.end.l
    loop {
      if v < val.v {
        res = val
        if val.l == null break
        val = val.l
      }
      else {
        if val.r == null break
        val = val.r
      }
    }
    return res
  }
  @next(n) {
    if n.r == null {
      var res = n
      loop {
        if res.p.l == res break
        res = res.p
      }
      return res.p
    }
    else {
      var res = n.r
      loop {
        if res.l == null break
        res = res.l
      }
      return res
    }
  }
  @prev(n) {
    if n.l == null {
      var res = n
      loop {
        if res.p.r == res break
        res = res.p
      }
      return res.p
    }
    else {
      var res = n.l
      loop {
        if res.r == null break
        res = res.r
      }
      return res
    }
  }
}

使用例

var a = Treap:init()
Treap:insert(a,3)
Treap:insert(a,1)
Treap:insert(a,4)
Treap:insert(a,1)
Treap:insert(a,5)
Treap:insert(a,9)
<:Treap:size(a)
<:"---"
var i = Treap:begin(a)
loop {
  <:i.v
  i = Treap:next(i)
  if i == Treap:end(a) break
}
<:"---"
Treap:erase(a,3)
Treap:erase(a,1)
Treap:erase(a,2)
Treap:erase(a,5)
<:Treap:size(a)
<:"---"
i = Treap:end(a)
loop {
  i = Treap:prev(i)
  <:i.v
  if i == Treap:begin(a) break
}
// 5
// 1 3 4 5 9
// 2
// 9 4