#880214 (TypeScript) No.875 Range Mindex Query

• 問題: No.875 Range Mindex Query
• ユーザー: 草苺奶昔
• 提出日時: 2023-06-13 02:24:11
• 言語: TypeScript (5.4.3)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 5,316 bytes
• コンパイル時間: 7,448 ms
• コンパイル使用メモリ: 148,568 KB
• 最終ジャッジ日時: 2024-06-12 01:21:23
• 合計ジャッジ時間: 8,186 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

コンパイルメッセージ

main.ts(3,21): error TS2307: Cannot find module 'fs' or its corresponding type declarations.
main.ts(4,25): error TS2307: Cannot find module 'path' or its corresponding type declarations.
main.ts(162,36): error TS2304: Cannot find name '__dirname'.
main.ts(164,28): error TS2580: Cannot find name 'process'. Do you need to install type definitions for node? Try `npm i --save-dev @types/node`.

ソースコード

import * as fs from 'fs'
import { resolve } from 'path'
/**
 * 单点更新,区间查询的线段树.
 */
class SegmentTreePointUpdateRangeQuery<E = number> {
  private readonly _n: number
  private readonly _size: number
  private readonly _seg: E[]
  private readonly _e: () => E
  private readonly _op: (a: E, b: E) => E

  /**
   * @param nOrLeaves 大小或叶子节点的值.
   * @param e 幺元.
   * @param op 结合律.
   */
  constructor(nOrLeaves: number | ArrayLike<E>, e: () => E, op: (a: E, b: E) => E) {
    const n = typeof nOrLeaves === 'number' ? nOrLeaves : nOrLeaves.length
    let size = 1
    while (size < n) size <<= 1
    const seg = Array(size << 1)
    for (let i = 0; i < seg.length; i++) seg[i] = e()

    this._n = n
    this._size = size
    this._seg = seg
    this._e = e
    this._op = op

    if (typeof nOrLeaves !== 'number') this.build(nOrLeaves)
  }

  set(index: number, value: E): void {
    if (index < 0 || index >= this._n) return
    index += this._size
    this._seg[index] = value
    while ((index >>= 1)) {
      this._seg[index] = this._op(this._seg[index << 1], this._seg[(index << 1) | 1])
    }
  }

  get(index: number): E {
    if (index < 0 || index >= this._n) return this._e()
    return this._seg[index + this._size]
  }

  /**
   * 将`index`处的值与作用素`value`结合.
   */
  update(index: number, value: E): void {
    if (index < 0 || index >= this._n) return
    index += this._size
    this._seg[index] = this._op(this._seg[index], value)
    while ((index >>= 1)) {
      this._seg[index] = this._op(this._seg[index << 1], this._seg[(index << 1) | 1])
    }
  }

  /**
   * 查询区间`[start,end)`的聚合值.
   * 0 <= start <= end <= n.
   */
  query(start: number, end: number): E {
    if (start < 0) start = 0
    if (end > this._n) end = this._n
    if (start >= end) return this._e()

    let leftRes = this._e()
    let rightRes = this._e()
    for (start += this._size, end += this._size; start < end; start >>= 1, end >>= 1) {
      if (start & 1) leftRes = this._op(leftRes, this._seg[start++])
      if (end & 1) rightRes = this._op(this._seg[--end], rightRes)
    }
    return this._op(leftRes, rightRes)
  }

  queryAll(): E {
    return this._seg[1]
  }

  /**
   * 树上二分查询最大的`end`使得`[start,end)`内的值满足`predicate`.
   */
  maxRight(start: number, predicate: (value: E) => boolean): number {
    if (start === this._n) return this._n
    start += this._size
    let res = this._e()
    while (true) {
      while (!(start & 1)) start >>= 1
      if (!predicate(this._op(res, this._seg[start]))) {
        while (start < this._size) {
          start <<= 1
          if (predicate(this._op(res, this._seg[start]))) {
            res = this._op(res, this._seg[start])
            start++
          }
        }
        return start - this._size
      }
      res = this._op(res, this._seg[start])
      start++
      if ((start & -start) === start) break
    }
    return this._n
  }

  /**
   * 树上二分查询最小的`start`使得`[start,end)`内的值满足`predicate`
   */
  minLeft(end: number, predicate: (value: E) => boolean): number {
    if (!end) return 0
    end += this._size
    let res = this._e()
    while (true) {
      end--
      while (end > 1 && end & 1) end >>= 1
      if (!predicate(this._op(this._seg[end], res))) {
        while (end < this._size) {
          end = (end << 1) | 1
          if (predicate(this._op(this._seg[end], res))) {
            res = this._op(this._seg[end], res)
            end--
          }
        }
        return end + 1 - this._size
      }
      res = this._op(this._seg[end], res)
      if ((end & -end) === end) break
    }
    return 0
  }

  build(arr: ArrayLike<E>): void {
    if (arr.length !== this._n) throw new RangeError(`length must be equal to ${this._n}`)
    for (let i = 0; i < arr.length; i++) {
      this._seg[i + this._size] = arr[i] // 叶子结点
    }
    for (let i = this._size - 1; ~i; i--) {
      this._seg[i] = this._op(this._seg[i << 1], this._seg[(i << 1) | 1])
    }
  }

  toString(): string {
    const sb: string[] = []
    sb.push('SegmentTreePointUpdateRangeQuery(')
    for (let i = 0; i < this._n; i++) {
      if (i) sb.push(', ')
      sb.push(JSON.stringify(this.get(i)))
    }
    sb.push(')')
    return sb.join('')
  }
}


function useInput(path?: string) {
  let data: string
  if (path) {
    data = fs.readFileSync(resolve(__dirname, path), 'utf8')
  } else {
    data = fs.readFileSync(process.stdin.fd, 'utf8')
  }

  const lines = data.split(/\r\n|\r|\n/)
  let lineId = 0
  const input = (): string => lines[lineId++]

  return {
    input
  }
}

const { input } = useInput()

const [N, Q] = input().split(' ').map(Number)
const a = input().split(' ').map(Number)

const INF = 2e15
const seg = new SegmentTreePointUpdateRangeQuery(a, () => INF, Math.min)

for (let i = 0; i < Q; i++) {
  let [c, l, r] = input().split(' ').map(Number)
  if (c === 1) {
    l--
    r--
    const vl = seg.get(l)
    seg.set(l, seg.get(r))
    seg.set(r, vl)
  } else {
    l--

    const mn = seg.query(l, r)
    const a1 = seg.maxRight(l, n => n > mn)
    let a2 = seg.minLeft(r, n => n > mn)
    a2--
    if (a1 !== a2) {
      throw new Error('a1 !== a2')
    }
    console.log(a1 + 1)
  }
}