// 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::>(); 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::>(); let init_weight = queries .iter() .take(n) .map(|query| match query { Query::Add(x, y, area) => (*x, *y, *area), _ => unreachable!(), }) .collect::>(); let mut wm_seg = WMSegWrapper::::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::>(); let y_list_parralel = y_list .into_iter() .map(|y| y - y_list[0]) .collect::>(); 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>;}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,all_popcnt:usize,one_select:Vec,zero_select:Vec,}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>6].bit>>(i&63))&1==1}pub fn set(&mut self,i:usize){debug_assert!(i>6].bit|=1<<(i&63);}pub fn build(&mut self){let all_popcnt=self.blocks.iter().map(|b|b.bit.count_ones()).sum::()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{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{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<u32{let mut left=0;let mut right=64;while right-left>1{let mid=(left+right)>>1;if(x&((1<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+AddAssign+Sub+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{range_size:usize,leaf_size:usize,log:usize,data:Vec,}implFrom<&Vec>for SegTree{fn from(v:&Vec)->Self{let range_size=v.len();let log=ceil_log2(range_size as u32)as usize;let leaf_size=1<SegTree{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>i);}}pub fn get(&self,p:usize)->M::Target{assert!(p>(&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>=1;r>>=1;}M::binary_operation(&sml,&smr)}pub fn all_prod(&self)->M::Target{self.data[1].clone()}pub fn max_right(&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>=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(&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 rSegTree{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{wm:WaveletMatrixSegTree,sorted_y:Vec,x_y:Vec<(T,T)>,}implWMSegWrapper{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::>();sorted_y.sort_unstable();let compressed_list=update_points.iter().map(|(_,y)|sorted_y.binary_search(y).unwrap()).collect::>();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::::from_weight(&compressed_list,&weight_list);Self{wm,sorted_y,x_y:update_points,}}fn get_pos_range>(&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>(&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|yM::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,R2:RangeBounds>(&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,R2:RangeBounds>(&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{upper_bound:usize,len:usize,indices:Vec,segtree_per_bit:Vec>,}implWaveletMatrixSegTree{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>(&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>(&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>(&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+Clone,R2:RangeBounds>(&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,R2:RangeBounds>(&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<M::Target{assert!(x