結果
| 問題 | No.3446 Range Adjacent Differences |
| ユーザー |
👑  ArcAki
|
| 提出日時 | 2026-10-22 18:18:55 |
| 言語 | Rust (1.99.0 + proconio + num + itertools + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 512 ms / 2,200 ms |
| + 997µs | |
| コード長 | 43,993 bytes |
| 記録 | |
| コンパイル時間 | 2,525 ms |
| コンパイル使用メモリ | 225,832 KB |
| 実行使用メモリ | 23,808 KB |
| 最終ジャッジ日時 | 2026-10-22 18:19:19 |
| 合計ジャッジ時間 | 14,858 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge4_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 26 |
ソースコード
#[allow(unused_imports)]
use std::{
convert::{Infallible, TryFrom, TryInto as _}, fmt::{self, Debug, Display, Formatter,},
fs::File, hash::{Hash, Hasher, BuildHasherDefault}, iter::{Product, Sum}, marker::PhantomData,
ops::{Add, AddAssign, Sub, SubAssign, Div, DivAssign, Mul, MulAssign,
Neg, RangeBounds, BitAnd, BitAndAssign, BitOr, BitXor, BitXorAssign, BitOrAssign, Index, IndexMut},
str::FromStr, sync::{atomic::{self, AtomicU32, AtomicU64}, Once},
collections::{*, btree_set::Range, btree_map::Range as BTreeRange}, mem::{take, swap},
cmp::{self, Reverse, Ordering, Eq, PartialEq, PartialOrd},
thread::LocalKey, f64::consts::PI, time::Instant, cell::RefCell,
io::{self, stdin, Read, read_to_string, BufWriter, BufReader, stdout, Write},
ptr::null_mut, println, print,debug_assert,debug_assert_eq,debug_assert_ne,
matches
};
#[allow(unused_imports)]
use core::panic;
pub mod fxhash {
use std::hash::BuildHasherDefault;
const K: u64 = 0x517c_c1b7_2722_0a95;
#[derive(Default)]
pub struct FxHasher {
pub hash: u64,
}
impl FxHasher {
#[inline(always)]
fn mix_u64(mut h: u64, x: u64) -> u64 {
h = h.rotate_left(5) ^ x;
h = h.wrapping_mul(K);
let x2 = x ^ (x >> 33) ^ (x << 11);
h = h.rotate_left(5) ^ x2;
h = h.wrapping_mul(K);
h
}
#[inline(always)]
fn write_u64_impl(&mut self, x: u64) {
self.hash = Self::mix_u64(self.hash, x);
}
}
impl std::hash::Hasher for FxHasher {
#[inline(always)]
fn finish(&self) -> u64 {
self.hash
}
#[inline(always)]
fn write(&mut self, bytes: &[u8]) {
let mut h = self.hash;
for &b in bytes {
h = h.rotate_left(5) ^ (b as u64);
h = h.wrapping_mul(K);
}
self.hash = h;
}
#[inline(always)]
fn write_u64(&mut self, i: u64) { self.write_u64_impl(i); }
#[inline(always)]
fn write_u32(&mut self, i: u32) { self.write_u64_impl(i as u64); }
#[inline(always)]
fn write_u16(&mut self, i: u16) { self.write_u64_impl(i as u64); }
#[inline(always)]
fn write_u8 (&mut self, i: u8 ) { self.write_u64_impl(i as u64); }
#[inline(always)]
fn write_usize(&mut self, i: usize) { self.write_u64_impl(i as u64); }
#[inline(always)]
fn write_i64(&mut self, i: i64) { self.write_u64_impl(i as u64); }
#[inline(always)]
fn write_i32(&mut self, i: i32) { self.write_u64_impl(i as u64); }
#[inline(always)]
fn write_i16(&mut self, i: i16) { self.write_u64_impl(i as u64); }
#[inline(always)]
fn write_i8 (&mut self, i: i8 ) { self.write_u64_impl(i as u64); }
#[inline(always)]
fn write_isize(&mut self, i: isize) { self.write_u64_impl(i as u64); }
}
pub type FxBuildHasher = BuildHasherDefault<FxHasher>;
pub type FxMap<K, V> = std::collections::HashMap<K, V, FxBuildHasher>;
pub type FxSet<K> = std::collections::HashSet<K, FxBuildHasher>;
}
pub fn gcd(mut a: i64, mut b: i64)->i64{a=a.abs();b=b.abs();if a==0{return b;}else if b==0{return a;}let l1 = a.trailing_zeros();let l2 = b.trailing_zeros();
a >>= l1; b >>= l2;while a!=b{let x = (a^b).trailing_zeros();if a<b{swap(&mut a, &mut b)}a = (a-b)>>x;}a << l1.min(l2)}
pub fn gcd_i32(mut a: i32, mut b: i32)->i32{a=a.abs();b=b.abs();if a==0{return b;}else if b==0{return a;}let l1 = a.trailing_zeros();let l2 = b.trailing_zeros();
a >>= l1; b >>= l2;while a!=b{let x = (a^b).trailing_zeros();if a<b{swap(&mut a, &mut b)}a = (a-b)>>x;}a << l1.min(l2)}
pub fn factorial_i64(n: usize)->(Vec<i64>, Vec<i64>){
let mut res = vec![1; n+1];let mut inv = vec![1; n+1];for i in 0..n{ res[i+1] = (res[i]*(i+1)as i64)%MOD; }
inv[n] = mod_inverse(res[n], MOD);for i in (0..n).rev(){ inv[i] = inv[i+1]*(i+1) as i64%MOD; }(res, inv) }
pub fn floor(a:i64, b:i64)->i64{let res=(a%b+b)%b;(a-res)/b}
pub fn modulo(a: i64, b: i64)->i64{(a%b+b)%b}
pub fn extended_gcd(a:i64,b:i64)->(i64,i64,i64)
{if b==0{(a,1,0)}else{let(g,x,y)=extended_gcd(b,a%b);(g,y,x-floor(a,b)*y)}}
pub fn mod_inverse(a:i64,m:i64)->i64{let(_,x,_) =extended_gcd(a,m);(x%m+m)%m}
pub fn comb(a: i64, b: i64, f: &Vec<(i64, i64)>)->i64{
if a<b{return 0;}else if b==0 || a==b{ return 1; }
else{let x=f[a as usize].0;
let y=f[(a-b) as usize].1;let z=f[b as usize].1;return((x*y)%MOD)*z%MOD;}}
pub fn factorial(x: i64)->Vec<(i64, i64)>{
let mut f=vec![(1i64,1i64),(1, 1)];let mut z = 1i64;
let mut inv = vec![0; x as usize+10];inv[1] = 1;
for i in 2..x+1{z=(z*i)%MOD;
let w=(MOD-inv[(MOD%i)as usize]*(MOD/i)%MOD)%MOD;
inv[i as usize] = w;
f.push((z, (f[i as usize-1].1*w)%MOD));}return f;}
pub fn fast_mod_pow(mut x: i64,p: usize, m: i64)->i64{
x %= m;
let mut res=1;let mut t=x;let mut z=p;while z > 0{
if z%2==1{res = (res*t)%m;}t = (t*t)%m;z /= 2; }res}
pub trait SortD{ fn sort_d(&mut self); }
impl<T: Ord> SortD for Vec<T>{ fn sort_d(&mut self) {self.sort_by(|u, v| v.cmp(&u));} }
pub trait Mx{fn max(&self, rhs: Self)->Self;}
impl Mx for f64{ fn max(&self, rhs: Self)->Self{if *self < rhs{ rhs } else { *self } }}
pub trait Mi{ fn min(&self, rhs: Self)->Self; }
impl Mi for f64{ fn min(&self, rhs: Self)->Self{ if *self > rhs{ rhs } else { *self } } }
pub trait Chmax: PartialOrd + Sized {
#[inline]
fn chmax(&mut self, rhs: Self) {
if *self < rhs {
*self = rhs;
}
}
}
impl<T: PartialOrd> Chmax for T {}
pub trait Chmin: PartialOrd + Sized {
#[inline]
fn chmin(&mut self, rhs: Self) {
if *self > rhs {
*self = rhs;
}
}
}
impl<T: PartialOrd> Chmin for T {}
#[allow(unused_macros)]
macro_rules! chmax {
($lhs:expr, $rhs:expr $(,)?) => {{
let candidate = $rhs;
let target = &mut $lhs;
if *target < candidate {
*target = candidate;
true
} else {
false
}
}};
}
#[allow(unused_macros)]
macro_rules! chmin {
($lhs:expr, $rhs:expr $(,)?) => {{
let candidate = $rhs;
let target = &mut $lhs;
if *target > candidate {
*target = candidate;
true
} else {
false
}
}};
}
#[allow(unused)]
use proconio::{*, marker::*};
#[allow(unused)]
use fxhash::{FxMap, FxSet};
#[allow(unused)]
use ac_library::{*};
pub struct MintCombination{
fact: Vec<MI>,
inv_fact: Vec<MI>,
inv: Vec<MI>,
}
impl MintCombination{
pub fn new(n: usize)->Self {
let mut fact = vec![MI::new(1); n+1];
let mut inv_fact = vec![MI::new(0); n+1];
let mut inv = vec![MI::new(1); n+1];
for i in 0..n{
fact[i+1] = fact[i]*(i+1);
}
inv_fact[n] = MI::new(1)/fact[n];
for i in (0..n).rev(){
inv_fact[i] = inv_fact[i+1]*(i+1);
inv[i+1] = fact[i]*inv_fact[i+1];
}
MintCombination { fact, inv_fact, inv }
}
#[inline]
pub fn inv(&self, x: usize)->MI{
self.inv[x]
}
#[inline]
pub fn f(&self, x: usize)->MI{
self.fact[x]
}
#[inline]
pub fn fi(&self, x: usize)->MI{
self.inv_fact[x]
}
#[inline]
pub fn p(&self, x: usize, y: usize)->MI{
if x < y{MI::new(0)}
else {self.fact[x]*self.inv_fact[x-y]}
}
#[inline]
pub fn c(&self, x: usize, y: usize)->MI{
if x < y{return MI::new(0);}
self.fact[x]*self.inv_fact[y]*self.inv_fact[x-y]
}
}
#[allow(dead_code)]
const INF: i64 = 1<<60;
#[allow(dead_code)]
const I: i32 = 1<<30;
#[allow(dead_code)]
const MOD: i64 = 998244353;
#[allow(dead_code)]
const D: [(usize, usize); 4] = [(1, 0), (0, 1), (!0, 0), (0, !0)];
#[allow(dead_code)]
pub fn c2d(c: u8)->(usize, usize){match c{b'U'=>(!0,0),b'D'=>(1,0),b'L'=>(0,!0),b'R'=>(0,1),_=>unreachable!()}}
#[allow(dead_code)]
pub fn c2d_i64(c: u8)->(i64, i64){match c{b'U'=>(-1,0),b'D'=>(1,0),b'L'=>(0,-1),b'R'=>(0,1),_=>unreachable!()}}
#[allow(dead_code)]
pub fn join2str<T: ToString>(v: &[T])->String{v.iter().map(|x| x.to_string()).collect::<Vec<_>>().join(" ")}
#[allow(dead_code)]
pub fn join2nospace<T: ToString>(v: &[T])->String{v.iter().map(|x| x.to_string()).collect::<Vec<_>>().join("")}
#[allow(dead_code)]
const D2: [(usize, usize); 8] = [(1, 0), (1, 1), (0, 1), (!0, 1), (!0, 0), (!0, !0), (0, !0), (1, !0)];
// Source: https://github.com/InverseAki/arcaki_library/blob/main/src/Basic/basic_io.rs
pub struct Input {
buf: Vec<u8>,
pos: usize,
}
impl Input {
#[inline]
pub fn new() -> Self {
let mut buf = Vec::new();
io::stdin().read_to_end(&mut buf).unwrap();
buf.push(0);
Self { buf, pos: 0 }
}
#[inline(always)]
fn skip_whitespace(&mut self) {
while self.buf[self.pos].is_ascii_whitespace() {
self.pos += 1;
}
}
#[inline(always)]
fn token_range(&mut self) -> (usize, usize) {
self.skip_whitespace();
let l = self.pos;
while self.buf[self.pos] > b' ' {
self.pos += 1;
}
(l, self.pos)
}
#[inline(always)]
pub fn byte(&mut self) -> u8 {
self.skip_whitespace();
let res = self.buf[self.pos];
while self.buf[self.pos] > b' ' {
self.pos += 1;
}
res
}
#[inline(always)]
pub fn bytes(&mut self) -> Vec<u8> {
let (l, r) = self.token_range();
self.buf[l..r].to_vec()
}
#[inline]
pub fn binary_u64(&mut self) -> Vec<u64> {
let (l, r) = self.token_range();
Self::pack_binary(&self.buf[l..r])
}
#[inline]
pub fn binary_u64_len(&mut self, n: usize) -> Vec<u64> {
if n == 0 {
return Vec::new();
}
self.skip_whitespace();
let l = self.pos;
let r = l.checked_add(n).expect("binary token length overflow");
assert!(r < self.buf.len(), "binary token shorter than requested");
assert!(
self.buf[r] == 0 || self.buf[r].is_ascii_whitespace(),
"binary token longer than requested"
);
self.pos = r;
Self::pack_binary(&self.buf[l..r])
}
fn pack_binary(bytes: &[u8]) -> Vec<u64> {
let mut invalid = 0u64;
let words = bytes
.chunks(64)
.map(|chunk| {
let mut word = 0;
let mut groups = chunk.chunks_exact(8);
for (i, group) in groups.by_ref().enumerate() {
let raw = u64::from_le_bytes(group.try_into().unwrap());
invalid |= (raw & 0xfefe_fefe_fefe_fefe) ^ 0x3030_3030_3030_3030;
let bits = raw & 0x0101_0101_0101_0101;
let packed = bits.wrapping_mul(0x0102_0408_1020_4080) >> 56;
word |= packed << (i * 8);
}
let offset = (chunk.len() / 8) * 8;
for (i, &c) in groups.remainder().iter().enumerate() {
invalid |= ((c & 0xfe) ^ b'0') as u64;
word |= ((c & 1) as u64) << (offset + i);
}
word
})
.collect();
assert_eq!(invalid, 0, "binary token must contain only 0 and 1");
words
}
#[inline(always)]
pub fn string(&mut self) -> String {
let (l, r) = self.token_range();
unsafe { String::from_utf8_unchecked(self.buf[l..r].to_vec()) }
}
#[inline(always)]
pub fn char(&mut self) -> char {
let (l, r) = self.token_range();
unsafe {
std::str::from_utf8_unchecked(&self.buf[l..r])
.chars()
.next()
.unwrap()
}
}
#[inline(always)]
pub fn chars(&mut self) -> Vec<char> {
let (l, r) = self.token_range();
unsafe {
std::str::from_utf8_unchecked(&self.buf[l..r])
.chars()
.collect()
}
}
#[inline]
pub fn f64(&mut self) -> f64 {
let (l, r) = self.token_range();
unsafe {
std::str::from_utf8_unchecked(&self.buf[l..r])
.parse()
.unwrap()
}
}
#[inline(always)]
pub fn usize1(&mut self) -> usize {
self.usize() - 1
}
#[inline]
pub fn vec_byte(&mut self, n: usize) -> Vec<u8> {
let mut res = Vec::with_capacity(n);
for _ in 0..n {
res.push(self.byte());
}
res
}
#[inline]
pub fn vec_bytes(&mut self, n: usize) -> Vec<Vec<u8>> {
let mut res = Vec::with_capacity(n);
for _ in 0..n {
res.push(self.bytes());
}
res
}
#[inline]
pub fn vec_string(&mut self, n: usize) -> Vec<String> {
let mut res = Vec::with_capacity(n);
for _ in 0..n {
res.push(self.string());
}
res
}
#[inline]
pub fn vec_char(&mut self, n: usize) -> Vec<char> {
let mut res = Vec::with_capacity(n);
for _ in 0..n {
res.push(self.char());
}
res
}
#[inline]
pub fn vec_chars(&mut self, n: usize) -> Vec<Vec<char>> {
let mut res = Vec::with_capacity(n);
for _ in 0..n {
res.push(self.chars());
}
res
}
#[inline]
pub fn byte_grid(&mut self, n: usize) -> Vec<Vec<u8>> {
let mut res = Vec::with_capacity(n);
for _ in 0..n {
res.push(self.bytes());
}
res
}
#[inline]
pub fn vec_f64(&mut self, n: usize) -> Vec<f64> {
let mut res = Vec::with_capacity(n);
for _ in 0..n {
res.push(self.f64());
}
res
}
#[inline]
pub fn vec_usize1(&mut self, n: usize) -> Vec<usize> {
let mut res = Vec::with_capacity(n);
for _ in 0..n {
res.push(self.usize1());
}
res
}
}
macro_rules! impl_unsigned_input {
($($name:ident, $vec_name:ident, $t:ty);* $(;)?) => {
impl Input {
$(
#[inline(always)]
pub fn $name(&mut self) -> $t {
let buf = &self.buf;
let mut i = self.pos;
while buf[i].is_ascii_whitespace() {
i += 1;
}
let mut res: $t = 0;
while buf[i].is_ascii_digit() {
res = res * 10 + (buf[i] - b'0') as $t;
i += 1;
}
self.pos = i;
res
}
#[inline]
pub fn $vec_name(&mut self, n: usize) -> Vec<$t> {
let mut res = Vec::with_capacity(n);
for _ in 0..n {
res.push(self.$name());
}
res
}
)*
}
};
}
macro_rules! impl_signed_input {
($($name:ident, $vec_name:ident, $t:ty);* $(;)?) => {
impl Input {
$(
#[inline(always)]
pub fn $name(&mut self) -> $t {
let buf = &self.buf;
let mut i = self.pos;
while buf[i].is_ascii_whitespace() {
i += 1;
}
let neg = buf[i] == b'-';
if neg {
i += 1;
}
let mut res: $t = 0;
if neg {
while buf[i].is_ascii_digit() {
res = res * 10 - (buf[i] - b'0') as $t;
i += 1;
}
} else {
while buf[i].is_ascii_digit() {
res = res * 10 + (buf[i] - b'0') as $t;
i += 1;
}
}
self.pos = i;
res
}
#[inline]
pub fn $vec_name(&mut self, n: usize) -> Vec<$t> {
let mut res = Vec::with_capacity(n);
for _ in 0..n {
res.push(self.$name());
}
res
}
)*
}
};
}
impl_unsigned_input! {
u8, vec_u8, u8;
u16, vec_u16, u16;
u32, vec_u32, u32;
u64, vec_u64, u64;
u128, vec_u128, u128;
usize, vec_usize, usize;
}
impl_signed_input! {
i8, vec_i8, i8;
i16, vec_i16, i16;
i32, vec_i32, i32;
i64, vec_i64, i64;
i128, vec_i128, i128;
}
// Source: https://github.com/InverseAki/arcaki_library/blob/main/src/Basic/basic_output.rs
pub struct Output<W: std::io::Write = std::io::Stdout> {
writer: std::io::BufWriter<W>,
}
impl Output<std::io::Stdout> {
pub fn new() -> Self {
Self::from_writer(std::io::stdout())
}
pub fn with_capacity(capacity: usize) -> Self {
Self::with_writer_capacity(capacity, std::io::stdout())
}
}
impl<W: std::io::Write> Output<W> {
pub fn from_writer(writer: W) -> Self {
Self::with_writer_capacity(1 << 16, writer)
}
pub fn with_writer_capacity(capacity: usize, writer: W) -> Self {
Self {
writer: std::io::BufWriter::with_capacity(capacity, writer),
}
}
#[inline(always)]
pub fn bytes(&mut self, bytes: &[u8]) -> &mut Self {
std::io::Write::write_all(&mut self.writer, bytes).unwrap();
self
}
#[inline(always)]
pub fn string(&mut self, s: &str) -> &mut Self {
self.bytes(s.as_bytes())
}
#[inline(always)]
pub fn byte(&mut self, byte: u8) -> &mut Self {
self.bytes(&[byte])
}
#[inline(always)]
pub fn space(&mut self) -> &mut Self {
self.byte(b' ')
}
#[inline(always)]
pub fn newline(&mut self) -> &mut Self {
self.byte(b'\n')
}
pub fn flush(&mut self) -> std::io::Result<()> {
std::io::Write::flush(&mut self.writer)
}
pub fn into_inner(self) -> Result<W, std::io::IntoInnerError<std::io::BufWriter<W>>> {
self.writer.into_inner()
}
}
const OUTPUT_DIGIT_PAIRS: &[u8; 200] = b"00010203040506070809101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899";
macro_rules! impl_unsigned_output {
($($name:ident, $line:ident, $helper:ident, $t:ty, $digits:expr);* $(;)?) => {
impl<W: std::io::Write> Output<W> {
$(
#[inline(always)]
fn $helper<const LINE: bool>(&mut self, mut value: $t) -> &mut Self {
let mut buf = [0u8; $digits + 1];
let mut at = buf.len();
if LINE {
at -= 1;
buf[at] = b'\n';
}
while value >= 100 {
let pair = (value % 100) as usize * 2;
value /= 100;
at -= 2;
buf[at..at + 2].copy_from_slice(&OUTPUT_DIGIT_PAIRS[pair..pair + 2]);
}
if value >= 10 {
let pair = value as usize * 2;
at -= 2;
buf[at..at + 2].copy_from_slice(&OUTPUT_DIGIT_PAIRS[pair..pair + 2]);
} else {
at -= 1;
buf[at] = b'0' + value as u8;
}
self.bytes(&buf[at..])
}
#[inline(always)]
pub fn $name(&mut self, value: $t) -> &mut Self {
self.$helper::<false>(value)
}
#[inline(always)]
pub fn $line(&mut self, value: $t) -> &mut Self {
self.$helper::<true>(value)
}
)*
}
};
}
macro_rules! impl_signed_output {
($($name:ident, $line:ident, $helper:ident, $t:ty, $digits:expr);* $(;)?) => {
impl<W: std::io::Write> Output<W> {
$(
#[inline(always)]
fn $helper<const LINE: bool>(&mut self, value: $t) -> &mut Self {
let mut magnitude = value.unsigned_abs();
let mut buf = [0u8; $digits + 2];
let mut at = buf.len();
if LINE {
at -= 1;
buf[at] = b'\n';
}
while magnitude >= 100 {
let pair = (magnitude % 100) as usize * 2;
magnitude /= 100;
at -= 2;
buf[at..at + 2].copy_from_slice(&OUTPUT_DIGIT_PAIRS[pair..pair + 2]);
}
if magnitude >= 10 {
let pair = magnitude as usize * 2;
at -= 2;
buf[at..at + 2].copy_from_slice(&OUTPUT_DIGIT_PAIRS[pair..pair + 2]);
} else {
at -= 1;
buf[at] = b'0' + magnitude as u8;
}
if value < 0 {
at -= 1;
buf[at] = b'-';
}
self.bytes(&buf[at..])
}
#[inline(always)]
pub fn $name(&mut self, value: $t) -> &mut Self {
self.$helper::<false>(value)
}
#[inline(always)]
pub fn $line(&mut self, value: $t) -> &mut Self {
self.$helper::<true>(value)
}
)*
}
};
}
impl_unsigned_output! {
u8, u8_line, write_u8, u8, 3;
u16, u16_line, write_u16, u16, 5;
u32, u32_line, write_u32, u32, 10;
u64, u64_line, write_u64, u64, 20;
u128, u128_line, write_u128, u128, 39;
usize, usize_line, write_usize, usize, 20;
}
impl_signed_output! {
i8, i8_line, write_i8, i8, 3;
i16, i16_line, write_i16, i16, 5;
i32, i32_line, write_i32, i32, 10;
i64, i64_line, write_i64, i64, 20;
i128, i128_line, write_i128, i128, 39;
isize, isize_line, write_isize, isize, 20;
}
// Source: https://github.com/InverseAki/arcaki_library/blob/main/src/DataStructure/predecessor64.rs
#[derive(Clone, Debug)]
pub struct Predecessor64 {
mx: usize,
data: Vec<u64>,
offset: [usize; 11],
levels: usize,
}
impl Predecessor64 {
pub fn new(mx: usize) -> Self {
let (offset, levels, total) = Self::layout(mx.max(1).div_ceil(64));
Self {
mx: mx.max(1),
data: vec![0; total],
offset,
levels,
}
}
fn layout(mut len: usize) -> ([usize; 11], usize, usize) {
let mut offset = [0; 11];
let mut levels = 0;
let mut total = 0;
loop {
offset[levels] = total;
levels += 1;
total += len;
if len <= 1 {
break;
}
len = len.div_ceil(64);
}
(offset, levels, total)
}
pub fn from_vec_u64(mut base: Vec<u64>) -> Self {
if base.is_empty() {
return Self::new(1);
}
let mx = base.len().checked_mul(64).expect("universe size overflow");
let (offset, levels, total) = Self::layout(base.len());
base.reserve_exact(total - base.len());
base.resize(total, 0);
for i in 1..levels {
let (lower, upper) = base.split_at_mut(offset[i]);
let lower = &lower[offset[i - 1]..];
let mut chunks = lower.chunks_exact(64);
let mut words = upper.iter_mut();
for (chunk, word) in (&mut chunks).zip(&mut words) {
let mut bits = 0;
for j in 0..64 {
bits |= ((chunk[j] != 0) as u64) << j;
}
*word = bits;
}
if let Some(word) = words.next() {
let mut bits = 0;
for (j, &v) in chunks.remainder().iter().enumerate() {
bits |= ((v != 0) as u64) << j;
}
*word = bits;
}
}
Self {
mx,
data: base,
offset,
levels,
}
}
pub fn from_vec_usize(base: Vec<usize>) -> Self {
Self::from_vec_u64(base.into_iter().map(|v| v as u64).collect())
}
pub fn from_01_string(s: String) -> Self {
let mut base = Vec::with_capacity(s.len().div_ceil(64));
for chunk in s.as_bytes().chunks(64) {
let mut word = 0;
let mut groups = chunk.chunks_exact(8);
for (i, group) in (&mut groups).enumerate() {
let mut bytes = [0; 8];
for j in 0..8 {
bytes[j] = (group[j] == b'1') as u8;
}
let bits = u64::from_le_bytes(bytes).wrapping_mul(0x0102_0408_1020_4080) >> 56;
word |= bits << (i * 8);
}
let start = chunk.len() & !7;
for (j, &c) in groups.remainder().iter().enumerate() {
word |= ((c == b'1') as u64) << (start + j);
}
base.push(word);
}
Self::from_vec_u64(base)
}
#[inline(always)]
fn word(&self, index: usize) -> u64 {
// SAFETY: callers use layout indices; public positions are checked against mx.
unsafe { *self.data.get_unchecked(index) }
}
#[inline(always)]
fn word_mut(&mut self, index: usize) -> &mut u64 {
// SAFETY: checked leaf positions and nonempty/empty transitions stay within layout.
unsafe { self.data.get_unchecked_mut(index) }
}
#[inline(always)]
pub fn insert(&mut self, mut p: usize) {
assert!(p < self.mx);
let word = self.word_mut(p >> 6);
let old = *word;
*word |= 1 << (p & 63);
if old != 0 {
return;
}
for i in 1..self.levels {
p >>= 6;
let word = self.word_mut(self.offset[i] + (p >> 6));
let old = *word;
*word |= 1 << (p & 63);
if old != 0 {
return;
}
}
}
#[inline(always)]
pub fn remove(&mut self, mut p: usize) {
assert!(p < self.mx);
let word = self.word_mut(p >> 6);
let old = *word;
*word &= !(1 << (p & 63));
if *word != 0 || old == 0 {
return;
}
for i in 1..self.levels {
p >>= 6;
let word = self.word_mut(self.offset[i] + (p >> 6));
let old = *word;
*word &= !(1 << (p & 63));
if *word != 0 || old == 0 {
return;
}
}
}
#[inline(always)]
pub fn include(&self, p: usize) -> bool {
if p >= self.mx {
return false;
}
self.word(p >> 6) & (1 << (p & 63)) != 0
}
#[inline(always)]
pub fn is_empty(&self) -> bool {
self.word(self.offset[self.levels - 1]) == 0
}
#[inline(always)]
pub fn min(&self) -> usize {
self.extreme::<true>()
}
#[inline(always)]
pub fn max(&self) -> usize {
self.extreme::<false>()
}
#[inline(always)]
fn extreme<const MIN: bool>(&self) -> usize {
let leaf_index = if MIN { 0 } else { (self.mx - 1) >> 6 };
let leaf = self.word(leaf_index);
if leaf != 0 {
let bit = if MIN {
leaf.trailing_zeros() as usize
} else {
63 - leaf.leading_zeros() as usize
};
return (leaf_index << 6) | bit;
}
let mut word = self.word(self.offset[self.levels - 1]);
if word == 0 {
return !0;
}
let mut p = if MIN {
word.trailing_zeros() as usize
} else {
63 - word.leading_zeros() as usize
};
for i in (0..self.levels - 1).rev() {
word = self.word(self.offset[i] + p);
let bit = if MIN {
word.trailing_zeros() as usize
} else {
63 - word.leading_zeros() as usize
};
p = (p << 6) | bit;
}
p
}
#[inline(always)]
pub fn prev(&self, p: usize) -> usize {
self.search_prev::<false>(p)
}
#[inline(always)]
pub fn inprev(&self, p: usize) -> usize {
self.search_prev::<true>(p)
}
#[inline(always)]
pub fn next(&self, p: usize) -> usize {
self.search_next::<false>(p)
}
#[inline(always)]
pub fn innext(&self, p: usize) -> usize {
self.search_next::<true>(p)
}
#[inline(always)]
fn search_prev<const INCLUSIVE: bool>(&self, mut p: usize) -> usize {
if p >= self.mx {
return self.max();
}
let mask = if INCLUSIVE {
u64::MAX >> (63 - (p & 63))
} else {
(1u64 << (p & 63)) - 1
};
let word = self.word(p >> 6) & mask;
if word != 0 {
return (p & !63) | (63 - word.leading_zeros() as usize);
}
for i in 1..self.levels {
p >>= 6;
let word = self.word(self.offset[i] + (p >> 6)) & ((1u64 << (p & 63)) - 1);
if word != 0 {
let mut res = (p & !63) | (63 - word.leading_zeros() as usize);
for j in (0..i).rev() {
res = (res << 6)
| (63 - self.word(self.offset[j] + res).leading_zeros() as usize);
}
return res;
}
}
!0
}
#[inline(always)]
fn search_next<const INCLUSIVE: bool>(&self, mut p: usize) -> usize {
if p >= self.mx {
return !0;
}
let mask = if INCLUSIVE {
u64::MAX << (p & 63)
} else {
(u64::MAX << (p & 63)) << 1
};
let word = self.word(p >> 6) & mask;
if word != 0 {
return (p & !63) | (word.trailing_zeros() as usize);
}
for i in 1..self.levels {
p >>= 6;
let word = self.word(self.offset[i] + (p >> 6)) & ((u64::MAX << (p & 63)) << 1);
if word != 0 {
let mut res = (p & !63) | (word.trailing_zeros() as usize);
for j in (0..i).rev() {
res = (res << 6) | (self.word(self.offset[j] + res).trailing_zeros() as usize);
}
return res;
}
}
!0
}
}
// Source: https://github.com/InverseAki/arcaki_library/blob/main/src/OfflineQuery/mo.rs
pub trait MoState {
type Data;
type Query;
type Ans;
fn add_left(&mut self, idx: usize, data: &Self::Data);
fn add_right(&mut self, idx: usize, data: &Self::Data);
fn sub_left(&mut self, idx: usize, data: &Self::Data);
fn sub_right(&mut self, idx: usize, data: &Self::Data);
fn ans(&mut self, query_id: usize, q_data: &Self::Query) -> Self::Ans;
}
pub trait SymMoState {
type Data;
type Query;
type Ans;
fn add(&mut self, idx: usize, data: &Self::Data);
fn sub(&mut self, idx: usize, data: &Self::Data);
fn ans(&mut self, query_id: usize, q_data: &Self::Query) -> Self::Ans;
}
impl<M: SymMoState> MoState for M {
type Data = <M as SymMoState>::Data;
type Query = <M as SymMoState>::Query;
type Ans = <M as SymMoState>::Ans;
#[inline]
fn add_left(&mut self, idx: usize, data: &Self::Data) {
self.add(idx, data);
}
#[inline]
fn add_right(&mut self, idx: usize, data: &Self::Data) {
self.add(idx, data);
}
#[inline]
fn sub_left(&mut self, idx: usize, data: &Self::Data) {
self.sub(idx, data);
}
#[inline]
fn sub_right(&mut self, idx: usize, data: &Self::Data) {
self.sub(idx, data);
}
#[inline]
fn ans(&mut self, query_id: usize, q_data: &Self::Query) -> Self::Ans {
SymMoState::ans(self, query_id, q_data)
}
}
pub struct MoQuery {
pub l: usize,
pub r: usize,
pub id: usize,
}
pub struct MoSolver<M: MoState> {
data: Vec<M::Data>,
query: Vec<(MoQuery, M::Query)>,
}
impl<M> MoSolver<M>
where
M: MoState,
{
pub fn new(data: Vec<M::Data>) -> Self {
MoSolver {
data,
query: Vec::new(),
}
}
pub fn add_query(&mut self, l: usize, r: usize, qd: M::Query) {
self.query.push((
MoQuery {
l,
r,
id: self.query.len(),
},
qd,
));
}
#[inline]
fn hilbert_order(x: u32, y: u32, pow: u32, mut rot: u32) -> u64 {
let mut ord = 0;
let mut flip = 0;
for p in (0..pow).rev() {
let rx = (x >> p) & 1;
let ry = (y >> p) & 1;
let seg = ((ry * 3 ^ rx) + rot) & 3;
rot = (rot + [3, 0, 0, 1][seg as usize]) & 3;
ord = (ord << 2) | ((seg ^ flip) as u64);
if seg == 0 || seg == 3 {
flip ^= 3;
}
}
ord
}
fn get_ord(&self) -> Vec<usize> {
let mx = self
.query
.iter()
.map(|(q, _)| q.l.max(q.r))
.max()
.unwrap_or(0);
let pow = if mx == 0 {
0
} else {
(usize::BITS - mx.leading_zeros()) as u32
};
let mut ord = (0..self.query.len())
.map(|i| {
let q = &self.query[i].0;
(Self::hilbert_order(q.l as u32, q.r as u32, pow, 0), i)
})
.collect::<Vec<_>>();
ord.sort_unstable_by_key(|&(key, _)| key);
ord.into_iter().map(|(_, i)| i).collect()
}
pub fn solve(&mut self, state: &mut M) -> Vec<M::Ans> {
let q = self.query.len();
let mut res: Vec<Option<M::Ans>> = (0..q).map(|_| None).collect();
let ord = self.get_ord();
let mut l = 0;
let mut r = 0;
for qi in ord {
let (query, qd) = &self.query[qi];
if l > query.l {
for (offset, value) in self.data[query.l..l].iter().enumerate().rev() {
state.add_left(query.l + offset, value);
}
l = query.l;
}
if r < query.r {
for (offset, value) in self.data[r..query.r].iter().enumerate() {
state.add_right(r + offset, value);
}
r = query.r;
}
if l < query.l {
for (offset, value) in self.data[l..query.l].iter().enumerate() {
state.sub_left(l + offset, value);
}
l = query.l;
}
if r > query.r {
for (offset, value) in self.data[query.r..r].iter().enumerate().rev() {
state.sub_right(query.r + offset, value);
}
r = query.r;
}
res[query.id] = Some(state.ans(query.id, qd));
}
res.into_iter().map(|x| x.unwrap()).collect()
}
}
// Source: https://github.com/InverseAki/arcaki_library/blob/main/src/Basic/integer_sort.rs
mod integer_sort_private {
pub trait Sealed {}
}
pub trait IntegerSortValue: Copy + Ord + integer_sort_private::Sealed {
fn sort_key(self) -> u64;
fn from_sort_key(key: u64) -> Self;
}
macro_rules! integer_sort_unsigned {
($($t:ty),*) => {$(
impl integer_sort_private::Sealed for $t {}
impl IntegerSortValue for $t {
#[inline]
fn sort_key(self) -> u64 { self as u64 }
#[inline]
fn from_sort_key(key: u64) -> Self { key as Self }
}
)*};
}
integer_sort_unsigned!(u32, u64, usize);
impl integer_sort_private::Sealed for i64 {}
impl IntegerSortValue for i64 {
#[inline]
fn sort_key(self) -> u64 {
(self as u64) ^ (1 << 63)
}
#[inline]
fn from_sort_key(key: u64) -> Self {
(key ^ (1 << 63)) as Self
}
}
pub fn integer_sort<T: IntegerSortValue>(values: &mut [T]) {
integer_sort_with_buffer(values, &mut Vec::new());
}
pub fn integer_sort_with_buffer<T: IntegerSortValue>(values: &mut [T], buffer: &mut Vec<T>) {
let n = values.len();
if n <= 128 {
values.sort_unstable();
return;
}
if values.is_sorted() {
return;
}
if values.windows(2).all(|w| w[0] >= w[1]) {
values.reverse();
return;
}
let first = values[0].sort_key();
let mut low = first;
let mut high = first;
let mut varying = 0;
for &value in values.iter() {
let key = value.sort_key();
low = low.min(key);
high = high.max(key);
varying |= key ^ first;
}
let offset = varying.trailing_zeros();
let range = (high - low) >> offset;
if range <= 65535 && range < (n / 8) as u64 {
let mut counts = vec![0usize; range as usize + 1];
for &value in values.iter() {
counts[((value.sort_key() - low) >> offset) as usize] += 1;
}
let mut pos = 0;
for (i, count) in counts.into_iter().enumerate() {
if count != 0 {
values[pos..pos + count].fill(T::from_sort_key(low + ((i as u64) << offset)));
pos += count;
}
}
return;
}
let mut width = 64 - varying.leading_zeros() - offset;
let mut base = 0;
let normalized_width = 64 - range.leading_zeros();
if normalized_width < width {
width = normalized_width;
base = low;
varying = (u64::MAX >> range.leading_zeros()) << offset;
}
if (n < 1024 && width > 16) || (n < 8192 && width > 32) {
values.sort_unstable();
return;
}
buffer.resize(n, values[0]);
if width == 9 {
integer_sort_radix::<T, 512>(values, &mut buffer[..n], varying, base);
} else if width == 10 {
integer_sort_radix::<T, 1024>(values, &mut buffer[..n], varying, base);
} else if width == 11 {
integer_sort_radix::<T, 2048>(values, &mut buffer[..n], varying, base);
} else if n < 2048 || width <= 16 {
integer_sort_radix::<T, 256>(values, &mut buffer[..n], varying, base);
} else {
integer_sort_radix::<T, 2048>(values, &mut buffer[..n], varying, base);
}
}
fn integer_sort_radix<T: IntegerSortValue, const BINS: usize>(
values: &mut [T],
buffer: &mut [T],
mut varying: u64,
base: u64,
) {
let bits = BINS.trailing_zeros();
let mask = BINS - 1;
let mut shift = varying.trailing_zeros();
varying >>= shift;
let mut source = values;
let mut target = buffer;
let mut in_buffer = false;
while varying != 0 {
if varying & mask as u64 != 0 {
if source.is_sorted() {
break;
}
let mut counts = [0usize; BINS];
for &value in source.iter() {
counts[((value.sort_key() - base) >> shift) as usize & mask] += 1;
}
let mut sum = 0;
for count in counts.iter_mut() {
let len = *count;
*count = sum;
sum += len;
}
for &value in source.iter() {
let pos = &mut counts[((value.sort_key() - base) >> shift) as usize & mask];
target[*pos] = value;
*pos += 1;
}
std::mem::swap(&mut source, &mut target);
in_buffer = !in_buffer;
}
varying >>= bits;
shift += bits;
}
if in_buffer {
target.copy_from_slice(source);
}
}
struct M{
c1: Vec<i32>,
c2: Vec<i32>,
b: Vec<u32>,
seg1: Predecessor64,
seg2: Predecessor64,
}
#[inline(always)]
fn inc(p: usize, c2: &mut [i32], seg: &mut Predecessor64){
if c2[p]==0 {
seg.insert(p);
}
c2[p] += 1;
}
#[inline(always)]
fn dec(p: usize, c2: &mut [i32], seg: &mut Predecessor64){
c2[p] -= 1;
if c2[p]==0 {
seg.remove(p);
}
}
impl SymMoState for M{
type Data = usize;
type Query = (usize, bool);
type Ans = usize;
fn add(&mut self, _idx: usize, &p: &Self::Data) {
let bp = self.b[p]as usize;
if self.c1[p]==0 {
let l = self.seg1.prev(p);
let r = self.seg1.next(p);
if l==!0 {
if r!=!0 {
inc(self.b[r]as usize-bp, &mut self.c2, &mut self.seg2);
}
} else if r==!0 {
if l!=!0 {
inc(bp-self.b[l]as usize, &mut self.c2, &mut self.seg2);
}
} else {
dec((self.b[r]-self.b[l])as usize, &mut self.c2, &mut self.seg2);
inc(self.b[r]as usize-bp, &mut self.c2, &mut self.seg2);
inc(bp-self.b[l]as usize, &mut self.c2, &mut self.seg2);
}
self.seg1.insert(p);
} else {
inc(0, &mut self.c2, &mut self.seg2);
}
self.c1[p] += 1;
}
fn sub(&mut self, _idx: usize, &p: &Self::Data) {
let bp = self.b[p]as usize;
self.c1[p]-=1;
if self.c1[p]==0 {
let l = self.seg1.prev(p);
let r = self.seg1.next(p);
if l==!0 {
if r!=!0 {
dec(self.b[r]as usize-bp, &mut self.c2, &mut self.seg2);
}
} else if r==!0 {
if l!=!0 {
dec(bp-self.b[l]as usize, &mut self.c2, &mut self.seg2);
}
} else {
inc((self.b[r]-self.b[l])as usize, &mut self.c2, &mut self.seg2);
dec(self.b[r]as usize-bp, &mut self.c2, &mut self.seg2);
dec(bp-self.b[l]as usize, &mut self.c2, &mut self.seg2);
}
self.seg1.remove(p);
} else {
dec(0, &mut self.c2, &mut self.seg2);
}
}
fn ans(&mut self, _query_id: usize, &q_data: &Self::Query) -> Self::Ans {
let (x, f) = q_data;
if f {
self.seg2.inprev(x)
} else {
self.seg2.innext(x)
}
}
}
#[allow(unused)]
type MI = StaticModInt<Mod998244353>;
const MULTI: bool = false;
//#[fastout]
fn solve(){
let mut ip = Input::new();
let mut o = Output::new();
let n = ip.usize();
let q = ip.usize();
let a = (0..n).map(|_| ip.u32()).collect::<Vec<_>>();
let mut z = a.clone();
integer_sort(&mut z);
let mut map = FxMap::default();
for (i, &v) in z.iter().enumerate(){
map.insert(v, i);
}
let b = a.into_iter().map(|x| map[&x]).collect::<Vec<_>>();
let mut mo = MoSolver::new(b);
for _ in 0..q {
let (l,r)=(ip.usize1(),ip.usize());
let (x, c) = (ip.usize(), ip.byte()==b'L');
mo.add_query(l, r, (x, c));
}
let m = z.len();
for x in mo.solve(&mut M{b:z.clone(), c1: vec![0;m], c2: vec![0;10000000],seg1: Predecessor64::new(m), seg2: Predecessor64::new(10000000)}){
o.i32_line(x as i32);
}
}
fn main() {
if MULTI{
input!{
t: usize,
}
for _ in 0..t{
solve();
}
} else {
solve();
}
}