#612721 (Rust) No.880 Yet Another Segment Tree Problem

提出ソース
結果

問題	No.880 Yet Another Segment Tree Problem
コンテスト
ユーザー	shino16
提出日時	2021-02-03 21:07:35
言語	Rust (1.83.0 + proconio)
結果	TLE (最新) AC (最初)
実行時間	-
コード長	13,298 bytes
記録
コンパイル時間	13,227 ms
コンパイル使用メモリ	379,576 KB
実行使用メモリ	13,440 KB
最終ジャッジ日時	2024-09-22 19:57:08
合計ジャッジ時間	27,013 ms
ジャッジサーバーID （参考情報）	judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 1
other	AC * 31 TLE * 1 -- * 5
権限があれば一括ダウンロードができます
ソースコード

raw source code
// verify-helper: PROBLEM https://yukicoder.me/problems/no/880

use crate::lib::ds::segtree::beats::*;
use crate::lib::math::gcd::*;
use crate::lib::io::*;
use crate::lib::iter::Itertools;

#[derive(Debug, Clone, Copy)]
struct E {
	len: usize,
	sum: u64,
	max: u32,
	lcm: u32,
}

#[derive(Debug, Clone, Copy)]
enum F {
	Asgn(u32),
	Gcd(u32),
	Unit,
}
use F::*;

struct M;
impl Alg for M {
	type Item = E;
}
impl Monoid for M {
	fn unit(&self) -> Self::Item {
		E { len: 0, sum: 0, max: 0, lcm: 1 }
	}
	fn op(&self, x: Self::Item, y: Self::Item) -> Self::Item {
		if x.len == 0 {
			y
		} else if y.len == 0 {
			x
		} else {
			E {
				len: x.len + y.len,
				sum: x.sum + y.sum,
				max: x.max.max(y.max),
				lcm: lcm(x.lcm, y.lcm),
			}
		}
	}
}

struct A;
impl Alg for A {
	type Item = F;
}
impl Monoid for A {
	fn unit(&self) -> Self::Item {
		Unit
	}
	fn op(&self, x: Self::Item, y: Self::Item) -> Self::Item {
		match y {
			Asgn(_) => y,
			Gcd(y) => match x {
				Asgn(a) => Asgn(ugcd(a, y)),
				Gcd(x) => Gcd(ugcd(x, y)),
				_ => Gcd(y),
			},
			_ => x,
		}
	}
}

fn lcm(x: u32, y: u32) -> u32 {
	let lcm = x as u64 * y as u64 / ugcd(x, y) as u64;
	(1 << 30).min(lcm) as u32
}

fn fill(a: u32, len: usize) -> E {
	E { len, sum: a as u64 * len as u64, max: a, lcm: a }
}

fn act(e: E, a: F) -> Option<E> {
	match a {
		Asgn(a) => Some(fill(a, e.len)),
		Gcd(a) =>
			if e.len == 1 {
				Some(fill(ugcd(e.max, a), 1))
			} else if e.lcm != 1 << 30 && a % e.lcm == 0 {
				Some(e)
			} else {
				None
			},
		_ => Some(e),
	}
}

fn main() {
	let mut io = IO::new();
	let [n, q]: [usize; 2] = io.scan();
	let a = io
		.scan_iter::<u32>(n)
		.map(|a| E { len: 1, sum: a as u64, max: a, lcm: a })
		.collect_vec();
	let mut st = SegmentTreeBeats::from_slice(&a, M, A, act);
	for _ in 0..q {
		let (c, Usize1(l), r) = io.scan();
		match c {
			1 => {
				st.act_over(l, r, Asgn(io.scan()));
			},
			2 => {
				st.act_over(l, r, Gcd(io.scan()));
			},
			3 => {
				io.println(st.ask(l, r).max);
			},
			_ => {
				io.println(st.ask(l, r).sum);
			},
		}
	}
}




pub mod lib {

pub mod alg {


pub trait Alg {
	type Item: Copy;
}

pub trait Monoid: Alg {
	fn unit(&self) -> Self::Item;
	fn op(&self, x: Self::Item, y: Self::Item) -> Self::Item;
	fn op_to(&self, y: Self::Item, x: &mut Self::Item) {
		*x = self.op(*x, y);
	}
}

pub trait Group: Monoid {
	fn inv(&self, x: Self::Item) -> Self::Item;
	fn op_inv_to(&self, y: Self::Item, x: &mut Self::Item) {
		*x = self.op(*x, self.inv(y))
	}
}

macro_rules! impl_monoid {
	($target:ty, $($params:tt : $bounds:tt),*) => {
		impl<$($params : $bounds),*> Alg for $target {
			type Item = T;
		}
		impl<$($params : $bounds),*> Monoid for $target {
			fn unit(&self) -> Self::Item {
				(self.0)()
			}
			fn op(&self, x: Self::Item, y: Self::Item) -> Self::Item {
				(self.1)(x, y)
			}
		}
	};
}

macro_rules! impl_group {
	($target:ty, $($params:tt : $bounds:tt),*) => {
		impl_monoid!($target, $($params : $bounds),*);
		impl<$($params : $bounds),*> Group for $target {
			fn inv(&self, x: Self::Item) -> Self::Item {
				(self.2)(x)
			}
		}
	};
}

pub struct MonoidImpl<T: Copy, Unit: Fn() -> T, Op: Fn(T, T) -> T>(pub Unit, pub Op);
pub struct GroupImpl<T, Unit, Op, Inv>(pub Unit, pub Op, pub Inv)
where
	T: Copy,
	Unit: Fn() -> T,
	Op: Fn(T, T) -> T,
	Inv: Fn(T) -> T;

// help!
impl_monoid!(MonoidImpl<T, Unit, Op>, T: Copy, Unit: (Fn() -> T), Op: (Fn(T, T) -> T));
impl_group!(GroupImpl<T, Unit, Op, Inv>,
			T: Copy, Unit: (Fn() -> T), Op: (Fn(T, T) -> T), Inv: (Fn(T) -> T));

}  // mod alg

pub mod ds {

pub mod segtree {

pub mod beats {

pub use crate::lib::alg::*;

fn trunc(x: usize) -> usize {
	x >> x.trailing_zeros()
}

#[derive(Clone)]
pub struct SegmentTreeBeats<On: Alg, Act: Alg, Apply>
where
	Apply: Fn(On::Item, Act::Item) -> Option<On::Item>,
{
	len: usize,
	log: u32,
	data: Vec<(On::Item, Act::Item)>,
	on_alg: On,
	act_alg: Act,
	apply: Apply,
}

impl<On: Monoid, Act: Monoid, Apply: Fn(On::Item, Act::Item) -> Option<On::Item>>
	SegmentTreeBeats<On, Act, Apply>
{
	pub fn new(len: usize, on_alg: On, act_alg: Act, apply: Apply) -> Self {
		Self {
			len,
			log: len.next_power_of_two().trailing_zeros(),
			data: vec![(on_alg.unit(), act_alg.unit()); len * 2],
			on_alg,
			act_alg,
			apply,
		}
	}
	pub fn from_slice(slice: &[On::Item], on_alg: On, act_alg: Act, apply: Apply) -> Self {
		let len = slice.len();
		let log = len.next_power_of_two().trailing_zeros();
		let iter = slice.iter().map(|&x| (x, act_alg.unit()));
		let mut data: Vec<_> = iter.clone().chain(iter).collect();
		for i in (1..len).rev() {
			data[i].0 = on_alg.op(data[i << 1].0, data[i << 1 | 1].0);
		}
		Self { len, log, data, on_alg, act_alg, apply }
	}
	pub fn len(&self) -> usize {
		self.len
	}
	fn apply(&mut self, p: usize, actor: Act::Item) {
		self.act_alg.op_to(actor, &mut self.data[p].1);
		self.data[p].0 = if let Some(d) = (self.apply)(self.data[p].0, actor) {
			d
		} else {
			self.push(p);
			self.on_alg.op(self.data[p << 1].0, self.data[p << 1 | 1].0)
		};
	}
	fn push(&mut self, p: usize) {
		self.apply(p << 1, self.data[p].1);
		self.apply(p << 1 | 1, self.data[p].1);
		self.data[p].1 = self.act_alg.unit();
	}
	fn flush(&mut self, p: usize) {
		for s in (1..=self.log).rev() {
			self.push(p >> s);
		}
	}
	fn build(&mut self, mut p: usize) {
		p >>= 1;
		while p != 0 {
			self.data[p].0 = self.on_alg.op(self.data[p << 1].0, self.data[p << 1 | 1].0);
			// debug_assert_eq!(self.data[p].1, self.act_alg.unit());
			p >>= 1;
		}
	}
	pub fn ask(&mut self, l: usize, r: usize) -> On::Item {
		self.flush(trunc(l + self.len()));
		self.flush(trunc(r + self.len()) - 1);
		let [mut resl, mut resr] = [self.on_alg.unit(); 2];
		let (mut l, mut r) = (l + self.len(), r + self.len());
		while l < r {
			if l & 1 != 0 {
				resl = self.on_alg.op(resl, self.data[l].0);
				l += 1;
			}
			if r & 1 != 0 {
				r -= 1;
				resr = self.on_alg.op(self.data[r].0, resr);
			}
			l >>= 1;
			r >>= 1;
		}
		self.on_alg.op(resl, resr)
	}
	pub fn exec<F: FnOnce(&mut On::Item)>(&mut self, pos: usize, f: F) {
		self.flush(pos + self.len());
		let p = pos + self.len();
		f(&mut self.data[p].0);
		self.build(pos + self.len());
	}
	pub fn act_over(&mut self, l: usize, r: usize, actor: Act::Item) {
		self.flush(trunc(l + self.len()));
		self.flush(trunc(r + self.len()) - 1);
		{
			let (mut l, mut r) = (l + self.len(), r + self.len());
			while l < r {
				if l & 1 != 0 {
					self.apply(l, actor);
					l += 1;
				}
				if r & 1 != 0 {
					r -= 1;
					self.apply(r, actor);
				}
				l >>= 1;
				r >>= 1;
			}
		}
		self.build(trunc(l + self.len()));
		self.build(trunc(r + self.len()) - 1);
	}
}

}  // mod beats

}  // mod segtree

}  // mod ds

pub mod io {

use std::io::{stdout, BufWriter, Read, StdoutLock, Write};
use std::marker::PhantomData;

pub type Bytes = &'static [u8];

pub struct IO {
	iter: std::str::SplitAsciiWhitespace<'static>,
	buf: BufWriter<StdoutLock<'static>>,
}
impl IO {
	pub fn new() -> Self {
		let mut input = String::new();
		std::io::stdin().read_to_string(&mut input).unwrap();
		let input = Box::leak(input.into_boxed_str());
		let out = Box::leak(Box::new(stdout()));
		IO {
			iter: input.split_ascii_whitespace(),
			buf: BufWriter::new(out.lock()),
		}
	}
	fn scan_str(&mut self) -> &'static str { self.iter.next().unwrap() }
	fn scan_raw(&mut self) -> Bytes { self.scan_str().as_bytes() }
	pub fn scan<T: Scan>(&mut self) -> T { T::scan(self) }
	pub fn scan_iter<T: Scan>(&mut self, n: usize) -> std::iter::Take<Iter<'_, T>> {
		Iter { io: self, _m: PhantomData }.take(n)
	}
	pub fn scan_vec<T: Scan>(&mut self, n: usize) -> Vec<T> {
		(0..n).map(|_| self.scan()).collect()
	}
	pub fn print<T: Print>(&mut self, x: T) { T::print(self, x); }
	pub fn println<T: Print>(&mut self, x: T) {
		self.print(x);
		self.print("\n");
	}
	pub fn iterln<T: Print, I: IntoIterator<Item = T>>(&mut self, into_iter: I, delim: &str) {
		let mut iter = into_iter.into_iter();
		if let Some(v) = iter.next() {
			self.print(v);
			for v in iter {
				self.print(delim);
				self.print(v);
			}
		}
		self.print("\n");
	}
	pub fn flush(&mut self) { self.buf.flush().unwrap(); }
}
pub struct Iter<'a, T> {
	io: &'a mut IO,
	_m: PhantomData<T>,
}
impl<T: Scan> Iterator for Iter<'_, T> {
	type Item = T;
	fn next(&mut self) -> Option<Self::Item> { Some(self.io.scan()) }
}
pub trait Scan {
	fn scan(io: &mut IO) -> Self;
}
pub trait Print {
	fn print(w: &mut IO, x: Self);
}
macro_rules! impl_parse_iint {
	($($t:ty),*) => { $(
		impl Scan for $t {
			fn scan(s: &mut IO) -> Self {
				let scan = |t: &[u8]| t.iter().fold(0, |s, &b| s * 10 + (b & 0x0F) as $t);
				let s = s.scan_raw();
				if let Some((&b'-', t)) = s.split_first() { -scan(t) } else { scan(s) }
			}
		}
	)* };
}
macro_rules! impl_parse_uint {
	($($t:ty),*) => { $(
		impl Scan for $t {
			fn scan(s: &mut IO) -> Self {
				s.scan_raw().iter().fold(0, |s, &b| s * 10 + (b & 0x0F) as $t)
			}
		}
	)* };
}
impl_parse_iint!(i32, i64, i128, isize);
impl_parse_uint!(u32, u64, u128, usize);
impl Scan for u8 {
	fn scan(s: &mut IO) -> Self {
		let bytes = s.scan_raw();
		debug_assert_eq!(bytes.len(), 1);
		bytes[0]
	}
}
impl Scan for Bytes {
	fn scan(s: &mut IO) -> Self { s.scan_raw() }
}
impl Scan for Vec<u8> {
	fn scan(s: &mut IO) -> Self { s.scan_raw().to_vec() }
}
macro_rules! impl_tuple {
	() => {};
	($t:ident $($ts:ident)*) => {
		impl<$t: Scan, $($ts: Scan),*> Scan for ($t, $($ts),*) {
			fn scan(s: &mut IO) -> Self { ($t::scan(s), $($ts::scan(s)),*) }
		}
		impl<$t: Print, $($ts: Print),*> Print for ($t, $($ts),*) {
			#[allow(non_snake_case)]
			fn print(w: &mut IO, ($t, $($ts),*): Self) {
				w.print($t);
				$( w.print(" "); w.print($ts); )*
			}
		}
		impl_tuple!($($ts)*);
	};
}
impl_tuple!(A B C D E F G);
macro_rules! impl_scan_array {
	() => {};
	($n:literal $($ns:literal)*) => {
		impl<T: Scan> Scan for [T; $n] {
			fn scan(s: &mut IO) -> Self {
				let mut scan = |_| T::scan(s);
				[scan($n), $(scan($ns)),*]
			}
		}
		// use IO::iterln to print [T; N]
		impl_scan_array!($($ns)*);
	};
}
impl_scan_array!(7 6 5 4 3 2 1);
macro_rules! impl_print_prim {
	($($t:ty),*) => { $(
		impl Print for $t {
			fn print(w: &mut IO, x: Self) {
				w.buf.write_all(format!("{:.10}", x).as_bytes()).unwrap();
			}
		}
		impl Print for &$t {
			fn print(w: &mut IO, x: Self) { w.print(*x); }
		}
	)* };
}
impl_print_prim!(i32, i64, i128, isize, u32, u64, u128, usize, f32, f64);
impl Print for u8 {
	fn print(w: &mut IO, x: Self) { w.buf.write_all(&[x]).unwrap(); }
}
impl Print for &[u8] {
	fn print(w: &mut IO, x: Self) { w.buf.write_all(x).unwrap(); }
}
impl Print for Vec<u8> {
	fn print(w: &mut IO, x: Self) { w.buf.write_all(&x).unwrap(); }
}
impl Print for &str {
	fn print(w: &mut IO, x: Self) { w.print(x.as_bytes()); }
}
#[derive(Debug, Clone, Copy, Default)]
pub struct Usize1(pub usize);
impl Scan for Usize1 {
	fn scan(io: &mut IO) -> Self {
		let n: usize = io.scan();
		Self(n - 1)
	}
}
impl Print for Usize1 {
	fn print(w: &mut IO, x: Self) { w.print(x.0 + 1) }
}

}  // mod io

pub mod iter {


pub trait Itertools: Iterator {
	fn collect_vec(self) -> Vec<Self::Item>
	where
		Self: Sized,
	{
		self.collect()
	}
}

impl<I: Iterator> Itertools for I {}

#[macro_export]
macro_rules! iprod {
	($head:expr) => {
		$head.into_iter()
	};
	($head:expr, $($tail:expr),*) => (
		$head.into_iter().flat_map(|e| {
			std::iter::repeat(e).zip(iprod!($($tail),*))
		})
	);
}

}  // mod iter

pub mod math {

pub mod gcd {

type Int = i32;
type UInt = u32;

pub fn gcd(a: Int, b: Int) -> Int {
	ugcd(a.abs() as _, b.abs() as _) as _
}

// binary gcd
pub fn ugcd(a: UInt, b: UInt) -> UInt {
	#[target_feature(enable = "bmi1")]
	unsafe fn ugcd_impl(mut a: UInt, mut b: UInt) -> UInt {
		if a == 0 {
			return b;
		} else if b == 0 {
			return a;
		}
		let a_shift = a.trailing_zeros();
		a >>= a_shift;
		let b_shift = b.trailing_zeros();
		b >>= b_shift;
		while a != b {
			if a > b {
				std::mem::swap(&mut a, &mut b);
			}
			b -= a;
			b >>= b.trailing_zeros();
		}
		a << a_shift.min(b_shift)
	}
	unsafe {
		ugcd_impl(a, b)
	}
}

/// (x, y, g) where ax + by = g, x >= 0
pub fn extgcd(mut a: Int, mut b: Int) -> (Int, Int, Int) {
	// A = [a, x, y; b, u, v], k = [-1; a0; b0]
	// A'= [a, x, y; 0, u, v] \therefore a0*u + b0*v = 0
	let (mut x, mut y, mut u, mut v) = (1, 0, 0, 1);
	while b != 0 {
		let t = a / b;
		a -= t * b;
		x -= t * u;
		y -= t * v;
		std::mem::swap(&mut a, &mut b);
		std::mem::swap(&mut x, &mut u);
		std::mem::swap(&mut y, &mut v);
	}
	if x < 0 {
		x += u;
		y -= v;
		debug_assert_eq!(gcd(u, v), 1);
		debug_assert!(x + u >= 0);
	}
	(x, y, a)
}

}  // mod gcd

}  // mod math

}  // mod lib