結果
| 問題 | No.875 Range Mindex Query |
| ユーザー |
 cotton_fn_
|
| 提出日時 | 2020-11-08 02:23:06 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 42 ms / 2,000 ms |
| コード長 | 7,919 bytes |
| コンパイル時間 | 24,208 ms |
| コンパイル使用メモリ | 378,792 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-07-22 15:00:13 |
| 合計ジャッジ時間 | 16,448 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 18 |
ソースコード
#![allow(unused_imports, unused_macros)]use kyoproio::*;use std::{collections::*,io::{self, prelude::*},iter,mem::{replace, swap},};fn run<I: Input, O: Write>(mut kin: I, mut out: O) {macro_rules! output { ($($args:expr),+) => { write!(&mut out, $($args),+).unwrap(); }; }macro_rules! outputln {($($args:expr),+) => { output!($($args),+); outputln!(); };() => { output!("\n"); if cfg!(debug_assertions) { out.flush().unwrap(); } }}let (n, q): (usize, usize) = kin.input();let mut st = SegmentTree::new(n, || (!0, 0), |a, b| *a.min(b));for i in 0..n {let a: u32 = kin.input();st.set(i, (a, i as u32 + 1));}for (t, l, r) in kin.iter::<(u8, usize, usize)>().take(q) {if t == 1 {let x = st[l - 1];let y = st[r - 1];st.set(l - 1, (y.0, x.1));st.set(r - 1, (x.0, y.1));} else {let (_, i) = st.fold(l - 1, r);outputln!("{}", i);}}}pub struct SegmentTree<T, Z, F> {zero: Z,f: F,a: Vec<T>,}impl<T, Z: Fn() -> T, F: Fn(&T, &T) -> T> SegmentTree<T, Z, F> {pub fn new(n: usize, zero: Z, f: F) -> Self {let n = n.next_power_of_two() << 1;Self {a: std::iter::repeat_with(|| zero()).take(n).collect(),zero,f,}}pub fn len(&self) -> usize {self.a.len() >> 1}pub fn set(&mut self, i: usize, value: T) {let mut i = self.len() + i;self.a[i] = value;while (i >> 1) > 0 {i >>= 1;self.a[i] = (self.f)(&self.a[i << 1], &self.a[(i << 1) + 1]);}}pub fn update(&mut self, i: usize, value: &T) -> &T {let j = self.len() + i;self.set(i, (self.f)(&value, &self.a[j]));&self.a[j]}// [l, r)pub fn fold(&self, l: usize, r: usize) -> T {let mut l = self.len() + l;let mut r = self.len() + r;let mut x = (self.zero)();let mut y = (self.zero)();while l != r {if l & 1 == 1 {x = (self.f)(&x, &self.a[l]);l += 1;}if r & 1 == 1 {r -= 1;y = (self.f)(&self.a[r], &y);}l >>= 1;r >>= 1;}(self.f)(&x, &y)}}impl<T, Z: Fn() -> T, F: Fn(&T, &T) -> T> std::ops::Index<usize> for SegmentTree<T, Z, F> {type Output = T;fn index(&self, i: usize) -> &Self::Output {&self.a[self.len() + i]}}// -----------------------------------------------------------------------------fn main() -> io::Result<()> {std::thread::Builder::new().stack_size(64 * 1024 * 1024).spawn(|| {run(KInput::new(io::stdin().lock()),io::BufWriter::new(io::stdout().lock()),)})?.join().unwrap();Ok(())}// -----------------------------------------------------------------------------pub mod kyoproio {use std::io::prelude::*;pub trait Input {fn bytes(&mut self) -> &[u8];fn str(&mut self) -> &str {std::str::from_utf8(self.bytes()).unwrap()}fn input<T: InputParse>(&mut self) -> T {T::input(self)}fn iter<T: InputParse>(&mut self) -> Iter<T, Self> {Iter(self, std::marker::PhantomData)}fn seq<T: InputParse, B: std::iter::FromIterator<T>>(&mut self, n: usize) -> B {self.iter().take(n).collect()}}pub struct KInput<R> {src: R,buf: Vec<u8>,pos: usize,len: usize,}impl<R: Read> KInput<R> {pub fn new(src: R) -> Self {Self {src,buf: vec![0; 1 << 16],pos: 0,len: 0,}}}impl<R: Read> Input for KInput<R> {fn bytes(&mut self) -> &[u8] {loop {while let Some(delim) = self.buf[self.pos..self.len].iter().position(|b| b.is_ascii_whitespace()){let range = self.pos..self.pos + delim;self.pos += delim + 1;if delim > 0 {return &self.buf[range];}}if self.pos > 0 {self.buf.copy_within(self.pos..self.len, 0);self.len -= self.pos;self.pos = 0;}if self.len >= self.buf.len() {self.buf.resize(2 * self.buf.len(), 0);}let read = self.src.read(&mut self.buf[self.len..]).unwrap();if read == 0 {let range = self.pos..self.len;self.pos = self.len;return &self.buf[range];}self.len += read;}}}pub struct Iter<'a, T, I: ?Sized>(&'a mut I, std::marker::PhantomData<*const T>);impl<'a, T: InputParse, I: Input + ?Sized> Iterator for Iter<'a, T, I> {type Item = T;fn next(&mut self) -> Option<T> {Some(self.0.input())}}pub trait InputParse: Sized {fn input<I: Input + ?Sized>(src: &mut I) -> Self;}impl InputParse for Vec<u8> {fn input<I: Input + ?Sized>(src: &mut I) -> Self {src.bytes().to_owned()}}macro_rules! from_str_impl {{ $($T:ty)* } => {$(impl InputParse for $T {fn input<I: Input + ?Sized>(src: &mut I) -> Self {src.str().parse::<$T>().unwrap()}})*}}from_str_impl! { String char bool f32 f64 }macro_rules! parse_int_impl {{ $($I:ty: $U:ty)* } => {$(impl InputParse for $I {fn input<I: Input + ?Sized>(src: &mut I) -> Self {let f = |s: &[u8]| s.iter().fold(0, |x, b| 10 * x + (b & 0xf) as $I);let s = src.bytes();if let Some((&b'-', t)) = s.split_first() { -f(t) } else { f(s) }}}impl InputParse for $U {fn input<I: Input + ?Sized>(src: &mut I) -> Self {src.bytes().iter().fold(0, |x, b| 10 * x + (b & 0xf) as $U)}})*};}parse_int_impl! { isize:usize i8:u8 i16:u16 i32:u32 i64:u64 i128:u128 }macro_rules! tuple_impl {($H:ident $($T:ident)*) => {impl<$H: InputParse, $($T: InputParse),*> InputParse for ($H, $($T),*) {fn input<I: Input + ?Sized>(src: &mut I) -> Self {($H::input(src), $($T::input(src)),*)}}tuple_impl!($($T)*);};() => {}}tuple_impl!(A B C D E F G);macro_rules! array_impl {{ $($N:literal)* } => {$(impl<T: InputParse> InputParse for [T; $N] {fn input<I: Input + ?Sized>(src: &mut I) -> Self {let mut arr = std::mem::MaybeUninit::uninit();unsafe {let ptr = arr.as_mut_ptr() as *mut T;for i in 0..$N {ptr.add(i).write(src.input());}arr.assume_init()}}})*};}array_impl! { 1 2 3 4 5 6 7 8 }#[macro_export]macro_rules! kdbg {($($v:expr),*) => {if cfg!(debug_assertions) { dbg!($($v),*) } else { ($($v),*) }}}}