結果

問題 No.875 Range Mindex Query
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-06-13 02:21:55
言語 TypeScript
(5.4.3)
結果
WA  
実行時間 -
コード長 4,906 bytes
コンパイル時間 7,614 ms
コンパイル使用メモリ 260,780 KB
実行使用メモリ 80,448 KB
最終ジャッジ日時 2023-09-02 18:52:00
合計ジャッジ時間 17,923 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
権限があれば一括ダウンロードができます

ソースコード

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 === 0) 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 {
    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])
    }
  }
}

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.update(l, seg.get(r))
    seg.update(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--

    console.log(a2)
  }
}
0