結果
| 問題 | No.875 Range Mindex Query |
| ユーザー |
 くれちー
|
| 提出日時 | 2019-09-06 21:28:27 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 27,183 bytes |
| コンパイル時間 | 12,865 ms |
| コンパイル使用メモリ | 383,732 KB |
| 最終ジャッジ日時 | 2024-11-14 21:37:45 |
| 合計ジャッジ時間 | 13,682 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
error[E0433]: failed to resolve: use of undeclared crate or module `spella`
--> src/main.rs:926:11
|
926 | pub use spella::byte::{ByteChar, ByteStr, ByteString};
| ^^^^^^ use of undeclared crate or module `spella`
error[E0433]: failed to resolve: use of undeclared crate or module `spella`
--> src/main.rs:314:11
|
314 | use spella::byte::{ByteChar, ByteString};
| ^^^^^^ use of undeclared crate or module `spella`
error[E0433]: failed to resolve: use of undeclared crate or module `spella`
--> src/main.rs:410:11
|
410 | use spella::byte::{ByteChar, ByteStr};
| ^^^^^^ use of undeclared crate or module `spella`
error[E0433]: failed to resolve: use of undeclared crate or module `spella`
--> src/main.rs:479:11
|
479 | use spella::byte::{ByteChar, ByteStr, ByteString};
| ^^^^^^ use of undeclared crate or module `spella`
error[E0433]: failed to resolve: use of undeclared crate or module `spella`
--> src/main.rs:618:11
|
618 | use spella::byte::{ByteStr, FromByteStr};
| ^^^^^^ use of undeclared crate or module `spella`
error[E0433]: failed to resolve: use of undeclared crate or module `spella`
--> src/main.rs:687:11
|
687 | use spella::algebra::structures::Monoid;
| ^^^^^^ use of undeclared crate or module `spella`
warning: unused import: `std::collections::*`
--> src/main.rs:927:11
|
927 | pub use std::collections::*;
| ^^^^^^^^^^^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: unused import: `std::marker::PhantomData`
--> src/main.rs:930:11
|
930 | pub use std::marker::PhantomData;
| ^^^^^^^^^^^^^^^^^^^^^^^^
warning: unused import: `std::num::Wrapping`
--> src/main.rs:931:11
|
931 | pub use std::num::Wrapping;
| ^^^^^^^^^^^^^^^^^^
warning: unused imports: `RangeFrom`, `RangeTo`, `Range`
--> src/main.rs:932:22
ソースコード
#[allow(unused_imports)]
#[macro_use]
pub mod spella {
#[macro_use]
mod internal {
macro_rules! rev {
($m:ident [$($t_front:tt)*] [] [$($t_rear:tt)*]) => {
$m! { $($t_front)* $($t_rear)* }
};
($m:ident [$($t_front:tt)*] [$t_head:tt, $($t_tail:tt,)*] [$($t_rear:tt)*]) => {
rev! { $m [$($t_front)*] [$($t_tail,)*] [$t_head, $($t_rear)*] }
};
}
macro_rules! __for_each_tuple_internal {
(@invoke $m:ident! $(($i:tt: $T:ident),)+) => {
$m! { $($i: $T),+ }
};
($m:ident!) => {};
($m:ident! $i0:tt: $T0:ident, $($i:tt: $T:ident,)*) => {
__for_each_tuple_internal! { $m! $($i: $T,)* }
rev! { __for_each_tuple_internal [@invoke $m!] [($i0: $T0), $(($i: $T),)*] [] }
};
}
macro_rules! for_each_tuple {
($m:ident) => {
__for_each_tuple_internal! {
$m! 11: T11, 10: T10, 9: T9, 8: T8, 7: T7, 6: T6, 5: T5, 4: T4, 3: T3, 2: T2, 1: T1, 0: T0,
}
};
}
}
pub mod algebra {
pub mod structures {
pub use self::abelian_group::*;
pub use self::associative_magma::*;
pub use self::commutative_magma::*;
pub use self::group::*;
pub use self::invertible_magma::*;
pub use self::magma::*;
pub use self::monoid::*;
pub use self::semigroup::*;
pub use self::unital_magma::*;
mod abelian_group {
use super::{CommutativeMagma, Group};
pub trait AbelianGroup: Group + CommutativeMagma {}
impl<T: Group + CommutativeMagma> AbelianGroup for T {}
}
mod associative_magma {
use super::Magma;
pub trait AssociativeMagma: Magma {}
impl<T> AssociativeMagma for Option<T> where T: AssociativeMagma {}
impl AssociativeMagma for () {}
macro_rules! imp {
($($i:tt: $T:ident),*) => {
impl<$($T),*> AssociativeMagma for ($($T,)*)
where
$($T: AssociativeMagma,)*
{
}
}
}
for_each_tuple! { imp }
}
mod commutative_magma {
use super::Magma;
pub trait CommutativeMagma: Magma {}
impl<T> CommutativeMagma for Option<T> where T: CommutativeMagma {}
impl CommutativeMagma for () {}
macro_rules! imp {
($($i:tt: $T:ident),*) => {
impl<$($T),*> CommutativeMagma for ($($T,)*)
where
$($T: CommutativeMagma,)*
{
}
}
}
for_each_tuple! { imp }
}
mod group {
use super::{AssociativeMagma, InvertibleMagma, UnitalMagma};
pub trait Group: AssociativeMagma + UnitalMagma + InvertibleMagma {}
impl<T: AssociativeMagma + UnitalMagma + InvertibleMagma> Group for T {}
}
mod invertible_magma {
use super::{Magma, UnitalMagma};
pub trait InvertibleMagma: Magma + UnitalMagma {
fn invert(&self) -> Self;
fn inverse_op(&self, rhs: &Self) -> Self {
self.op(&rhs.invert())
}
fn inverse_op_assign_right(&mut self, rhs: &Self) {
*self = self.inverse_op(rhs);
}
fn inverse_op_assign_left(&mut self, lhs: &Self) {
*self = lhs.inverse_op(self);
}
}
impl InvertibleMagma for () {
fn invert(&self) -> Self {
()
}
}
macro_rules! imp {
($($i:tt: $T:ident),*) => {
impl<$($T),*> InvertibleMagma for ($($T,)*)
where
$($T: InvertibleMagma,)*
{
fn invert(&self) -> Self {
($(self.$i.invert(),)*)
}
fn inverse_op(&self, rhs: &Self) -> Self {
($(self.$i.inverse_op(&rhs.$i),)*)
}
fn inverse_op_assign_right(&mut self, rhs: &Self) {
$(self.$i.inverse_op_assign_right(&rhs.$i);)*
}
fn inverse_op_assign_left(&mut self, lhs: &Self) {
$(self.$i.inverse_op_assign_left(&lhs.$i);)*
}
}
}
}
for_each_tuple! { imp }
}
mod magma {
pub trait Magma: Clone {
fn op(&self, rhs: &Self) -> Self;
fn op_assign_right(&mut self, rhs: &Self) {
*self = self.op(rhs);
}
fn op_assign_left(&mut self, lhs: &Self) {
*self = lhs.op(self);
}
}
impl<T> Magma for Option<T>
where
T: Magma,
{
fn op(&self, rhs: &Self) -> Self {
match (self, rhs) {
(&Some(ref lhs), &Some(ref rhs)) => Some(lhs.op(rhs)),
(&Some(ref value), &None) | (&None, &Some(ref value)) => Some(value.clone()),
(&None, &None) => None,
}
}
fn op_assign_right(&mut self, rhs: &Self) {
match (self, rhs.as_ref()) {
(&mut Some(ref mut lhs), Some(rhs)) => lhs.op_assign_right(rhs),
(lhs @ &mut None, Some(rhs)) => *lhs = Some(rhs.clone()),
(_, None) => {}
}
}
fn op_assign_left(&mut self, lhs: &Self) {
match (lhs.as_ref(), self) {
(Some(lhs), &mut Some(ref mut rhs)) => rhs.op_assign_left(lhs),
(Some(lhs), rhs @ &mut None) => *rhs = Some(lhs.clone()),
(None, _) => {}
}
}
}
impl Magma for () {
fn op(&self, _rhs: &Self) -> Self {
()
}
}
macro_rules! imp {
($($i:tt: $T:ident),*) => {
impl<$($T),*> Magma for ($($T,)*)
where
$($T: Magma,)*
{
fn op(&self, rhs: &Self) -> Self {
($(self.$i.op(&rhs.$i),)*)
}
fn op_assign_right(&mut self, rhs: &Self) {
$(self.$i.op_assign_right(&rhs.$i);)*
}
fn op_assign_left(&mut self, lhs: &Self) {
$(self.$i.op_assign_left(&lhs.$i);)*
}
}
};
}
for_each_tuple! { imp }
}
mod monoid {
use super::{AssociativeMagma, UnitalMagma};
pub trait Monoid: AssociativeMagma + UnitalMagma {}
impl<T: AssociativeMagma + UnitalMagma> Monoid for T {}
}
mod semigroup {
use super::AssociativeMagma;
pub trait Semigroup: AssociativeMagma {}
impl<T: AssociativeMagma> Semigroup for T {}
}
mod unital_magma {
use super::Magma;
pub trait UnitalMagma: Magma {
fn identity() -> Self;
}
impl<T> UnitalMagma for Option<T>
where
T: Magma,
{
fn identity() -> Self {
None
}
}
impl UnitalMagma for () {
fn identity() -> Self {
()
}
}
macro_rules! imp {
($($i:tt: $T:ident),*) => {
impl<$($T),*> UnitalMagma for ($($T,)*)
where
$($T: UnitalMagma,)*
{
fn identity() -> Self {
($($T::identity(),)*)
}
}
}
}
for_each_tuple! { imp }
}
}
}
pub mod byte {
pub use self::byte_char::*;
pub use self::byte_str::*;
pub use self::byte_string::*;
pub use self::from_byte_str::*;
mod byte_char {
use std::fmt::{self, Debug, Display, Formatter};
#[derive(Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct ByteChar(pub u8);
impl Debug for ByteChar {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
write!(f, "b'{}'", self.0 as char)
}
}
impl Display for ByteChar {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
write!(f, "{}", self.0 as char)
}
}
}
mod byte_str {
use spella::byte::{ByteChar, ByteString};
use std::fmt::{self, Debug, Display, Formatter};
use std::ops::{Deref, DerefMut};
#[derive(PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct ByteStr([ByteChar]);
macro_rules! cast {
(mut $x:expr, $($T:ty)=>*) => {
unsafe { &mut *($x $(as *mut $T)*) }
};
($x:expr, $($T:ty)=>*) => {
unsafe { &*($x $(as *const $T)*) }
};
}
impl ByteStr {
pub fn from_bytes(s: &[u8]) -> &Self {
cast!(s, [u8] => [ByteChar] => ByteStr)
}
pub fn from_bytes_mut(s: &mut [u8]) -> &mut Self {
cast!(mut s, [u8] => [ByteChar] => ByteStr)
}
pub fn from_byte_chars(s: &[ByteChar]) -> &Self {
cast!(s, [ByteChar] => ByteStr)
}
pub fn from_byte_chars_mut(s: &mut [ByteChar]) -> &mut Self {
cast!(mut s, [ByteChar] => ByteStr)
}
pub fn as_byte_chars(&self) -> &[ByteChar] {
&self.0
}
pub fn as_byte_chars_mut(&mut self) -> &mut [ByteChar] {
&mut self.0
}
pub fn as_bytes(&self) -> &[u8] {
cast!(self, ByteStr => [ByteChar] => [u8])
}
pub fn as_bytes_mut(&mut self) -> &mut [u8] {
cast!(mut self, ByteStr => [ByteChar] => [u8])
}
}
impl ToOwned for ByteStr {
type Owned = ByteString;
fn to_owned(&self) -> ByteString {
ByteString::from(self.0.to_owned())
}
}
impl Debug for ByteStr {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
write!(f, "b\"")?;
for &c in &self.0 {
write!(f, "{}", c)?;
}
write!(f, "\"")
}
}
impl Display for ByteStr {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
for &c in &self.0 {
write!(f, "{}", c)?;
}
Ok(())
}
}
impl Deref for ByteStr {
type Target = [ByteChar];
fn deref(&self) -> &[ByteChar] {
self.as_byte_chars()
}
}
impl DerefMut for ByteStr {
fn deref_mut(&mut self) -> &mut [ByteChar] {
self.as_byte_chars_mut()
}
}
}
mod byte_string {
use spella::byte::{ByteChar, ByteStr};
use std::borrow::{Borrow, BorrowMut};
use std::fmt::{self, Debug, Display, Formatter};
use std::ops::{Deref, DerefMut};
#[derive(Clone, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct ByteString(Vec<ByteChar>);
impl ByteString {
pub fn into_byte_chars(self) -> Vec<ByteChar> {
self.0
}
pub fn as_byte_str(&self) -> &ByteStr {
ByteStr::from_byte_chars(&self.0)
}
pub fn as_mut_byte_str(&mut self) -> &mut ByteStr {
ByteStr::from_byte_chars_mut(&mut self.0)
}
}
impl From<Vec<ByteChar>> for ByteString {
fn from(s: Vec<ByteChar>) -> ByteString {
ByteString(s)
}
}
impl Borrow<ByteStr> for ByteString {
fn borrow(&self) -> &ByteStr {
self.as_byte_str()
}
}
impl BorrowMut<ByteStr> for ByteString {
fn borrow_mut(&mut self) -> &mut ByteStr {
self.as_mut_byte_str()
}
}
impl Debug for ByteString {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
Debug::fmt(self.as_byte_str(), f)
}
}
impl Display for ByteString {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
Display::fmt(self.as_byte_str(), f)
}
}
impl Deref for ByteString {
type Target = ByteStr;
fn deref(&self) -> &ByteStr {
ByteStr::from_byte_chars(&self.0)
}
}
impl DerefMut for ByteString {
fn deref_mut(&mut self) -> &mut ByteStr {
ByteStr::from_byte_chars_mut(&mut self.0)
}
}
}
mod from_byte_str {
use spella::byte::{ByteChar, ByteStr, ByteString};
use std::error::Error;
use std::fmt::{self, Debug, Display, Formatter};
use std::str::{self, FromStr, Utf8Error};
pub trait FromByteStr: Sized {
type Err;
fn from_byte_str(s: &ByteStr) -> Result<Self, Self::Err>;
}
macro_rules! fn_description {
() => {
fn description(&self) -> &str {
"description() is deprecated; use Display"
}
};
}
#[derive(Debug)]
pub struct ParseByteCharError(ParseByteCharErrorKind);
#[derive(Debug)]
enum ParseByteCharErrorKind {
EmptyByteStr,
TooManyByteChars,
}
impl Display for ParseByteCharError {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
use self::ParseByteCharErrorKind::*;
f.write_str(match self.0 {
EmptyByteStr => "empty `ByteStr`",
TooManyByteChars => "too many `ByteChar`s",
})
}
}
impl Error for ParseByteCharError {
fn_description! {}
}
impl FromByteStr for ByteChar {
type Err = ParseByteCharError;
fn from_byte_str(s: &ByteStr) -> Result<Self, Self::Err> {
use self::ParseByteCharErrorKind::*;
match s.len() {
1 => Ok(unsafe { *s.get_unchecked(0) }),
0 => Err(ParseByteCharError(EmptyByteStr)),
_ => Err(ParseByteCharError(TooManyByteChars)),
}
}
}
#[derive(Debug)]
pub enum ParseByteStringError {}
impl Display for ParseByteStringError {
fn fmt(&self, _: &mut Formatter) -> fmt::Result {
match *self {}
}
}
impl Error for ParseByteStringError {
fn_description! {}
}
impl FromByteStr for ByteString {
type Err = ParseByteStringError;
fn from_byte_str(s: &ByteStr) -> Result<Self, Self::Err> {
Ok(ByteString::from(s.to_vec()))
}
}
pub struct ParseFromStrError<T: FromStr>(ParseFromStrErrorKind<T>);
enum ParseFromStrErrorKind<T: FromStr> {
Utf8Error(Utf8Error),
FromStrError(T::Err),
}
impl<T: FromStr> Debug for ParseFromStrError<T>
where
T::Err: Debug,
{
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
use self::ParseFromStrErrorKind::*;
match self.0 {
Utf8Error(ref err) => f.debug_tuple("Utf8Error").field(err).finish(),
FromStrError(ref err) => f.debug_tuple("FromStrError").field(err).finish(),
}
}
}
impl<T: FromStr> Display for ParseFromStrError<T>
where
T::Err: Display,
{
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
use self::ParseFromStrErrorKind::*;
match self.0 {
Utf8Error(ref err) => write!(f, "{}", err),
FromStrError(ref err) => write!(f, "{}", err),
}
}
}
impl<T: FromStr> Error for ParseFromStrError<T>
where
T::Err: Debug + Display,
{
fn_description! {}
}
impl<T: FromStr> FromByteStr for T {
type Err = ParseFromStrError<T>;
fn from_byte_str(s: &ByteStr) -> Result<T, Self::Err> {
use self::ParseFromStrErrorKind::*;
str::from_utf8(s.as_bytes())
.map_err(|e| ParseFromStrError(Utf8Error(e)))
.and_then(|s| s.parse().map_err(|e| ParseFromStrError(FromStrError(e))))
}
}
}
}
pub mod io {
pub use self::scanner::*;
mod scanner {
use spella::byte::{ByteStr, FromByteStr};
use std::io::{self, BufRead};
#[derive(Debug)]
pub struct Scanner<R> {
reader: R,
buf: Vec<u8>,
pos: usize,
}
const INITIAL_CAPACITY: usize = 32;
impl<R: BufRead> Scanner<R> {
pub fn new(reader: R) -> Self {
Scanner {
reader: reader,
buf: Vec::with_capacity(INITIAL_CAPACITY),
pos: 0,
}
}
pub fn next<T: FromByteStr>(&mut self) -> io::Result<Result<T, T::Err>> {
self.next_byte_str().map(T::from_byte_str)
}
pub fn next_byte_str(&mut self) -> io::Result<&ByteStr> {
if self.buf.is_empty() {
self.read_line()?;
}
loop {
match self.buf.get(self.pos) {
Some(&b' ') => self.pos += 1,
Some(&b'\n') => self.read_line()?,
Some(_) => break,
None => return Err(io::Error::from(io::ErrorKind::UnexpectedEof)),
}
}
let start = self.pos;
self.pos += 1;
loop {
match self.buf.get(self.pos) {
Some(&b' ') | Some(&b'\n') | None => break,
Some(_) => self.pos += 1,
}
}
Ok(ByteStr::from_bytes(&self.buf[start..self.pos]))
}
fn read_line(&mut self) -> io::Result<()> {
self.buf.clear();
self.pos = 0;
self.reader.read_until(b'\n', &mut self.buf)?;
Ok(())
}
}
}
}
pub mod sequences {
pub use self::segment_tree::SegmentTree;
pub mod segment_tree {
use super::*;
use spella::algebra::structures::Monoid;
use std::collections::VecDeque;
use std::iter::{self, FromIterator};
use std::mem;
use std::ops::{Deref, DerefMut, Range};
#[derive(Clone, PartialEq, Eq, Debug, Hash)]
pub struct SegmentTree<T> {
vec: Vec<T>,
base_len: usize,
len: usize,
}
impl<M: Monoid> FromIterator<M> for SegmentTree<M> {
fn from_iter<I>(iter: I) -> Self
where
I: IntoIterator<Item = M>,
{
let iter = iter.into_iter();
let min_len = iter.size_hint().0;
let (min_base_len, min_vec_len) = Self::extend_len(min_len);
let mut deque = VecDeque::with_capacity(min_vec_len);
if min_base_len > 1 {
deque.extend(iter::repeat(M::identity()).take(min_base_len - 1));
}
deque.extend(iter);
let len = deque.len() - min_base_len.saturating_sub(1);
let (base_len, _) = Self::extend_len(len);
if base_len > min_base_len {
for identity in iter::repeat(M::identity()).take(base_len - min_base_len) {
deque.push_front(identity);
}
} else if min_base_len > base_len {
deque.drain(..min_base_len - base_len);
}
let mut tree = SegmentTree {
vec: deque.into(),
base_len: base_len,
len: len,
};
for node in (1..base_len).rev() {
tree.recalc(node);
}
tree
}
}
impl<M: Monoid> SegmentTree<M> {
pub fn new(len: usize) -> Self {
let (base_len, vec_len) = Self::extend_len(len);
let vec = if vec_len == 0 {
vec![]
} else {
vec![M::identity(); vec_len]
};
SegmentTree {
vec: vec,
base_len: base_len,
len: len,
}
}
pub fn len(&self) -> usize {
self.len
}
pub fn get(&self, index: usize) -> &M {
assert_index(index, self.len());
self.node(self.node_index(index))
}
pub fn get_mut(&mut self, index: usize) -> GetMut<M> {
assert_index(index, self.len());
GetMut {
node: self.node_index(index),
tree: self,
}
}
pub fn fold(&self, index: Range<usize>) -> M {
assert_index_range(&index, self.len());
let mut start = self.node_index(index.start);
let mut end = self.node_index(index.end);
let mut lacc = M::identity();
let mut racc = M::identity();
while start < end {
if start & 1 == 1 {
lacc.op_assign_right(self.node(start));
start += 1;
}
if end & 1 == 1 {
end -= 1;
racc.op_assign_left(self.node(end));
}
start >>= 1;
end >>= 1;
}
lacc.op(&racc)
}
fn extend_len(len: usize) -> (usize, usize) {
if len == 0 {
(0, 0)
} else {
len
.checked_next_power_of_two()
.and_then(|base_len| {
(base_len - 1)
.checked_add(len)
.map(|vec_len| (base_len, vec_len))
})
.unwrap_or_else(|| panic!("length too large: {:?}", len))
}
}
fn node_index(&self, index: usize) -> usize {
self.base_len + index
}
fn recalc(&mut self, node: usize) {
let l = node << 1;
let r = (node << 1) | 1;
let last = self.vec.len();
debug_assert_eq!(last, self.node_index(self.len() - 1));
if l <= last {
*self.node_mut(node) = if r <= last {
self.node(l).op(&self.node(r))
} else {
self.node(l).clone()
};
}
}
fn rebuild(&mut self, mut node: usize) {
while {
node >>= 1;
node > 0
} {
self.recalc(node);
}
}
fn node(&self, node: usize) -> &M {
&self.vec[node - 1]
}
fn node_mut(&mut self, node: usize) -> &mut M {
&mut self.vec[node - 1]
}
}
pub struct GetMut<'a, M: 'a + Monoid> {
tree: &'a mut SegmentTree<M>,
node: usize,
}
impl<'a, M: Monoid> Drop for GetMut<'a, M> {
fn drop(&mut self) {
self.tree.rebuild(self.node);
}
}
impl<'a, M: Monoid> Deref for GetMut<'a, M> {
type Target = M;
fn deref(&self) -> &M {
self.tree.node(self.node)
}
}
impl<'a, M: Monoid> DerefMut for GetMut<'a, M> {
fn deref_mut(&mut self) -> &mut M {
self.tree.node_mut(self.node)
}
}
impl<'a, M: Monoid> GetMut<'a, M> {
pub fn update<F>(&mut self, f: F)
where
F: FnOnce(M) -> M,
{
let value = mem::replace::<M>(self, M::identity());
mem::replace::<M>(self, f(value));
}
}
}
use std::ops::{Range, RangeTo};
macro_rules! assert_index {
($cond:expr, $index:expr, $len:expr) => {
assert!(
$cond,
"index out of bounds: the len is {:?} but the index is {:?}",
$len, $index
)
};
}
fn assert_index(index: usize, len: usize) {
assert_index!(index < len, index, len);
}
fn assert_index_range(index: &Range<usize>, len: usize) {
assert!(
index.start <= index.end,
"range start is greater than range end: {:?}",
index
);
assert_index!(index.end <= len, index, len);
}
}
}
mod prelude {
pub use spella::byte::{ByteChar, ByteStr, ByteString};
pub use std::collections::*;
pub use std::io::prelude::*;
pub use std::iter::FromIterator;
pub use std::marker::PhantomData;
pub use std::num::Wrapping;
pub use std::ops::{Range, RangeFrom, RangeTo};
pub use std::{cell, cmp, f64, i32, i64, isize, iter, mem, rc, str, time, u32, u64, usize};
}
use prelude::*;
const CUSTOM_STACK_SIZE_MEBIBYTES: Option<usize> = None;
fn main() {
fn exec_solver() {
let stdin = std::io::stdin();
let stdout = std::io::stdout();
#[cfg(not(debug_assertions))]
let mut writer = std::io::BufWriter::new(stdout.lock());
#[cfg(debug_assertions)]
let mut writer = stdout.lock();
solve(stdin.lock(), &mut writer);
writer.flush().unwrap();
}
if let Some(stack_size_mebibytes) = CUSTOM_STACK_SIZE_MEBIBYTES {
std::thread::Builder::new()
.name("exec_solver".to_owned())
.stack_size(stack_size_mebibytes * 1024 * 1024)
.spawn(exec_solver)
.unwrap()
.join()
.unwrap();
} else {
exec_solver();
}
}
fn solve<R: BufRead, W: Write>(reader: R, mut writer: W) {
let mut _scanner = spella::io::Scanner::new(reader);
#[allow(unused_macros)]
macro_rules! scan {
($T:ty) => {
_scanner.next::<$T>().unwrap().unwrap()
};
($($T:ty),+) => {
($(scan!($T)),+)
};
($($T:ty),+; $n:expr $(; $m:expr)*) => {{
(0..$n).map(|_| scan!($($T),+ $(; $m)*)).collect::<Vec<_>>()
}};
}
#[allow(unused_macros)]
macro_rules! scan_iter {
($($T:ty),+; $n:expr) => {
(0..$n).map(|_| scan!($($T),+))
};
}
#[allow(unused_macros)]
macro_rules! print {
($fmt:expr) => {
write!(writer, $fmt).unwrap()
};
($fmt:expr, $($arg:tt)*) => {
write!(writer, $fmt, $($arg)*).unwrap()
};
}
#[allow(unused_macros)]
macro_rules! println {
($fmt:expr) => {
writeln!(writer, $fmt).unwrap()
};
($fmt:expr, $($arg:tt)*) => {
writeln!(writer, $fmt, $($arg)*).unwrap()
};
}
#[allow(unused_macros)]
macro_rules! eprint {
($fmt:expr) => {
#[cfg(debug_assertions)]
write!(std::io::stderr(), $fmt).unwrap()
};
($fmt:expr, $($arg:tt)*) => {
#[cfg(debug_assertions)]
write!(std::io::stderr(), $fmt, $($arg)*).unwrap()
};
}
#[allow(unused_macros)]
macro_rules! eprintln {
($fmt:expr) => {
#[cfg(debug_assertions)]
writeln!(std::io::stderr(), $fmt).unwrap()
};
($fmt:expr, $($arg:tt)*) => {
#[cfg(debug_assertions)]
writeln!(std::io::stderr(), $fmt, $($arg)*).unwrap()
};
}
#[allow(unused_macros)]
macro_rules! dbg {
($($x:expr),+) => {{
eprintln!(concat!("[{}:{}] ", $(stringify!($x), " = {:?}; "),+), file!(), line!(), $($x),+);
}};
}
use spella::algebra::structures::*;
#[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Debug)]
struct M(usize, u64);
impl Magma for M {
fn op(&self, rhs: &Self) -> Self {
*if self.1 < rhs.1 { self } else { rhs }
}
}
impl AssociativeMagma for M {}
impl CommutativeMagma for M {}
impl UnitalMagma for M {
fn identity() -> Self {
M(usize::max_value(), u64::max_value())
}
}
let (n, q) = scan!(usize, usize);
let a = scan!(u64; n);
let mut segtree = spella::sequences::SegmentTree::<M>::from_iter(
a.into_iter().enumerate().map(|(i, a_i)| M(i, a_i)),
);
for (t, l, r) in scan_iter!(u8, usize, usize; q) {
let l = l - 1;
let r = r - 1;
match t {
1 => {
let M(_, a_l) = *segtree.get(l);
let M(_, a_r) = *segtree.get(r);
segtree.get_mut(r).1 = a_l;
segtree.get_mut(l).1 = a_r;
}
2 => {
let M(i, _) = segtree.fold(l..r + 1);
println!("{}", i + 1);
}
_ => unreachable!(),
}
}
}