結果

問題 No.875 Range Mindex Query
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-06-13 02:24:11
言語 TypeScript
(5.4.3)
結果
AC  
実行時間 1,215 ms / 2,000 ms
コード長 5,316 bytes
コンパイル時間 10,077 ms
コンパイル使用メモリ 254,412 KB
実行使用メモリ 79,948 KB
最終ジャッジ日時 2023-09-02 18:54:22
合計ジャッジ時間 17,559 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 79 ms
42,372 KB
testcase_01 AC 100 ms
47,964 KB
testcase_02 AC 112 ms
48,540 KB
testcase_03 AC 86 ms
43,180 KB
testcase_04 AC 93 ms
43,568 KB
testcase_05 AC 86 ms
43,052 KB
testcase_06 AC 98 ms
46,096 KB
testcase_07 AC 103 ms
48,092 KB
testcase_08 AC 91 ms
43,612 KB
testcase_09 AC 96 ms
43,648 KB
testcase_10 AC 113 ms
48,404 KB
testcase_11 AC 956 ms
79,188 KB
testcase_12 AC 875 ms
74,352 KB
testcase_13 AC 794 ms
79,576 KB
testcase_14 AC 780 ms
79,948 KB
testcase_15 AC 899 ms
78,448 KB
testcase_16 AC 1,136 ms
78,328 KB
testcase_17 AC 1,215 ms
78,412 KB
testcase_18 AC 1,182 ms
79,184 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 


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)
  }
}
0