#1190820 (Rust) No.877 Range ReLU Query

• 問題: No.877 Range ReLU Query
• ユーザー: 👑 ArcAki
• 提出日時: 2026-09-30 15:09:13
• 言語: Rust (1.99.0 + proconio + num + itertools + ACL)
• 結果: AC
• 実行時間: 234 ms / 2,000 ms
• コード長: 18,128 bytes
• コンパイル時間: 1,639 ms
• コンパイル使用メモリ: 213,372 KB
• 実行使用メモリ: 21,268 KB
• 最終ジャッジ日時: 2026-09-30 15:09:21
• 合計ジャッジ時間: 7,087 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 20

コンパイルメッセージ

warning: method `rank0_range` is never used
   --> src/main.rs:282:8
    |
205 | impl BitVector {
    | -------------- method in this implementation
...
282 |     fn rank0_range(&self, l: usize, r: usize) -> usize {
    |        ^^^^^^^^^^^
    |
    = note: `#[warn(dead_code)]` (part of `#[warn(unused)]`) on by default

ソースコード

#[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 + Copy {fn chmax(&mut self, rhs: Self) {if *self < rhs { *self = rhs; }}}
impl<T: PartialOrd + Copy> Chmax for T {}
pub trait Chmin: PartialOrd + Copy {fn chmin(&mut self, rhs: Self) {if *self > rhs { *self = rhs; }}}
impl<T: PartialOrd + Copy> Chmin for T {}
#[allow(unused)]
use proconio::{*, marker::*};
#[allow(unused)]
use fxhash::FxMap;
#[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)];

#[derive(Clone, Debug)]
struct BitVector {
    n: usize,
    bits: Vec<u64>,
    acc: Vec<usize>,
}
 
impl BitVector {
    #[inline]
    fn blocks(n: usize) -> usize {
        (n + 63) >> 6
    }
 
    #[inline]
    fn index(i: usize) -> (usize, usize) {
        (i >> 6, i & 63)
    }
 
    fn new(n: usize) -> Self {
        let m = Self::blocks(n);
        Self {
            n,
            bits: vec![0; m],
            acc: vec![0; m + 1],
        }
    }
 
    #[inline]
    fn set(&mut self, i: usize) {
        let (b, off) = Self::index(i);
        self.bits[b] |= 1u64 << off;
    }
 
    fn build(&mut self) {
        let m = self.bits.len();
        self.acc[0] = 0;
 
        for i in 0..m {
            let valid = if (i + 1) << 6 <= self.n {
                64
            } else {
                self.n.saturating_sub(i << 6)
            };
 
            let mask = if valid == 64 {
                !0u64
            } else if valid == 0 {
                0
            } else {
                (1u64 << valid) - 1
            };
 
            self.acc[i + 1] =
                self.acc[i] + (self.bits[i] & mask).count_ones() as usize;
        }
    }
 
    #[inline]
    fn access(&self, i: usize) -> bool {
        let (b, off) = Self::index(i);
        ((self.bits[b] >> off) & 1) != 0
    }
 
    /// [0, k) にある 1 の個数
    #[inline]
    fn rank1(&self, k: usize) -> usize {
        let k = k.min(self.n);
        let (b, off) = Self::index(k);
 
        if off == 0 {
            self.acc[b]
        } else {
            self.acc[b]
                + (self.bits[b] & ((1u64 << off) - 1)).count_ones() as usize
        }
    }
 
    #[inline]
    fn rank0(&self, k: usize) -> usize {
        let k = k.min(self.n);
        k - self.rank1(k)
    }
 
    #[inline]
    fn rank0_range(&self, l: usize, r: usize) -> usize {
        self.rank0(r) - self.rank0(l)
    }
}
 
 
#[derive(Clone, Debug)]
pub struct WaveletMatrix {
    n: usize,
    max_log: usize,
    mids: Vec<usize>,
    bitvecs: Vec<BitVector>,
    zero_sums: Vec<Vec<u64>>,
    original_sum: Vec<u64>,
}
 
impl WaveletMatrix {
    pub fn new(a: &[usize]) -> Self {
        let n = a.len();
        let max_val = a.iter().copied().max().unwrap_or(0);
        let max_log = if n == 0 || max_val == 0 {
            1
        } else {
            (usize::BITS - max_val.leading_zeros()) as usize
        };
        let mut original_sum = vec![0u64; n + 1];
        for i in 0..n {
            original_sum[i + 1] = original_sum[i] + a[i] as u64;
        }
        let mut cur = a.to_vec();
        let mut bitvecs = Vec::with_capacity(max_log);
        let mut mids = Vec::with_capacity(max_log);
        let mut zero_sums = Vec::with_capacity(max_log);
        for level_rev in 0..max_log {
            let level = max_log - 1 - level_rev;
            let mut bv = BitVector::new(n);
            let mut zero = Vec::with_capacity(n);
            let mut one = Vec::with_capacity(n);
            for (i, &x) in cur.iter().enumerate() {
                if ((x >> level) & 1) == 1 {
                    bv.set(i);
                    one.push(x);
                } else {
                    zero.push(x);
                }
            }
            bv.build();
            let mid = zero.len();
            mids.push(mid);
            let mut sum = Vec::with_capacity(mid + 1);
            sum.push(0);
            for &x in &zero {
                let nxt = *sum.last().unwrap() + x as u64;
                sum.push(nxt);
            }
            zero_sums.push(sum);
            zero.extend(one);
            cur = zero;
            bitvecs.push(bv);
        }
 
        Self {
            n,
            max_log,
            mids,
            bitvecs,
            zero_sums,
            original_sum,
        }
    }
 
    #[inline]
    pub fn len(&self) -> usize {
        self.n
    }
 
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.n == 0
    }
 
    pub fn access(&self, mut i: usize) -> usize {
        assert!(i < self.n);
 
        let mut x = 0usize;
 
        for d in 0..self.max_log {
            let bit = self.bitvecs[d].access(i);
 
            if bit {
                x |= 1usize << (self.max_log - 1 - d);
 
                i = self.mids[d]
                    + self.bitvecs[d].rank1(i);
            } else {
                i = self.bitvecs[d].rank0(i);
            }
        }
 
        x
    }
 
    pub fn rank(&self, x: usize, mut r: usize) -> usize {
        r = r.min(self.n);
 
        if self.max_log < usize::BITS as usize
            && x >= (1usize << self.max_log)
        {
            return 0;
        }
 
        let mut l = 0usize;
 
        for d in 0..self.max_log {
            let bit =
                (x >> (self.max_log - 1 - d)) & 1;
 
            if bit == 0 {
                l = self.bitvecs[d].rank0(l);
                r = self.bitvecs[d].rank0(r);
            } else {
                l = self.mids[d]
                    + self.bitvecs[d].rank1(l);
 
                r = self.mids[d]
                    + self.bitvecs[d].rank1(r);
            }
        }
 
        r - l
    }
 
    /// [l, r) にある x の個数
    pub fn rank_range(
        &self,
        x: usize,
        l: usize,
        r: usize,
    ) -> usize {
        assert!(l <= r && r <= self.n);
 
        self.rank(x, r) - self.rank(x, l)
    }
 
    pub fn kth_smallest(
        &self,
        mut l: usize,
        mut r: usize,
        mut k: usize,
    ) -> usize {
        assert!(l <= r && r <= self.n);
        assert!(k < r - l);
 
        let mut ans = 0usize;
 
        for d in 0..self.max_log {
            let l1 = self.bitvecs[d].rank1(l);
            let r1 = self.bitvecs[d].rank1(r);
 
            let l0 = l - l1;
            let r0 = r - r1;
 
            let zeros = r0 - l0;
 
            if k < zeros {
                l = l0;
                r = r0;
            } else {
                ans |=
                    1usize << (self.max_log - 1 - d);
 
                k -= zeros;
 
                l = self.mids[d] + l1;
                r = self.mids[d] + r1;
            }
        }
 
        ans
    }

    pub fn kth_largest(
        &self,l: usize,r: usize,k: usize,) -> usize {
        assert!(k < r - l);
        self.kth_smallest(l,r,r - l - 1 - k)
    }

    pub fn quantile(&self,l: usize,r: usize,k: usize,) -> usize {
        self.kth_smallest(l, r, k)
    }

    pub fn range_freq(&self,mut l: usize,mut r: usize,upper: usize) -> usize {
        assert!(l <= r && r <= self.n);
        if l >= r || upper == 0 {return 0;}
        if self.max_log < usize::BITS as usize&& upper >= (1usize << self.max_log){return r - l;}
        let mut cnt = 0usize;
        for d in 0..self.max_log {
            let bit = (upper >> (self.max_log - 1 - d)) & 1;
            let l1 = self.bitvecs[d].rank1(l);
            let r1 = self.bitvecs[d].rank1(r);
            let l0 = l - l1;
            let r0 = r - r1;

            if bit == 1 {
                cnt += r0 - l0;
                l = self.mids[d] + l1;
                r = self.mids[d] + r1;
            } else {
                l = l0;
                r = r0;
            }
        }

        cnt
    }

    /// [l, r) にある
    /// lower <= x < upper
    /// を満たす値の個数
    pub fn range_freq_between(&self,l: usize,r: usize,lower: usize,upper: usize) -> usize {
        if lower >= upper || l >= r {
            0
        } else {
            self.range_freq(l, r, upper)
                - self.range_freq(l, r, lower)
        }
    }

    /// [l, r) にある upper 未満の値の総和
    ///
    /// Σ a[i]  (l <= i < r, a[i] < upper)
    pub fn range_sum(&self,mut l: usize,mut r: usize,upper: usize) -> u64 {
        assert!(l <= r && r <= self.n);
        if l >= r || upper == 0 {
            return 0;
        }

        if self.max_log < usize::BITS as usize && upper >= (1usize << self.max_log)
        {return self.original_sum[r]- self.original_sum[l];}
        let mut ans = 0u64;
        for d in 0..self.max_log {
            let bit =(upper >> (self.max_log - 1 - d)) & 1;
            let l1 = self.bitvecs[d].rank1(l);
            let r1 = self.bitvecs[d].rank1(r);
            let l0 = l - l1;
            let r0 = r - r1;
            if bit == 1 {
                ans += self.zero_sums[d][r0]- self.zero_sums[d][l0];
                l = self.mids[d] + l1;
                r = self.mids[d] + r1;
            } else {
                l = l0;
                r = r0;
            }
        }

        ans
    }

    pub fn range_sum_between(
        &self,
        l: usize,
        r: usize,
        lower: usize,
        upper: usize,
    ) -> u64 {
        if lower >= upper || l >= r {
            0
        } else {
            self.range_sum(l, r, upper)
                - self.range_sum(l, r, lower)
        }
    }

    pub fn range_sum_leq(&self,l: usize,r: usize,x: usize) -> u64 {
        assert!(l <= r && r <= self.n);
        if x == usize::MAX {
            self.original_sum[r]
                - self.original_sum[l]
        } else {
            self.range_sum(l, r, x + 1)
        }
    }

    pub fn prev_value(&self,l: usize,r: usize,upper: usize,) -> Option<usize> {
        let cnt = self.range_freq(l, r, upper);
        if cnt == 0 {
            None
        } else {
            Some(self.kth_smallest(l,r,cnt - 1,))
        }
    }

    pub fn next_value(&self,l: usize,r: usize,lower: usize,) -> Option<usize> {
        let cnt = self.range_freq(l, r, lower);
        if cnt == r - l {
            None
        } else {
            Some(self.kth_smallest(l,r,cnt,))
        }
    }
}

#[allow(unused)]
type MI = StaticModInt<Mod998244353>;
const MULTI: bool = false;
//#[fastout]
fn solve(){
    input!{
        n: usize, q: usize,
        a: [usize; n],
        query: [(u8, Usize1, usize, usize); q],
    }
    let wm = WaveletMatrix::new(&a);
    for &(_, l, r, x) in &query{
        println!("{}", wm.range_sum_between(l, r, x, 1<<30)as usize-wm.range_freq_between(l, r, x, 1<<30)*x);
    }
}

fn main() {
    if MULTI{
        input!{
            t: usize,
        }
        for _ in 0..t{
            solve();
        }
    } else {
        solve();
    }
}