#![allow(unused_imports,non_snake_case,dead_code)] use std::{cmp::Reverse as Rev,collections::*,iter::*}; use proconio::{marker::*,*}; #[fastout] fn main(){ input!{ n:usize, q:usize, } let mut qs=(0..q).map(|i|{ let time=i+1; input!{t:usize} if t==1{ input!{x:Usize1} Q{time,x,c:-1} } else{ input!{x:Usize1,c:i64} Q{time,x,c} } }).collect::>(); qs.insert(0,Q{time:0,x:0,c:0}); const INF:i64=i64::MAX/64; let mut ans=vec![INF;qs.len()]; let mut todo=vec![vec![];n]; let mut add=vec![vec![];n]; for i in 0..qs.len(){ if qs[i].c==-1{ todo[qs[i].x].push(qs[i]); } else{ add[qs[i].x].push(qs[i]); } } let mut set=BTreeMap::::new(); let mut rem=vec![]; for i in 0..n{ 'a: for &Q{time,x,c} in &add[i]{ let new=c-x as i64; if let Some((_,&pc))=set.range(..=time).rev().next(){ if pc<=new{ continue 'a; } } rem.clear(); for (&pt,&pc) in set.range(time..){ if new<=pc{ rem.push(pt); } } for &t in &rem{ set.remove(&t); } set.insert(time,new); } for &Q{time,x,..} in &todo[i]{ if let Some((_,&nc))=set.range(..=time).rev().next(){ ans[time]=ans[time].min(nc+x as i64); } } } set.clear(); for i in (0..n).rev(){ 'a: for &Q{time,x,c} in &add[i]{ let new=c-(n-x) as i64; if let Some((_,&pc))=set.range(..=time).rev().next(){ if pc<=new{ continue 'a; } } rem.clear(); for (&pt,&pc) in set.range(time..){ if new<=pc{ rem.push(pt); } } for &t in &rem{ set.remove(&t); } set.insert(time,new); } for &Q{time,x,..} in &todo[i]{ if let Some((_,&nc))=set.range(..=time).rev().next(){ ans[time]=ans[time].min(nc+(n-x) as i64); } } } for i in 0..qs.len(){ if qs[i].c==-1{ println!("{}",ans[i]); } } } #[derive(Clone,Copy)] struct Q{ time:usize, x:usize, c:i64, }