2213-由单个字符重复的最长子字符串

给你一个下标从 0 开始的字符串 s 。另给你一个下标从 0 开始、长度为 k 的字符串 queryCharacters
，一个下标从 0 开始、长度也是 k 的整数 下标 数组 queryIndices ，这两个都用来描述 k 个查询。

第 i 个查询会将 s 中位于下标 queryIndices[i] 的字符更新为 queryCharacters[i] 。

返回一个长度为 k 的数组 lengths ，其中 lengths[i] 是在执行第 i 个查询 之后 s 中仅由
单个字符重复 组成的 最长子字符串 的 长度 。

示例 1：

**输入：** s = "babacc", queryCharacters = "bcb", queryIndices = [1,3,3]
**输出：** [3,3,4]
**解释：**
- 第 1 次查询更新后 s = " _b **b** b_acc" 。由单个字符重复组成的最长子字符串是 "bbb" ，长度为 3 。
- 第 2 次查询更新后 s = "bbb _ **c** cc_" 。由单个字符重复组成的最长子字符串是 "bbb" 或 "ccc"，长度为 3 。
- 第 3 次查询更新后 s = " _bbb **b**_ cc" 。由单个字符重复组成的最长子字符串是 "bbbb" ，长度为 4 。
因此，返回 [3,3,4] 。

示例 2：

**输入：** s = "abyzz", queryCharacters = "aa", queryIndices = [2,1]
**输出：** [2,3]
**解释：**
- 第 1 次查询更新后 s = "ab **a** _zz_ " 。由单个字符重复组成的最长子字符串是 "zz" ，长度为 2 。
- 第 2 次查询更新后 s = " _a **a** a_zz" 。由单个字符重复组成的最长子字符串是 "aaa" ，长度为 3 。
因此，返回 [2,3] 。

提示：

• 1 <= s.length <= 105
• s 由小写英文字母组成
• k == queryCharacters.length == queryIndices.length
• 1 <= k <= 105
• queryCharacters 由小写英文字母组成
• 0 <= queryIndices[i] < s.length

解题思路

珂朵莉树，又叫基于数据随机的颜色段均摊，用于管理区间。它可以高效地进行区间的赋值、查询、遍历和删除操作。珂朵莉树的特点是，维护的每段区间的值是相等的，值相等的区间可以自动合并。

1. 这里用到的珂朵莉树是具有以下三个接口的数据结构。

• set: set(start: number, end: number, value: S): void，用于设置指定范围内的值。它接受起始位置 start、结束位置 end 和值 value 作为参数，并将该范围内的值设置为指定的值。

• get: get(x: number, erase = false): [start: number, end: number, value: S] | undefined，用于获取包含特定位置 x 的区间信息。它返回一个包含起始位置 start、结束位置 end 和对应的值 value 的元组。如果 erase 参数为 true，则在获取值的同时会将该区间删除。

• enumerateRange: enumerateRange(start: number, end: number, f: (start: number, end: number, value: S) => void, erase = false): void，用于遍历指定范围内的所有区间，并对每个区间执行回调函数 f。回调函数 f 接受每个区间的起始位置 start、结束位置 end 和对应的值 value 作为参数。如果 erase 参数为 true，则在遍历区间的同时会将遍历到的区间删除。

只要一个数据结构可以支持快速寻找前驱和后继以及快速删除和插入元素，那么就可以用来实现珂朵莉树，例如SortedDict/64叉树/Van Emde Boas Tree/链表，等等…
下面的珂朵莉树基于64叉树实现。
2. 解法

1. 用珂朵莉树维护区间字符类型，有序数组维护每个连续段的长度。
2. 因为每次单点修改最多影响到左、中、右三个段，为了避免分类讨论，每次修改前，遍历左段起点到右段终点的每个区间，删除这些区间的长度，单点修改后，再遍历左段起点到右段终点的每个区间，把这些区间长度加回来。
3. 每次查询的单个字符重复的最长子字符串，就是有序数组中的最大值。
   {:width=400}

代码

[-Solution]

function longestRepeating(s: string, queryCharacters: string, queryIndices: number[]): number[] {
   const n = s.length
   const q = queryIndices.length
   const res = Array(q).fill(1)

   const odt = new ODT(n, -1) // !珂朵莉树维护区间字符类型
   s.split('').forEach((c, i) => {
     odt.set(i, i + 1, c.charCodeAt(0) - 97)
   })

   const lens = new SortedList<number>() // !SortedList维护每个连续段的长度
   odt.enumerateAll((start, end, value) => {
     if (value !== -1) {
       lens.add(end - start)
     }
   })

   for (let i = 0; i < q; i++) {
     const target = queryCharacters.charCodeAt(i) - 97
     const pos = queryIndices[i]

     // !每次更新最多影响左中右三段区间
     // !先删除这三段区间的长度，修改后，再添加这三段区间的长度
     // 这种做法无需分类讨论
     const [start, end] = odt.get(pos)!
     const leftSeg = odt.get(start - 1)
     const rightSeg = odt.get(end)
     const first = leftSeg ? leftSeg[0] : 0
     const last = rightSeg ? rightSeg[1] : n
     odt.enumerateRange(first, last, (start, end) => {
       lens.discard(end - start)
     })

     odt.set(pos, pos + 1, target)

     odt.enumerateRange(first, last, (start, end) => {
       lens.add(end - start)
     })

     res[i] = lens.max()
   }

   return res
 }

[-珂朵莉树]

const INF = 2e15

/**
 * 珂朵莉树，基于数据随机的颜色段均摊。
 * `FastSet`实现.
 */
class ODT<S> {
  private _len = 0
  private _count = 0
  private readonly _leftLimit: number
  private readonly _rightLimit: number
  private readonly _noneValue: S
  private readonly _data: S[]
  private readonly _fs: FastSet

  /**
   * 指定区间长度和哨兵值建立一个ODT.初始时,所有位置的值为 {@link noneValue}.
   * @param n 区间范围为`[0, n)`.
   * @param noneValue 表示空值的哨兵值.
   */
  constructor(n: number, noneValue: S) {
    const data = Array(n)
    for (let i = 0; i < n; i++) data[i] = noneValue
    const fs = new FastSet(n)
    fs.insert(0)

    this._leftLimit = 0
    this._rightLimit = n
    this._noneValue = noneValue
    this._data = data
    this._fs = fs
  }

  /**
   * 返回包含`x`的区间的信息.
   * 0 <= x < n.
   */
  get(x: number, erase = false): [start: number, end: number, value: S] | undefined {
    if (x < this._leftLimit || x >= this._rightLimit) return undefined
    const start = this._fs.prev(x)
    const end = this._fs.next(x + 1)
    const value = this._data[start]
    if (erase && value !== this._noneValue) {
      this._len--
      this._count -= end - start
      this._data[start] = this._noneValue
      this._mergeAt(start)
      this._mergeAt(end)
    }
    return [start, end, value]
  }

  set(start: number, end: number, value: S): void {
    // eslint-disable-next-line @typescript-eslint/no-empty-function
    this.enumerateRange(start, end, () => {}, true) // remove
    this._fs.insert(start)
    this._data[start] = value
    if (value !== this._noneValue) {
      this._len++
      this._count += end - start
    }
    this._mergeAt(start)
    this._mergeAt(end)
  }

  enumerateAll(f: (start: number, end: number, value: S) => void): void {
    this.enumerateRange(this._leftLimit, this._rightLimit, f, false)
  }

  /**
   * 遍历范围`[start, end)`内的所有区间.
   */
  enumerateRange(
    start: number,
    end: number,
    f: (start: number, end: number, value: S) => void,
    erase = false
  ): void {
    if (start < this._leftLimit) start = this._leftLimit
    if (end > this._rightLimit) end = this._rightLimit
    if (start >= end) return

    const none = this._noneValue
    if (!erase) {
      let left = this._fs.prev(start)
      while (left < end) {
        const right = this._fs.next(left + 1)
        f(Math.max(left, start), Math.min(right, end), this._data[left])
        left = right
      }
      return
    }

    let p = this._fs.prev(start)
    if (p < start) {
      this._fs.insert(start)
      this._data[start] = this._data[p]
      if (this._data[start] !== none) {
        this._len++
      }
    }

    p = this._fs.next(end)
    if (end < p) {
      this._data[end] = this._data[this._fs.prev(end)]
      this._fs.insert(end)
      if (this._data[end] !== none) {
        this._len++
      }
    }

    p = start
    while (p < end) {
      const q = this._fs.next(p + 1)
      const x = this._data[p]
      f(p, q, x)
      if (this._data[p] !== none) {
        this._len--
        this._count -= q - p
      }
      this._fs.erase(p)
      p = q
    }

    this._fs.insert(start)
    this._data[start] = none
  }

  toString(): string {
    const sb: string[] = [`ODT({this.length}) {`]
    this.enumerateAll((start, end, value) => {
      const v = value === this._noneValue ? 'null' : value
      sb.push(`  [{start},{end}):{v}`)
    })
    sb.push('}')
    return sb.join('\n')
  }

  /**
   * 区间个数.
   */
  get length(): number {
    return this._len
  }

  /**
   * 区间内元素个数之和.
   */
  get count(): number {
    return this._count
  }

  private _mergeAt(p: number): void {
    if (p <= 0 || this._rightLimit <= p) return
    const q = this._fs.prev(p - 1)
    if (this._data[p] === this._data[q]) {
      if (this._data[p] !== this._noneValue) this._len--
      this._fs.erase(p)
    }
  }
}

/**
 * 利用位运算寻找区间的某个位置左侧/右侧第一个未被访问过的位置.
 * 初始时,所有位置都未被访问过.
 */
class FastSet {
  private readonly _n: number
  private readonly _lg: number
  private readonly _seg: Uint32Array[]

  constructor(n: number) {
    this._n = n
    const seg: Uint32Array[] = []
    while (true) {
      seg.push(new Uint32Array((n + 31) >>> 5))
      n = (n + 31) >>> 5
      if (n <= 1) {
        break
      }
    }
    this._lg = seg.length
    this._seg = seg
  }

  insert(i: number): void {
    for (let h = 0; h < this._lg; h++) {
      this._seg[h][i >>> 5] |= 1 << (i & 31)
      i >>>= 5
    }
  }

  has(i: number): boolean {
    return !!(this._seg[0][i >>> 5] & (1 << (i & 31)))
  }

  erase(i: number): void {
    for (let h = 0; h < this._lg; h++) {
      this._seg[h][i >>> 5] &= ~(1 << (i & 31))
      if (this._seg[h][i >>> 5]) {
        break
      }
      i >>>= 5
    }
  }

  /**
   * 返回x右侧第一个未被访问过的位置(包含x).
   * 如果不存在,返回`n`.
   */
  next(i: number): number {
    if (i < 0) {
      i = 0
    }
    if (i >= this._n) {
      return this._n
    }

    for (let h = 0; h < this._lg; h++) {
      if (i >>> 5 === this._seg[h].length) {
        break
      }
      let d = this._seg[h][i >>> 5] >>> (i & 31)
      if (d === 0) {
        i = (i >>> 5) + 1
        continue
      }
      // !trailingZeros32: 31 - Math.clz32(x & -x)
      i += 31 - Math.clz32(d & -d)
      for (let g = h - 1; ~g; g--) {
        i <<= 5
        const tmp = this._seg[g][i >>> 5]
        i += 31 - Math.clz32(tmp & -tmp)
      }
      return i
    }

    return this._n
  }

  /**
   * 返回x左侧第一个未被访问过的位置(包含x).
   * 如果不存在,返回`-1`.
   */
  prev(i: number): number {
    if (i < 0) {
      return -1
    }
    if (i >= this._n) {
      i = this._n - 1
    }

    for (let h = 0; h < this._lg; h++) {
      if (i === -1) {
        break
      }
      let d = this._seg[h][i >>> 5] << (31 - (i & 31))
      if (d === 0) {
        i = (i >>> 5) - 1
        continue
      }

      i -= Math.clz32(d)
      for (let g = h - 1; ~g; g--) {
        i <<= 5
        i += 31 - Math.clz32(this._seg[g][i >>> 5])
      }
      return i
    }

    return -1
  }

  /**
   * 遍历[start,end)区间内的元素.
   */
  enumerateRange(start: number, end: number, f: (v: number) => void): void {
    let x = start - 1
    while (true) {
      x = this.next(x + 1)
      if (x >= end) {
        break
      }
      f(x)
    }
  }

  toString(): string {
    const sb: string[] = []
    this.enumerateRange(0, this._n, v => sb.push(v.toString()))
    return `FastSet({sb.join(', ')})`
  }

  get min(): number | null {
    return this.next(-1)
  }

  get max(): number | null {
    return this.prev(this._n)
  }
}

[-SortedList]

/**
 * A fast SortedList with O(sqrt(n)) insertion and deletion.
 *
 * @_see {@link https://github.com/981377660LMT/algorithm-study/blob/master/22_%E4%B8%93%E9%A2%98/%E7%A6%BB%E7%BA%BF%E6%9F%A5%E8%AF%A2/%E6%A0%B9%E5%8F%B7%E5%88%86%E6%B2%BB/SortedList/SortedList.ts}
 * @_see {@link https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py}
 * @_see {@link https://qiita.com/tatyam/items/492c70ac4c955c055602}
 * @_see {@link https://speakerdeck.com/tatyam_prime/python-dezui-qiang-falseping-heng-er-fen-tan-suo-mu-wozuo-ru}
 */
class SortedList<T = number> {
  /** Optimized for 1e5 elements in javascript. Do not change it. */
  protected static readonly _BLOCK_RATIO = 50
  protected static readonly _REBUILD_RATIO = 170

  protected readonly _compareFn: (a: T, b: T) => number
  protected _size: number
  protected _blocks: T[][]

  constructor()
  constructor(iterable: Iterable<T>)
  constructor(compareFn: (a: T, b: T) => number)
  constructor(iterable: Iterable<T>, compareFn: (a: T, b: T) => number)
  constructor(compareFn: (a: T, b: T) => number, iterable: Iterable<T>)
  constructor(
    arg1?: Iterable<T> | ((a: T, b: T) => number),
    arg2?: Iterable<T> | ((a: T, b: T) => number)
  ) {
    let defaultCompareFn = (a: T, b: T) => (a as unknown as number) - (b as unknown as number)
    let defaultData: T[] = []
    if (arg1 !== void 0) {
      if (typeof arg1 === 'function') {
        defaultCompareFn = arg1
      } else {
        defaultData = [...arg1]
      }
    }
    if (arg2 !== void 0) {
      if (typeof arg2 === 'function') {
        defaultCompareFn = arg2
      } else {
        defaultData = [...arg2]
      }
    }

    this._compareFn = defaultCompareFn
    defaultData.sort(defaultCompareFn)
    this._blocks = this._initBlocks(defaultData)
    this._size = defaultData.length
  }

  add(value: T): void {
    if (!this._size) {
      this._blocks = [[value]]
      this._size = 1
      return
    }

    const blockIndex = this._findBlockIndex(value)
    if (blockIndex === -1) {
      this._blocks[this._blocks.length - 1].push(value)
      this._size++
      if (
        this._blocks[this._blocks.length - 1].length >
        this._blocks.length * SortedList._REBUILD_RATIO
      ) {
        this._rebuild()
      }
      return
    }

    const block = this._blocks[blockIndex]
    const pos = this._bisectRight(block, value)
    block.splice(pos, 0, value)
    this._size += 1
    if (block.length > this._blocks.length * SortedList._REBUILD_RATIO) {
      this._rebuild()
    }
  }

  /** 注意内部使用 `===` 来比较两个对象是否相等 */
  has(value: T): boolean {
    if (!this._size) return false
    const blockIndex = this._findBlockIndex(value)
    if (blockIndex === void 0) return false
    const block = this._blocks[blockIndex]
    const pos = this._bisectLeft(block, value)
    return pos < block.length && value === block[pos]
  }

  /** 注意内部使用 `===` 来比较两个对象是否相等 */
  discard(value: T): boolean {
    if (!this._size) return false
    const blockIndex = this._findBlockIndex(value)
    if (blockIndex === -1) return false
    const block = this._blocks[blockIndex]
    const pos = this._bisectLeft(block, value)
    if (pos === block.length || block[pos] !== value) {
      return false
    }
    block.splice(pos, 1)
    this._size -= 1
    if (!block.length) {
      this._blocks.splice(blockIndex, 1) // !Splice When Empty, Do Not Rebuild
    }
    return true
  }

  pop(index = -1): T | undefined {
    if (index < 0) index += this._size
    if (index < 0 || index >= this._size) {
      return void 0
    }
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      if (index < block.length) {
        const res = block[index]
        block.splice(index, 1)
        this._size -= 1
        if (!block.length) {
          this._blocks.splice(i, 1) // !Splice When Empty, Do Not Rebuild
        }
        return res
      }
      index -= block.length
    }
    return void 0
  }

  /**
   * 删除区间 [start, end) 内的元素.
   */
  erase(start: number, end: number): void {
    if (start < 0) start = 0
    if (end > this._size) end = this._size
    if (start >= end) return

    let [bid, startPos] = this._moveTo(start)
    let deleteCount = end - start
    for (; bid < this._blocks.length && deleteCount > 0; bid++) {
      const block = this._blocks[bid]
      const endPos = Math.min(block.length, startPos + deleteCount)
      const curDeleteCount = endPos - startPos
      if (curDeleteCount === block.length) {
        this._blocks.splice(bid, 1)
        bid--
      } else {
        block.splice(startPos, curDeleteCount)
      }
      deleteCount -= curDeleteCount
      this._size -= curDeleteCount
      startPos = 0
    }
  }

  at(index: number): T | undefined {
    if (index < 0) index += this._size
    if (index < 0 || index >= this._size) {
      return void 0
    }
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      if (index < block.length) {
        return block[index]
      }
      index -= block.length
    }
    return void 0
  }

  lower(value: T): T | undefined {
    for (let i = this._blocks.length - 1; ~i; i--) {
      const block = this._blocks[i]
      if (this._compareFn(block[0], value) < 0) {
        const pos = this._bisectLeft(block, value)
        return block[pos - 1]
      }
    }
    return void 0
  }

  higher(value: T): T | undefined {
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      if (this._compareFn(block[block.length - 1], value) > 0) {
        const pos = this._bisectRight(block, value)
        return block[pos]
      }
    }
    return void 0
  }

  floor(value: T): T | undefined {
    for (let i = this._blocks.length - 1; ~i; i--) {
      const block = this._blocks[i]
      if (this._compareFn(block[0], value) <= 0) {
        const pos = this._bisectRight(block, value)
        return block[pos - 1]
      }
    }
    return void 0
  }

  ceiling(value: T): T | undefined {
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      if (this._compareFn(block[block.length - 1], value) >= 0) {
        const pos = this._bisectLeft(block, value)
        return block[pos]
      }
    }
    return void 0
  }

  /**
   * Count the number of elements < value or
   * returns the index of the first element >= value.
   */
  bisectLeft(value: T): number {
    let res = 0
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      if (this._compareFn(value, block[block.length - 1]) <= 0) {
        return res + this._bisectLeft(block, value)
      }
      res += block.length
    }
    return res
  }

  /**
   * Count the number of elements <= value or
   * returns the index of the first element > value.
   */
  bisectRight(value: T): number {
    let res = 0
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      if (this._compareFn(value, block[block.length - 1]) < 0) {
        return res + this._bisectRight(block, value)
      }
      res += block.length
    }
    return res
  }

  slice(start: number, end: number): T[] {
    if (start < 0) start = 0
    if (end > this._size) end = this._size
    if (start >= end) return []
    let count = end - start
    const res: T[] = Array(count)
    let [bid, startPos] = this._moveTo(start)
    let ptr = 0
    for (; bid < this._blocks.length && count > 0; bid++) {
      const block = this._blocks[bid]
      const endPos = Math.min(block.length, startPos + count)
      const curCount = endPos - startPos
      for (let j = startPos; j < endPos; j++) {
        res[ptr++] = block[j]
      }
      count -= curCount
      startPos = 0
    }
    return res
  }

  clear(): void {
    this._blocks = []
    this._size = 0
  }

  min(): T | undefined {
    if (!this._size) return void 0
    return this._blocks[0][0]
  }

  max(): T | undefined {
    if (!this._size) return void 0
    const last = this._blocks[this._blocks.length - 1]
    return last[last.length - 1]
  }

  toString(): string {
    return `SortedList[{[...this].join(', ')}]`
  }

  /**
   * 返回一个迭代器，用于遍历区间 [start, end) 内的元素.
   */
  *islice(start: number, end: number, reverse = false): IterableIterator<T> {
    if (start < 0) start = 0
    if (end > this._size) end = this._size
    if (start >= end) return
    let count = end - start

    if (reverse) {
      let [bid, endPos] = this._moveTo(end)
      for (; ~bid && count > 0; bid--, ~bid && (endPos = this._blocks[bid].length)) {
        const block = this._blocks[bid]
        const startPos = Math.max(0, endPos - count)
        const curCount = endPos - startPos
        for (let j = endPos - 1; j >= startPos; j--) {
          yield block[j]
        }
        count -= curCount
      }
    } else {
      let [bid, startPos] = this._moveTo(start)
      for (; bid < this._blocks.length && count > 0; bid++) {
        const block = this._blocks[bid]
        const endPos = Math.min(block.length, startPos + count)
        const curCount = endPos - startPos
        for (let j = startPos; j < endPos; j++) {
          yield block[j]
        }
        count -= curCount
        startPos = 0
      }
    }
  }

  /**
   * 返回一个迭代器，用于遍历范围在 `[min, max] 闭区间`内的元素.
   */
  *irange(min: T, max: T, reverse = false): IterableIterator<T> {
    if (this._compareFn(min, max) > 0) {
      return
    }

    if (reverse) {
      let bi = this._findBlockIndex(max)
      if (bi === -1) {
        bi = this._blocks.length - 1
      }
      for (let i = bi; ~i; i--) {
        const block = this._blocks[i]
        for (let j = block.length - 1; ~j; j--) {
          const x = block[j]
          if (this._compareFn(x, min) < 0) {
            return
          }
          if (this._compareFn(x, max) <= 0) {
            yield x
          }
        }
      }
    } else {
      const bi = this._findBlockIndex(min)
      for (let i = bi; i < this._blocks.length; i++) {
        const block = this._blocks[i]
        for (let j = 0; j < block.length; j++) {
          const x = block[j]
          if (this._compareFn(x, max) > 0) {
            return
          }
          if (this._compareFn(x, min) >= 0) {
            yield x
          }
        }
      }
    }
  }

  enumerate(start: number, end: number, f: (value: T) => void, erase = false): void {
    let [bid, startPos] = this._moveTo(start)
    let count = end - start

    for (; bid < this._blocks.length && count > 0; bid++) {
      const block = this._blocks[bid]
      const endPos = Math.min(block.length, startPos + count)
      for (let j = startPos; j < endPos; j++) {
        f(block[j])
      }

      const curDeleteCount = endPos - startPos
      if (erase) {
        if (curDeleteCount === block.length) {
          this._blocks.splice(bid, 1)
          bid--
        } else {
          block.splice(startPos, curDeleteCount)
        }
        this._size -= curDeleteCount
      }

      count -= curDeleteCount
      startPos = 0
    }
  }

  forEach(callbackfn: (value: T, index: number) => void): void {
    let pos = 0
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      for (let j = 0; j < block.length; j++) {
        callbackfn(block[j], pos++)
      }
    }
  }

  *entries(): IterableIterator<[number, T]> {
    let pos = 0
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      for (let j = 0; j < block.length; j++) {
        yield [pos++, block[j]]
      }
    }
  }

  *[Symbol.iterator](): Iterator<T> {
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      for (let j = 0; j < block.length; j++) {
        yield block[j]
      }
    }
  }

  get length(): number {
    return this._size
  }

  // Find the block which should contain x. Block must not be empty.
  private _findBlockIndex(x: T): number {
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      if (this._compareFn(x, block[block.length - 1]) <= 0) {
        return i
      }
    }
    return -1
  }

  private _rebuild(): void {
    if (!this._size) {
      return
    }
    const bCount = Math.ceil(Math.sqrt(this._size / SortedList._BLOCK_RATIO))
    const bSize = ~~((this._size + bCount - 1) / bCount) // ceil
    const newB: T[][] = Array(bCount)
    for (let i = 0; i < bCount; i++) {
      newB[i] = []
    }
    let ptr = 0
    for (let i = 0; i < this._blocks.length; i++) {
      const b = this._blocks[i]
      for (let j = 0; j < b.length; j++) {
        newB[~~(ptr / bSize)].push(b[j])
        ptr++
      }
    }
    this._blocks = newB
  }

  // eslint-disable-next-line class-methods-use-this
  private _initBlocks(sorted: T[]): T[][] {
    const bCount = Math.ceil(Math.sqrt(sorted.length / SortedList._BLOCK_RATIO))
    const bSize = ~~((sorted.length + bCount - 1) / bCount) // ceil
    const newB: T[][] = Array(bCount)
    for (let i = 0; i < bCount; i++) {
      newB[i] = []
    }
    for (let i = 0; i < bCount; i++) {
      for (let j = i * bSize; j < Math.min((i + 1) * bSize, sorted.length); j++) {
        newB[i].push(sorted[j])
      }
    }
    return newB
  }

  private _bisectLeft(nums: T[], value: T): number {
    let left = 0
    let right = nums.length - 1
    while (left <= right) {
      const mid = (left + right) >> 1
      if (this._compareFn(value, nums[mid]) <= 0) {
        right = mid - 1
      } else {
        left = mid + 1
      }
    }
    return left
  }

  private _bisectRight(nums: T[], value: T): number {
    let left = 0
    let right = nums.length - 1
    while (left <= right) {
      const mid = (left + right) >> 1
      if (this._compareFn(value, nums[mid]) < 0) {
        right = mid - 1
      } else {
        left = mid + 1
      }
    }
    return left
  }

  private _moveTo(index: number): [blockId: number, startPos: number] {
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      if (index < block.length) {
        return [i, index]
      }
      index -= block.length
    }
    return [this._blocks.length, 0]
  }
}