結果
| 問題 | No.875 Range Mindex Query |
| コンテスト | |
| ユーザー |
 guricerin
|
| 提出日時 | 2020-01-29 16:06:16 |
| 言語 | F# (F# 4.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,734 bytes |
| 記録 | |
| コンパイル時間 | 12,442 ms |
| コンパイル使用メモリ | 213,528 KB |
| 実行使用メモリ | 77,184 KB |
| 最終ジャッジ日時 | 2024-09-16 01:06:38 |
| 合計ジャッジ時間 | 23,171 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge6 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | WA * 18 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.fsproj を復元しました (628 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) /home/judge/data/code/Main.fs(163,13): warning FS0025: この式のパターン マッチが不完全です たとえば、値 '[|_; _; _; _|]' はパターンに含まれないケースを示す可能性があります。 [/home/judge/data/code/main.fsproj] /home/judge/data/code/Main.fs(150,9): warning FS0025: この式のパターン マッチが不完全です たとえば、値 '[|_; _; _|]' はパターンに含まれないケースを示す可能性があります。 [/home/judge/data/code/main.fsproj] main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
open System
open System.Collections.Generic
[<AutoOpen>]
module Cin =
let read f = stdin.ReadLine() |> f
let reada f = stdin.ReadLine().Split() |> Array.map f
let readChars() = read string |> Seq.toArray
let readInts() = readChars() |> Array.map (fun x -> Convert.ToInt32(x.ToString()))
[<AutoOpen>]
module Cout =
let writer = new IO.StreamWriter(new IO.BufferedStream(Console.OpenStandardOutput()))
let print (s: string) = writer.Write s
let println (s: string) = writer.WriteLine s
let inline puts (s: ^a) = string s |> println
type LazySegTree<'Monoid, 'OpMonoid> =
{
/// 実データの要素数
size: int
/// 木の高さ
height: int
/// モノイドの単位元
mUnity: 'Monoid
/// 作用素の単位元
omUnity: 'OpMonoid
nodes: 'Monoid array
lazyNodes: 'OpMonoid array
f: F<'Monoid>
g: G<'Monoid, 'OpMonoid>
h: H<'OpMonoid> }
and F<'Monoid> = 'Monoid -> 'Monoid -> 'Monoid
and G<'Monoid, 'OpMonoid> = 'Monoid -> 'OpMonoid -> 'Monoid
and H<'OpMonoid> = 'OpMonoid -> 'OpMonoid -> 'OpMonoid
[<RequireQualifiedAccess>]
[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module LazySegTree =
let internal sizeAndHeight n =
let rec loop sAcc hAcc =
if sAcc < n then loop (sAcc <<< 1) (hAcc + 1) else (sAcc, hAcc)
loop 1 0
let internal parent i = (i - 1) / 2
let internal leftChild i = (i <<< 1) + 0
let internal rightChild i = (i <<< 1) + 1
let internal leafIdx tree k = k + tree.size
let init (n: int) f g h (mUnity: 'Monoid) (omUnity: 'OpMonoid): LazySegTree<_, _> =
let size, height = sizeAndHeight n
let nodes = Array.init (size * 2) (fun _ -> mUnity)
let lazyNodes = Array.init (size * 2) (fun _ -> omUnity)
{ LazySegTree.size = size
height = height
mUnity = mUnity
omUnity = omUnity
nodes = nodes
lazyNodes = lazyNodes
f = f
g = g
h = h }
/// k番目(0-indexed)の要素をxに更新
let set (k: int) x tree: unit =
let size = tree.size
let idx = leafIdx tree k
tree.nodes.[idx] <- x
/// k番目のノードについて遅延評価を行う
let internal apply (k: int) tree =
let nodes, lazyNodes = tree.nodes, tree.lazyNodes
let omUnity = tree.omUnity
let g = tree.g
match lazyNodes.[k] = omUnity with
| true -> nodes.[k]
| false -> g nodes.[k] lazyNodes.[k]
/// 親から子への遅延伝播
let internal propagate (k: int) tree: unit =
let nodes, lazyNodes = tree.nodes, tree.lazyNodes
let omUnity = tree.omUnity
let lc, rc = leftChild k, rightChild k
let h = tree.h
let g = tree.g
if lazyNodes.[k] <> omUnity then
if k < tree.size then
lazyNodes.[lc] <- h lazyNodes.[lc] lazyNodes.[k]
lazyNodes.[rc] <- h lazyNodes.[rc] lazyNodes.[k]
// nodes.[k] <- apply k tree
nodes.[k] <- g nodes.[k] lazyNodes.[k]
lazyNodes.[k] <- omUnity
let rec internal updateCore a b (x: 'OpMonoid) k l r tree =
propagate k tree
let nodes = tree.nodes
let lazyNodes = tree.lazyNodes
let f = tree.f
let h = tree.h
if r <= a || b <= l then
nodes.[k]
elif a <= l && r <= b then
lazyNodes.[k] <- h lazyNodes.[k] x
propagate k tree
nodes.[k]
else
let lc, rc, mid = leftChild k, rightChild k, (l + r) >>> 1
let lm = updateCore a b x lc l mid tree
let rm = updateCore a b x rc mid r tree
nodes.[k] <- f lm rm
nodes.[k]
/// 半開区間[l, r)を更新する
let update (l: int) (r: int) (x: 'OpMonoid) (tree: LazySegTree<'Monoid, 'OpMonoid>): 'Monoid =
updateCore l r x 1 0 tree.size tree
let rec internal queryCore (a: int) (b: int) (k: int) (l: int) (r: int) tree: 'Monoid =
propagate k tree
let mUnity = tree.mUnity
let f = tree.f
if r <= a || b <= l then
mUnity
elif a <= l && r <= b then
tree.nodes.[k]
else
let lc, rc, mid = leftChild k, rightChild k, (l + r) >>> 1
let lm = queryCore a b lc l mid tree
let rm = queryCore a b rc mid r tree
f lm rm
/// 半開区間[l, r)の演算結果
let query (l: int) (r: int) tree: 'Monoid = queryCore l r 1 0 tree.size tree
/// k番目の要素を取得
let get (k: int) tree = query k (k + 1) tree
let dump tree =
let size = tree.size
let nodes = tree.nodes.[0..size - 1]
let mutable buf = ""
for a in nodes do
buf <- sprintf "%s%A " buf a
buf
let main() =
let [| N; Q |] = reada int
let A = reada int64
let f (x: int * int64) (y: int * int64) =
let xi, xv = x
let yi, yv = y
if xi < yi then x else y
let e = Int32.MaxValue, Int64.MaxValue
let seg = LazySegTree.init N f f f e e
for i in 0 .. N - 1 do
seg |> LazySegTree.set i (i, A.[i])
for _ in 0 .. Q - 1 do
let [| q; l; r |] = reada int
match q with
| 1 ->
let l, r = l - 1, r - 1
let lv = seg |> LazySegTree.get l
let rv = seg |> LazySegTree.get r
seg |> LazySegTree.set l rv
seg |> LazySegTree.set r lv
| 2 ->
let (i, _) = seg |> LazySegTree.query l (r + 1)
puts (i + 1)
| _ -> failwithf "unreachable"
()
main()
writer.Close()