結果

問題 No.1625 三角形の質問
ユーザー CoCo_Japan_panCoCo_Japan_pan
提出日時 2024-12-02 13:51:09
言語 Rust
(1.77.0 + proconio)
結果
RE  
実行時間 -
コード長 21,185 bytes
コンパイル時間 18,412 ms
コンパイル使用メモリ 379,260 KB
実行使用メモリ 104,980 KB
最終ジャッジ日時 2024-12-02 13:51:46
合計ジャッジ時間 31,484 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 101 ms
7,988 KB
testcase_02 AC 404 ms
30,720 KB
testcase_03 AC 157 ms
51,956 KB
testcase_04 AC 181 ms
28,488 KB
testcase_05 AC 354 ms
56,168 KB
testcase_06 AC 923 ms
104,848 KB
testcase_07 AC 757 ms
104,852 KB
testcase_08 AC 669 ms
104,844 KB
testcase_09 AC 749 ms
104,872 KB
testcase_10 AC 673 ms
104,888 KB
testcase_11 AC 740 ms
104,744 KB
testcase_12 AC 724 ms
104,844 KB
testcase_13 AC 665 ms
104,980 KB
testcase_14 AC 724 ms
104,976 KB
testcase_15 AC 740 ms
104,856 KB
testcase_16 AC 106 ms
32,400 KB
testcase_17 AC 351 ms
99,784 KB
testcase_18 RE -
testcase_19 AC 412 ms
104,908 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// verification-helper: PROBLEM https://yukicoder.me/problems/no/1625

pub use __cargo_equip::prelude::*;

use algebra::{Commutative, Monoid};
use proconio::{fastout, input};
use wavelet_matrix_segtree::WMSegWrapper;

#[derive(Clone, Copy, Debug)]
enum Query {
    Add(i64, i64, i64),
    Get(i64, i64),
}

#[derive(Clone, Copy, Debug)]
enum MaxMonoid {}
impl Monoid for MaxMonoid {
    type Target = i64;
    fn binary_operation(a: &Self::Target, b: &Self::Target) -> Self::Target {
        *a.max(b)
    }
    fn id_element() -> Self::Target {
        -1
    }
}
impl Commutative for MaxMonoid {}

#[fastout]
fn main() {
    input! {
        n: usize,
        q: usize,
        a_b_c_d_e_f: [(i64, i64, i64, i64, i64, i64); n],
    }
    let mut queries = a_b_c_d_e_f.into_iter().map(l_r_area).collect::<Vec<_>>();
    for _ in 0..q {
        input! {
            query_type: u8,
        }
        if query_type == 1 {
            input! {
                add: (i64, i64, i64, i64, i64, i64)
            }
            queries.push(l_r_area(add));
        } else {
            input! {
                l: i64,
                r: i64,
            }
            queries.push(Query::Get(l, r));
        }
    }
    let queries = queries;
    let update_points = queries
        .iter()
        .filter_map(|query| match query {
            Query::Add(x, y, _) => Some((*x, *y)),
            _ => None,
        })
        .collect::<Vec<_>>();
    let init_weight = queries
        .iter()
        .take(n)
        .map(|query| match query {
            Query::Add(x, y, area) => (*x, *y, *area),
            _ => unreachable!(),
        })
        .collect::<Vec<_>>();
    let mut wm_seg = WMSegWrapper::<MaxMonoid, _>::from_weight(update_points, init_weight);
    for query in queries.into_iter().skip(n) {
        match query {
            Query::Add(x, y, area) => {
                let old_val = wm_seg.get(x, y);
                wm_seg.set(x, y, old_val.max(area));
            }
            Query::Get(l, r) => {
                let ans = wm_seg.rect_sum_monoid(l..=r, l..=r);
                println!("{}", ans);
            }
        }
    }
}

fn l_r_area(x: (i64, i64, i64, i64, i64, i64)) -> Query {
    let x_list = [x.0, x.2, x.4];
    let left = *x_list.iter().min().unwrap();
    let right = *x_list.iter().max().unwrap();
    let y_list = [x.1, x.3, x.5];
    let x_list_parralel = x_list
        .into_iter()
        .map(|x| x - x_list[0])
        .collect::<Vec<_>>();
    let y_list_parralel = y_list
        .into_iter()
        .map(|y| y - y_list[0])
        .collect::<Vec<_>>();
    let area =
        (x_list_parralel[1] * y_list_parralel[2] - x_list_parralel[2] * y_list_parralel[1]).abs();
    Query::Add(left, right, area)
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `algebra 0.1.0 (path+██████████████████████████████████████████████████████)`                                       published in https://github.com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::algebra`
///  - `bitdict 0.1.0 (path+██████████████████████████████████████████████████████████████)`                               published in https://github.com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__bitdict_0_1_0`
///  - `internal_bits 0.1.0 (path+██████████████████████████████████████████████████████████████████████)`                 published in **missing**                                         licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__internal_bits_0_1_0`
///  - `internal_type_traits 0.1.0 (path+█████████████████████████████████████████████████████████████████████████████)`   published in **missing**                                         licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__internal_type_traits_0_1_0`
///  - `segtree 0.1.0 (path+█████████████████████████████████████████████████████████████████████)`                        published in https://github.com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__segtree_0_1_0`
///  - `wavelet_matrix_segtree 0.1.0 (path+█████████████████████████████████████████████████████████████████████████████)` published in https://github.com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::wavelet_matrix_segtree`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod algebra {use std::fmt::Debug;pub trait Commutative{}pub trait Action:Debug+Clone{type Target:Clone;fn id_action()->Self;fn composition(&mut self,rhs:&Self);fn apply(&self,target:&mut Self::Target);}pub trait Monoid{type Target:Debug+Clone+Eq;fn id_element()->Self::Target;fn binary_operation(a:&Self::Target,b:&Self::Target)->Self::Target;}pub trait ActionMonoid{type M:Monoid;type A:Action<Target=<Self::M as Monoid>::Target>;}pub trait IdempotentMonoid:Monoid{}pub trait Group:Monoid{fn inverse(a:&Self::Target)->Self::Target;}pub trait Semiring:Debug+Clone+Eq{type Target:Debug+Clone+Eq;fn zero()->Self::Target;fn one()->Self::Target;fn add_assign(a:&mut Self::Target,b:&Self::Target);fn mul(a:&Self::Target,b:&Self::Target)->Self::Target;}}
        pub mod __bitdict_0_1_0 {#[derive(Debug,Clone,Copy)]struct Block{bit:u64,cum_sum_popcnt:u32,}#[derive(Debug,Clone)]pub struct BitDict{len:usize,blocks:Vec<Block>,all_popcnt:usize,one_select:Vec<u32>,zero_select:Vec<u32>,}impl From<&[bool]>for BitDict{fn from(bitvec:&[bool])->Self{let len=bitvec.len();let mut ret=Self::new(len);for(i,&b)in bitvec.iter().enumerate(){if b{ret.set(i);}}ret.build();ret}}impl BitDict{pub fn new(len:usize)->Self{Self{len,blocks:vec![Block{bit:0,cum_sum_popcnt:0};(len>>6)+1],all_popcnt:0,one_select:Vec::new(),zero_select:Vec::new(),}}pub fn rank1_all(&self)->usize{self.all_popcnt}pub fn rank0_all(&self)->usize{self.len-self.all_popcnt}pub fn access(&self,i:usize)->bool{debug_assert!(i<self.len);(self.blocks[i>>6].bit>>(i&63))&1==1}pub fn set(&mut self,i:usize){debug_assert!(i<self.len);self.blocks[i>>6].bit|=1<<(i&63);}pub fn build(&mut self){let all_popcnt=self.blocks.iter().map(|b|b.bit.count_ones()).sum::<u32>()as usize;let mut popcnt=0;let one_num=(all_popcnt>>6)+1;let zero_num=((self.len-all_popcnt)>>6)+1;let mut one_select=Vec::with_capacity(one_num);let mut zero_select=Vec::with_capacity(zero_num);for(i,b)in self.blocks.iter_mut().enumerate(){if popcnt as usize>=one_select.len()<<6{one_select.push(i as u32);}if(i<<6)-popcnt as usize>=zero_select.len()<<6{zero_select.push(i as u32);}b.cum_sum_popcnt=popcnt;popcnt+=b.bit.count_ones();}assert_eq!(popcnt as usize,all_popcnt);self.all_popcnt=all_popcnt;self.one_select=one_select;self.zero_select=zero_select;}pub fn rank_1(&self,i:usize)->usize{debug_assert!(i<=self.len);let Block{bit:block,cum_sum_popcnt,}=self.blocks[i>>6];let mask=(1<<(i&63))-1;let popcnt=(block&mask).count_ones();(cum_sum_popcnt+popcnt)as usize}pub fn rank_0(&self,i:usize)->usize{i-self.rank_1(i)}pub fn select_1(&self,i:usize)->Option<usize>{if i>=self.all_popcnt{return None;}let mut ok=if let Some(&ok)=self.one_select.get(i>>6){ok.saturating_sub(1)as usize}else{self.blocks.len().saturating_sub(1)};let mut ng=if let Some(&ng)=self.one_select.get((i>>6)+1){ng as usize}else{self.blocks.len()};let i=i as u32;while ng-ok>1{let mid=(ok+ng)>>1;if self.blocks[mid].cum_sum_popcnt<=i{ok=mid;}else{ng=mid;}}let rem=i-self.blocks[ok].cum_sum_popcnt;let offset=select1_u64(self.blocks[ok].bit,rem as usize);Some((ok<<6)+offset as usize)}pub fn select_0(&self,i:usize)->Option<usize>{let all_0=self.len-self.all_popcnt;if i>=all_0{return None;}let mut ok=if let Some(&ok)=self.zero_select.get(i>>6){ok.saturating_sub(1)as usize}else{self.blocks.len().saturating_sub(1)};let mut ng=if let Some(&ng)=self.zero_select.get((i>>6)+1){ng as usize}else{self.blocks.len()};while ng-ok>1{let mid=(ok+ng)>>1;if((mid<<6)-self.blocks[mid].cum_sum_popcnt as usize)<=i{ok=mid;}else{ng=mid;}}let rem=i-((ok<<6)-self.blocks[ok].cum_sum_popcnt as usize);let offset=select1_u64(!self.blocks[ok].bit,rem);Some((ok<<6)+offset as usize)}}#[cfg(target_arch="x86_64")]fn select1_u64(x:u64,index:usize)->u32{use std::arch::x86_64::_pdep_u64;let z=1<<index;let y=unsafe{_pdep_u64(z,x)};y.trailing_zeros()}#[cfg(not(target_arch="x86_64"))]fn select1_u64(x:u64,index:usize)->u32{let mut left=0;let mut right=64;while right-left>1{let mid=(left+right)>>1;if(x&((1<<mid)-1)).count_ones()>index as u32{right=mid;}else{left=mid;}}left}}
        pub mod __internal_bits_0_1_0 {pub fn ceil_log2(n:u32)->u32{32-n.saturating_sub(1).leading_zeros()}}
        pub mod __internal_type_traits_0_1_0 {use std::fmt::{Debug,Display};use std::ops::{Add,AddAssign,Sub,SubAssign};pub trait Integral:Copy+Add<Output=Self>+AddAssign+Sub<Output=Self>+SubAssign+Ord+Zero+One+BoundedBelow+BoundedAbove+Display+Debug{}pub trait Zero{fn zero()->Self;}pub trait One{fn one()->Self;}pub trait BoundedBelow{fn min_value()->Self;}pub trait BoundedAbove{fn max_value()->Self;}macro_rules!impl_integral{($($ty:ty),*)=>{$(impl Zero for$ty{#[inline]fn zero()->Self{0}}impl One for$ty{#[inline]fn one()->Self{1}}impl BoundedBelow for$ty{#[inline]fn min_value()->Self{Self::MIN}}impl BoundedAbove for$ty{#[inline]fn max_value()->Self{Self::MAX}}impl Integral for$ty{})*};}impl_integral!(i8,i16,i32,i64,i128,isize,u8,u16,u32,u64,u128,usize);}
        pub mod __segtree_0_1_0 {use crate::__cargo_equip::preludes::__segtree_0_1_0::*;use algebra::Monoid;use internal_bits::ceil_log2;use std::ops::RangeBounds;#[derive(Debug,Clone,PartialEq,Eq)]pub struct SegTree<M:Monoid>{range_size:usize,leaf_size:usize,log:usize,data:Vec<M::Target>,}impl<M:Monoid>From<&Vec<M::Target>>for SegTree<M>{fn from(v:&Vec<M::Target>)->Self{let range_size=v.len();let log=ceil_log2(range_size as u32)as usize;let leaf_size=1<<log;let mut data=vec![M::id_element();leaf_size*2];data[leaf_size..leaf_size+range_size].clone_from_slice(v);let mut seg_tree=SegTree{range_size,leaf_size,log,data,};for i in(1..leaf_size).rev(){seg_tree.update(i);}seg_tree}}impl<M:Monoid>SegTree<M>{pub fn new(n:usize)->Self{(&vec![M::id_element();n]).into()}pub fn set(&mut self,mut p:usize,x:M::Target){assert!(p<self.range_size);p+=self.leaf_size;self.data[p]=x;for i in 1..=self.log{self.update(p>>i);}}pub fn get(&self,p:usize)->M::Target{assert!(p<self.range_size);self.data[p+self.leaf_size].clone()}pub fn prod<R:RangeBounds<usize>>(&self,range:R)->M::Target{use std::ops::Bound::*;let mut l=match range.start_bound(){Included(&l)=>l,Excluded(&l)=>l+1,Unbounded=>0,};let mut r=match range.end_bound(){Included(&r)=>r+1,Excluded(&r)=>r,Unbounded=>self.range_size,};assert!(l<=r&&r<=self.range_size);if l==0&&r==self.range_size{return self.all_prod();}l+=self.leaf_size;r+=self.leaf_size;let mut sml=M::id_element();let mut smr=M::id_element();while l<r{if l&1!=0{sml=M::binary_operation(&sml,&self.data[l]);l+=1;}if r&1!=0{r-=1;smr=M::binary_operation(&self.data[r],&smr);}l>>=1;r>>=1;}M::binary_operation(&sml,&smr)}pub fn all_prod(&self)->M::Target{self.data[1].clone()}pub fn max_right<F>(&self,mut l:usize,f:F)->usize where F:Fn(&M::Target)->bool,{assert!(l<=self.range_size);assert!(f(&M::id_element()));if l==self.range_size{return self.range_size;}l+=self.leaf_size;let mut sm=M::id_element();while{while l%2==0{l>>=1;}if!f(&M::binary_operation(&sm,&self.data[l])){while l<self.leaf_size{l>>=1;let res=M::binary_operation(&sm,&self.data[l]);if f(&res){sm=res;l+=1;}}return l-self.leaf_size;}sm=M::binary_operation(&sm,&self.data[l]);l+=1;{let l=l as isize;(l&-l)!=l}}{}self.range_size}pub fn min_left<F>(&self,mut r:usize,f:F)->usize where F:Fn(&M::Target)->bool,{assert!(r<=self.range_size);assert!(f(&M::id_element()));if r==0{return 0;}r+=self.leaf_size;let mut sm=M::id_element();while{r-=1;while r>1&&r%2!=0{r>>=1;}if!f(&M::binary_operation(&self.data[r],&sm)){while r<self.leaf_size{r=2*r+1;let res=M::binary_operation(&self.data[r],&sm);if f(&res){sm=res;r-=1;}}return r+1-self.leaf_size;}sm=M::binary_operation(&self.data[r],&sm);{let r=r as isize;(r&-r)!=r}}{}0}}impl<M:Monoid>SegTree<M>{fn update(&mut self,k:usize){self.data[k]=M::binary_operation(&self.data[k*2],&self.data[k*2+1]);}}}
        pub mod wavelet_matrix_segtree {use crate::__cargo_equip::preludes::wavelet_matrix_segtree::*;use algebra::{Commutative,Group,Monoid};use bitdict::BitDict;use internal_bits::ceil_log2;use internal_type_traits::Integral;use segtree::SegTree;use std::ops::RangeBounds;pub struct WMSegWrapper<M:Monoid+Commutative,T:Integral>{wm:WaveletMatrixSegTree<M>,sorted_y:Vec<T>,x_y:Vec<(T,T)>,}impl<M:Monoid+Commutative,T:Integral>WMSegWrapper<M,T>{pub fn new(update_points:Vec<(T,T)>)->Self{Self::from_weight(update_points,vec![])}pub fn from_weight(mut update_points:Vec<(T,T)>,mut init_weights:Vec<(T,T,M::Target)>,)->Self{update_points.sort_unstable();update_points.dedup();let mut sorted_y=update_points.iter().map(|(_,y)|y).copied().collect::<Vec<_>>();sorted_y.sort_unstable();let compressed_list=update_points.iter().map(|(_,y)|sorted_y.binary_search(y).unwrap()).collect::<Vec<_>>();let mut weight_list=vec![M::id_element();update_points.len()];init_weights.sort_unstable_by_key(|&(x,y,_)|(x,y));for ls in init_weights.windows(2){let(x1,y1)=(ls[0].0,ls[0].1);let(x2,y2)=(ls[1].0,ls[1].1);assert_ne!((x1,y1),(x2,y2),"init_weights has duplicated points!!!");}for(x,y,w)in init_weights{let idx=update_points.binary_search(&(x,y)).expect("init_weight points are not in update_points!!!");weight_list[idx]=w.clone();}let wm=WaveletMatrixSegTree::<M>::from_weight(&compressed_list,&weight_list);Self{wm,sorted_y,x_y:update_points,}}fn get_pos_range<R:RangeBounds<T>>(&self,range:R)->(usize,usize){use std::ops::Bound::*;let l=match range.start_bound(){Included(&l)=>l,Excluded(&l)=>l+T::one(),Unbounded=>T::min_value(),};let r=match range.end_bound(){Included(&r)=>r+T::one(),Excluded(&r)=>r,Unbounded=>T::max_value(),};assert!(l<=r);let l=self.x_y.partition_point(|&(x,_)|x<l);let r=self.x_y.partition_point(|&(x,_)|x<r);(l,r)}fn get_num_range<R:RangeBounds<T>>(&self,range:R)->(usize,usize){use std::ops::Bound::*;let l=match range.start_bound(){Included(&l)=>l,Excluded(&l)=>l+T::one(),Unbounded=>T::min_value(),};let r=match range.end_bound(){Included(&r)=>r+T::one(),Excluded(&r)=>r,Unbounded=>T::max_value(),};assert!(l<=r);let l=self.sorted_y.partition_point(|&y|y<l);let r=self.sorted_y.partition_point(|&y|y<r);(l,r)}pub fn set(&mut self,x:T,y:T,new_val:M::Target){let x=self.x_y.binary_search(&(x,y)).expect("(x, y) is not in update_queries!!!");self.wm.set(x,new_val);}pub fn get(&self,x:T,y:T)->M::Target{let Ok(x)=self.x_y.binary_search(&(x,y))else{return M::id_element();};self.wm.get_weight(x)}pub fn rect_sum_monoid<R1:RangeBounds<T>,R2:RangeBounds<T>>(&self,x_range:R1,y_range:R2,)->M::Target{let(xl,xr)=self.get_pos_range(x_range);let(y_low,y_hi)=self.get_num_range(y_range);self.wm.rect_sum_monoid(xl..xr,y_low..y_hi)}pub fn rect_sum_group<R1:RangeBounds<T>,R2:RangeBounds<T>>(&self,x_range:R1,y_range:R2,)->M::Target where M:Group,{let(xl,xr)=self.get_pos_range(x_range);let(y_low,y_hi)=self.get_num_range(y_range);self.wm.rect_sum_group(xl..xr,y_low..y_hi)}}struct WaveletMatrixSegTree<M:Monoid+Commutative>{upper_bound:usize,len:usize,indices:Vec<BitDict>,segtree_per_bit:Vec<SegTree<M>>,}impl<M:Monoid+Commutative>WaveletMatrixSegTree<M>{pub fn from_weight(compressed_list:&[usize],weight_list:&[M::Target])->Self{assert_eq!(compressed_list.len(),weight_list.len());let len=compressed_list.len();let upper_bound=*compressed_list.iter().max().unwrap_or(&0)+1;let log=ceil_log2(upper_bound as u32+1)as usize;let mut indices=vec![BitDict::new(len);log];let mut tmp=vec![Vec::with_capacity(len);2];let mut list=compressed_list.to_vec();let mut weight_list=weight_list.to_vec();let mut tmp_weight=vec![Vec::with_capacity(len);2];let mut segtree_per_bit=Vec::with_capacity(log);for(ln,index)in indices.iter_mut().enumerate().rev(){for(x,(y,w))in list.drain(..).zip(weight_list.drain(..)).enumerate(){if(y>>ln)&1==1{index.set(x);tmp[1].push(y);tmp_weight[1].push(w);}else{tmp[0].push(y);tmp_weight[0].push(w);}}index.build();list.append(&mut tmp[0]);list.append(&mut tmp[1]);weight_list.append(&mut tmp_weight[0]);weight_list.append(&mut tmp_weight[1]);segtree_per_bit.push(SegTree::from(&weight_list));}segtree_per_bit.reverse();Self{upper_bound,len,indices,segtree_per_bit,}}fn get_pos_range<R:RangeBounds<usize>>(&self,range:R)->(usize,usize){use std::ops::Bound::*;let l=match range.start_bound(){Included(&l)=>l,Excluded(&l)=>l+1,Unbounded=>0,};let r=match range.end_bound(){Included(&r)=>r+1,Excluded(&r)=>r,Unbounded=>self.len,};assert!(l<=r&&r<=self.len);(l,r)}fn get_num_range<R:RangeBounds<usize>>(&self,range:R)->(usize,usize){use std::ops::Bound::*;let l=match range.start_bound(){Included(&l)=>l,Excluded(&l)=>l+1,Unbounded=>0,}.min(self.upper_bound);let r=match range.end_bound(){Included(&r)=>r+1,Excluded(&r)=>r,Unbounded=>self.upper_bound,}.min(self.upper_bound);assert!(l<=r);(l,r)}pub fn prefix_rect_sum<R:RangeBounds<usize>>(&self,x_range:R,upper:usize)->M::Target{if upper==0{return M::id_element();}let(mut begin,mut end)=self.get_pos_range(x_range);let mut ret=M::id_element();for(ln,index)in self.indices.iter().enumerate().rev(){let bit=(upper>>ln)&1;let rank1_begin=index.rank_1(begin);let rank1_end=index.rank_1(end);let rank0_begin=begin-rank1_begin;let rank0_end=end-rank1_end;if bit==1{ret=M::binary_operation(&ret,&self.segtree_per_bit[ln].prod(rank0_begin..rank0_end),);begin=index.rank0_all()+rank1_begin;end=index.rank0_all()+rank1_end;}else{begin=rank0_begin;end=rank0_end;}}ret}pub fn rect_sum_group<R1:RangeBounds<usize>+Clone,R2:RangeBounds<usize>>(&self,x_range:R1,y_range:R2,)->M::Target where M:Group,{let(begin,end)=self.get_num_range(y_range);let s2=self.prefix_rect_sum(x_range.clone(),end);let s1=self.prefix_rect_sum(x_range,begin);M::binary_operation(&M::inverse(&s1),&s2)}pub fn rect_sum_monoid<R1:RangeBounds<usize>,R2:RangeBounds<usize>>(&self,x_range:R1,y_range:R2,)->M::Target{let(xl,xr)=self.get_pos_range(x_range);let(y_low,y_hi)=self.get_num_range(y_range);let mut ret=M::id_element();let ln=self.indices.len();self.dfs(&mut ret,ln,xl,xr,0,1<<ln,y_low,y_hi);ret}#[allow(clippy::too_many_arguments)]fn dfs(&self,ret:&mut M::Target,ln:usize,xl:usize,xr:usize,yl:usize,yr:usize,y_low:usize,y_hi:usize,){assert_eq!(yr-yl,1<<ln);if y_hi<=yl||yr<=y_low{return;}if y_low<=yl&&yr<=y_hi{*ret=M::binary_operation(ret,&self.segtree_per_bit[ln].prod(xl..xr));return;}let ln=ln-1;let rank1_xl=self.indices[ln].rank_1(xl);let rank1_xr=self.indices[ln].rank_1(xr);let rank0_all=self.indices[ln].rank0_all();let rank0_xl=xl-rank1_xl;let rank0_xr=xr-rank1_xr;let ymid=(yl+yr)/2;self.dfs(ret,ln,rank0_xl,rank0_xr,yl,ymid,y_low,y_hi);self.dfs(ret,ln,rank0_all+rank1_xl,rank0_all+rank1_xr,ymid,yr,y_low,y_hi,);}pub fn set(&mut self,mut x:usize,new_val:M::Target){assert!(x<self.len);for(ln,index)in self.indices.iter().enumerate().rev(){let bit=index.access(x);if bit{x=index.rank0_all()+index.rank_1(x);}else{x=index.rank_0(x);}self.segtree_per_bit[ln].set(x,new_val.clone());}}pub fn get_weight(&self,x:usize)->M::Target{assert!(x<self.len);let index=self.indices.last().unwrap();let x=if index.access(x){index.rank0_all()+index.rank_1(x)}else{index.rank_0(x)};self.segtree_per_bit.last().unwrap().get(x)}}}
    }

    pub(crate) mod macros {
        pub mod algebra {}
        pub mod __bitdict_0_1_0 {}
        pub mod __internal_bits_0_1_0 {}
        pub mod __internal_type_traits_0_1_0 {}
        pub mod __segtree_0_1_0 {}
        pub mod wavelet_matrix_segtree {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod algebra {}
        pub mod __bitdict_0_1_0 {}
        pub mod __internal_bits_0_1_0 {}
        pub mod __internal_type_traits_0_1_0 {}
        pub mod __segtree_0_1_0 {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{algebra,__internal_bits_0_1_0 as internal_bits};}
        pub mod wavelet_matrix_segtree {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{algebra,__bitdict_0_1_0 as bitdict,__internal_bits_0_1_0 as internal_bits,__internal_type_traits_0_1_0 as internal_type_traits,__segtree_0_1_0 as segtree};}
    }
}
0