結果
| 問題 | No.880 Yet Another Segment Tree Problem |
| ユーザー |
 ArcAki
|
| 提出日時 | 2025-02-23 06:11:09 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 1,065 ms / 5,000 ms |
| コード長 | 10,780 bytes |
| コンパイル時間 | 18,383 ms |
| コンパイル使用メモリ | 397,456 KB |
| 実行使用メモリ | 36,260 KB |
| 最終ジャッジ日時 | 2025-06-20 11:27:27 |
| 合計ジャッジ時間 | 38,669 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 38 |
ソースコード
#[allow(unused_imports)]
use std::{
cell::RefCell, convert::{Infallible, TryFrom, TryInto as _},
fmt::{self, Debug, Display, Formatter, Write},
fs::{File},
hash::{Hash, Hasher},
iter::{Product, Sum},
marker::PhantomData,
ops::{Add, AddAssign, Sub, SubAssign, Div, DivAssign, Mul, MulAssign, Neg, },
str::FromStr,
sync::{atomic::{self, AtomicU32, AtomicU64}, Once},
collections::{*},
mem::{swap},
cmp::{self, Reverse, Ordering, Eq, PartialEq, PartialOrd},
thread::LocalKey,
f64::consts::PI,
time::Instant,
io::{self, stdin, Read, read_to_string},
};
#[allow(unused_imports)]
use proconio::{input, input_interactive, marker::{*}};
#[allow(unused_imports)]
//use rand::{thread_rng, Rng, seq::SliceRandom};
#[allow(unused_imports)]
//use ac_library::{*};
#[allow(dead_code)]
const INF: i64 = 1<<60;
#[allow(dead_code)]
const MOD: usize = 998244353;
#[allow(dead_code)]
const D: [(usize, usize); 4] = [(1, 0), (0, 1), (!0, 0), (0, !0)];
pub fn bit_length(x: usize)->usize{
64-x.saturating_sub(1).leading_zeros()as usize
}
pub trait SegTreeMonoid{
type S: Clone+BeatsFail;
fn identity()->Self::S;
fn op(a: &Self::S, b: &Self::S)->Self::S;
}
pub trait LazySegtreeMonoid{
type M: SegTreeMonoid;
type F: Clone;
fn id_e()-><Self::M as SegTreeMonoid>::S{<Self::M as SegTreeMonoid>::identity()}
fn op(a: &<Self::M as SegTreeMonoid>::S, b: &<Self::M as SegTreeMonoid>::S)-><Self::M as SegTreeMonoid>::S{<Self::M>::op(a, b)}
fn identity()->Self::F;
fn map(f: &Self::F, x: &<Self::M as SegTreeMonoid>::S)-><Self::M as SegTreeMonoid>::S;
fn composition(f: &Self::F, g: &Self::F)->Self::F;
}
pub trait BeatsFail{
fn fail(&self) -> bool;
}
pub struct LazySegtree<F> where F: LazySegtreeMonoid{
n: usize,
log: usize,
data: Vec<<F::M as SegTreeMonoid>::S>,
lazy: Vec<F::F>,
}
impl<F: LazySegtreeMonoid> LazySegtree<F>{
// 初期値開始
pub fn new(n: usize)->Self{
let n = n.next_power_of_two();
let log = bit_length(n);
let lazy = vec![F::identity(); n<<1];
let data = vec![F::id_e(); n<<1];
LazySegtree{
n, log, data, lazy,
}
}
// vectorを飲ませるならこっち。O(N)で初期化。
pub fn build(vec: &Vec<<F::M as SegTreeMonoid>::S>)->Self {
let n = vec.len().next_power_of_two();
let log = bit_length(n);
let lazy = vec![F::identity(); n<<1];
let mut data = vec![F::id_e(); n<<1];
data[n..(n+vec.len())].clone_from_slice(vec);
let mut res = LazySegtree{
n, log, data, lazy,
};
for i in (1..n).rev(){
res.update(i);
}
res
}
pub fn set(&mut self, mut p: usize, x: <F::M as SegTreeMonoid>::S){
p += self.n;
for i in (1..=self.log).rev(){
self.push(p>>i);
}
self.data[p] = x;
for i in 1..=self.log{
self.update(p>>i);
}
}
// 下からデータ更新
fn update(&mut self, k: usize){
self.data[k] = F::op(&self.data[2*k], &self.data[2*k+1]);
}
// 遅延反映
fn inner_apply(&mut self, k: usize, f: F::F){
self.data[k] = F::map(&f, &self.data[k]);
if k < self.n{
self.lazy[k] = F::composition(&f, &self.lazy[k]);
if self.data[k].fail(){
self.push(k); self.update(k);
}
}
}
// 上から遅延更新
fn push(&mut self, k: usize){
self.inner_apply(2*k, self.lazy[k].clone());
self.inner_apply(2*k+1, self.lazy[k].clone());
self.lazy[k] = F::identity();
}
pub fn get(&mut self, mut p: usize)-><F::M as SegTreeMonoid>::S{
p += self.n;
for i in (1..self.log).rev(){
self.push(p>>i);
}
self.data[p].clone()
}
// whileで打ち切った方が早そうだけどどうなんでしょう？
pub fn prod(&mut self, mut l: usize, mut r: usize)-><F::M as SegTreeMonoid>::S{
if r<=l{return F::id_e()}
l += self.n; r += self.n;
for i in (1..=self.log).rev(){
if ((l>>i)<<i) != l{
self.push(l>>i);
}
if ((r>>i)<<i) != r{
self.push(r>>i);
}
}
let mut acl = F::id_e();
let mut acr = F::id_e();
while l < r{
if l&1 != 0{
acl = F::op(&acl, &self.data[l]);
l += 1;
}
if r&1 != 0{
r -= 1;
acr = F::op(&self.data[r], &acr);
}
l >>= 1; r >>= 1;
}
F::op(&acl, &acr)
}
pub fn all_prod(&mut self)-><F::M as SegTreeMonoid>::S{
self.update(1);
self.data[1].clone()
}
pub fn apply_range(&mut self, mut l: usize, mut r: usize, f: F::F){
if l>=r{return;}
l += self.n; r += self.n;
for i in (1..=self.log).rev(){
if ((l>>i)<<i)!=l{
self.push(l>>i);
}
if ((r>>i)<<i)!=r{
self.push((r-1)>>i);
}
}
let left = l;
let right = r;
while l < r{
if l&1!=0{
self.inner_apply(l, f.clone());
l += 1;
}
if r&1!=0{
r -= 1;
self.inner_apply(r, f.clone());
}
l >>= 1; r>>=1;
}
for i in 1..=self.log{
if ((left>>i)<<i)!=left{
self.update(left>>i);
}
if ((right>>i)<<i)!=right{
self.update((right-1)>>i);
}
}
}
pub fn max_right<G>(&mut self, mut l: usize, g: G)->usize
where G: Fn(<F::M as SegTreeMonoid>::S)->bool{
assert!(g(F::id_e()));
if l >= self.n{return self.n}
l += self.n;
for i in 1..=self.log{
self.push(l>>i);
}
let mut ac = F::id_e();
while {
while l%2==0{
l>>=1;
}
if !g(F::op(&ac, &self.data[l])){
while l < self.n{
self.push(l);
l *= 2;
let res = F::op(&ac, &self.data[l]);
if g(res.clone()){
ac = res;
l += 1;
}
}
return l-self.n;
}
ac = F::op(&ac, &self.data[l]);
l += 1;
let left = l as isize;
(left&-left)!=left
} {}
self.n
}
pub fn min_left<G>(&mut self, mut r: usize, g: G)->usize
where G: Fn(<F::M as SegTreeMonoid>::S)->bool{
assert!(g(F::id_e()));
if r==0{return 0;}
r += self.n;
for i in (1..=self.log).rev(){
self.push((r-1)>>i);
}
let mut ac = F::id_e();
while {
r -= 1;
while r%2 != 0{
r >>= 1;
}
if !g(F::op(&self.data[r], &ac)){
while r < self.n{
self.push(r);
r = 2*r+1;
let res = F::op(&self.data[r], &ac);
if g(res.clone()){
ac = res;
r -= 1;
}
}
return r+1-self.n;
}
ac = F::op(&self.data[r], &ac);
let right = r as isize;
(right&-right)!=right
} {}
0
}
pub fn get_slice(&mut self, mut l: usize, mut r: usize)->Vec<<F::M as SegTreeMonoid>::S>{
l += self.n; r += self.n;
for i in 1..self.n {
self.push(i)
}
(l..r).into_iter().map(|z| self.data[z].clone()).collect()
}
}
#[inline(always)]
fn gcd(mut a: i128, mut b: i128)->i128{
while b != 0{
let c = a;
a = b;
b = c%b;
}
a
}
#[derive(Clone, Copy)]
struct S{
num: i128,
mx: i128,
ac: i128,
lcm: i128,
fail: bool,
}
impl S{
fn new(x: i128, n: i128)->Self{
S{
num: n,
mx: x,
ac: x*n,
lcm: x,
fail: false
}
}
}
impl BeatsFail for S{
fn fail(&self) -> bool {
self.fail
}
}
struct M;
impl SegTreeMonoid for M{
type S = S;
fn identity() -> Self::S {
S{
num: 0,
mx: 0,
ac: 0,
lcm: 0,
fail: false,
}
}
fn op(&a: &Self::S, &b: &Self::S) -> Self::S {
if b.num==0{
return a;
} else if a.num==0{
return b;
}
let lcm = (a.lcm*b.lcm/gcd(a.lcm, b.lcm)).min(1<<30);
S{
num: a.num+b.num,
mx: a.mx.max(b.mx),
ac: a.ac+b.ac,
lcm,
fail: false,
}
}
}
struct MM;
impl LazySegtreeMonoid for MM{
type M = M;
type F = (i128, i128);
fn identity() -> Self::F {
(0, 0)
}
fn map(&f: &Self::F, &x: &<Self::M as SegTreeMonoid>::S) -> <Self::M as SegTreeMonoid>::S {
if x.fail{
return x;
}
let mut res = x;
if f.1 != 0{
res = S::new(f.1, res.num);
}
if f.0 != 0{
if res.mx*res.num == res.ac{
res = S::new(gcd(res.mx, f.0), res.num);
} else if x.lcm >= 1<<30||f.0%res.lcm != 0{
res.fail = true;
}
}
res
}
fn composition(&f: &Self::F, &g: &Self::F) -> Self::F {
if f.1 != 0{
(0, f.1)
} else if g.1 != 0{
(0, gcd(f.0, g.1))
} else {
(gcd(f.0, g.0), 0)
}
}
}
use proconio::fastout;
#[fastout]
fn main(){
input! {
n: usize, q: usize,
a: [i128; n],
}
let base = a.into_iter().map(|z| S::new(z, 1)).collect::<Vec<_>>();
let mut segtree = LazySegtree::<MM>::build(&base);
for _ in 0..q{
input!{t: Usize1}
match t{
0 => {
input!{l: Usize1, r: usize, x: i128}
segtree.apply_range(l, r, (0, x));
},
1 => {
input!{l: Usize1, r: usize, x: i128}
segtree.apply_range(l, r, (x, 0));
},
2 => {
input!{l: Usize1, r: usize}
let res = segtree.prod(l, r);
println!("{}", res.mx);
},
_ => {
input!{l: Usize1, r: usize}
let res = segtree.prod(l, r);
println!("{}", res.ac);
},
}
}
}