結果
問題 | No.749 クエリ全部盛り |
ユーザー |
|
提出日時 | 2021-09-18 20:44:49 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 1,823 ms / 3,000 ms |
コード長 | 11,330 bytes |
コンパイル時間 | 13,146 ms |
コンパイル使用メモリ | 398,148 KB |
実行使用メモリ | 225,092 KB |
最終ジャッジ日時 | 2024-06-30 18:50:30 |
合計ジャッジ時間 | 24,967 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#[allow(unused_imports)]use std::cmp::*;#[allow(unused_imports)]use std::collections::*;use std::io::{Write, BufWriter};// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8macro_rules! input {($($r:tt)*) => {let stdin = std::io::stdin();let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));let mut next = move || -> String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()};input_inner!{next, $($r)*}};}macro_rules! input_inner {($next:expr) => {};($next:expr, ) => {};($next:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($next, $t);input_inner!{$next $($r)*}};}macro_rules! read_value {($next:expr, ( $($t:tt),* )) => {( $(read_value!($next, $t)),* )};($next:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()};($next:expr, chars) => {read_value!($next, String).chars().collect::<Vec<char>>()};($next:expr, usize1) => (read_value!($next, usize) - 1);($next:expr, [ $t:tt ]) => {{let len = read_value!($next, usize);read_value!($next, [$t; len])}};($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error"));}/// Verified by https://atcoder.jp/contests/abc198/submissions/21774342mod mod_int {use std::ops::*;pub trait Mod: Copy { fn m() -> i64; }#[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]pub struct ModInt<M> { pub x: i64, phantom: ::std::marker::PhantomData<M> }impl<M: Mod> ModInt<M> {// x >= 0pub fn new(x: i64) -> Self { ModInt::new_internal(x % M::m()) }fn new_internal(x: i64) -> Self {ModInt { x: x, phantom: ::std::marker::PhantomData }}pub fn pow(self, mut e: i64) -> Self {debug_assert!(e >= 0);let mut sum = ModInt::new_internal(1);let mut cur = self;while e > 0 {if e % 2 != 0 { sum *= cur; }cur *= cur;e /= 2;}sum}#[allow(dead_code)]pub fn inv(self) -> Self { self.pow(M::m() - 2) }}impl<M: Mod, T: Into<ModInt<M>>> Add<T> for ModInt<M> {type Output = Self;fn add(self, other: T) -> Self {let other = other.into();let mut sum = self.x + other.x;if sum >= M::m() { sum -= M::m(); }ModInt::new_internal(sum)}}impl<M: Mod, T: Into<ModInt<M>>> Sub<T> for ModInt<M> {type Output = Self;fn sub(self, other: T) -> Self {let other = other.into();let mut sum = self.x - other.x;if sum < 0 { sum += M::m(); }ModInt::new_internal(sum)}}impl<M: Mod, T: Into<ModInt<M>>> Mul<T> for ModInt<M> {type Output = Self;fn mul(self, other: T) -> Self { ModInt::new(self.x * other.into().x % M::m()) }}impl<M: Mod, T: Into<ModInt<M>>> AddAssign<T> for ModInt<M> {fn add_assign(&mut self, other: T) { *self = *self + other; }}impl<M: Mod, T: Into<ModInt<M>>> SubAssign<T> for ModInt<M> {fn sub_assign(&mut self, other: T) { *self = *self - other; }}impl<M: Mod, T: Into<ModInt<M>>> MulAssign<T> for ModInt<M> {fn mul_assign(&mut self, other: T) { *self = *self * other; }}impl<M: Mod> Neg for ModInt<M> {type Output = Self;fn neg(self) -> Self { ModInt::new(0) - self }}impl<M> ::std::fmt::Display for ModInt<M> {fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {self.x.fmt(f)}}impl<M: Mod> ::std::fmt::Debug for ModInt<M> {fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {let (mut a, mut b, _) = red(self.x, M::m());if b < 0 {a = -a;b = -b;}write!(f, "{}/{}", a, b)}}impl<M: Mod> From<i64> for ModInt<M> {fn from(x: i64) -> Self { Self::new(x) }}// Finds the simplest fraction x/y congruent to r mod p.// The return value (x, y, z) satisfies x = y * r + z * p.fn red(r: i64, p: i64) -> (i64, i64, i64) {if r.abs() <= 10000 {return (r, 1, 0);}let mut nxt_r = p % r;let mut q = p / r;if 2 * nxt_r >= r {nxt_r -= r;q += 1;}if 2 * nxt_r <= -r {nxt_r += r;q -= 1;}let (x, z, y) = red(nxt_r, r);(x, y - q * z, z)}} // mod mod_intmacro_rules! define_mod {($struct_name: ident, $modulo: expr) => {#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]struct $struct_name {}impl mod_int::Mod for $struct_name { fn m() -> i64 { $modulo } }}}const MOD: i64 = 1_000_000_007;define_mod!(P, MOD);type MInt = mod_int::ModInt<P>;/*** Lazy Segment Tree. This data structure is useful for fast folding and updating on intervals of an array* whose elements are elements of monoid T. Note that constructing this tree requires the identity* element of T and the operation of T. This is monomorphised, because of efficiency. T := i64, biop = max, upop = (+)* Reference: http://d.hatena.ne.jp/kyuridenamida/20121114/1352835261* Verified by https://codeforces.com/contest/1114/submission/49759034*/pub trait ActionRing {type T: Clone + Copy; // datatype U: Clone + Copy + PartialEq + Eq; // actionfn biop(x: Self::T, y: Self::T) -> Self::T;fn update(x: Self::T, a: Self::U, height: usize) -> Self::T;fn upop(fst: Self::U, snd: Self::U) -> Self::U;fn e() -> Self::T;fn upe() -> Self::U; // identity for upop}pub struct LazySegTree<R: ActionRing> {n: usize,dep: usize,dat: Vec<R::T>,lazy: Vec<R::U>,}impl<R: ActionRing> LazySegTree<R> {pub fn new(a: &[R::T]) -> Self {let n_ = a.len();let mut n = 1;let mut dep = 0;while n < n_ { n *= 2; dep += 1; } // n is a power of 2let mut dat = vec![R::e(); 2 * n - 1];for i in 0..n_ {dat[n - 1 + i] = a[i];}for i in (0..n - 1).rev() {dat[i] = R::biop(dat[2 * i + 1], dat[2 * i + 2]);}LazySegTree {n: n,dep: dep,dat: dat,lazy: vec![R::upe(); 2 * n - 1],}}#[inline]fn lazy_evaluate_node(&mut self, k: usize, height: usize) {if self.lazy[k] == R::upe() { return; }self.dat[k] = R::update(self.dat[k], self.lazy[k], height);if k < self.n - 1 {self.lazy[2 * k + 1] = R::upop(self.lazy[2 * k + 1], self.lazy[k]);self.lazy[2 * k + 2] = R::upop(self.lazy[2 * k + 2], self.lazy[k]);}self.lazy[k] = R::upe(); // identity for upop}#[inline]fn update_node(&mut self, k: usize) {self.dat[k] = R::biop(self.dat[2 * k + 1], self.dat[2 * k + 2]);}fn update_sub(&mut self, a: usize, b: usize, v: R::U, k: usize, height: usize, l: usize, r: usize) {self.lazy_evaluate_node(k, height);// [a,b) and [l,r) intersects?if r <= a || b <= l {return;}if a <= l && r <= b {self.lazy[k] = R::upop(self.lazy[k], v);self.lazy_evaluate_node(k, height);return;}self.update_sub(a, b, v, 2 * k + 1, height - 1, l, (l + r) / 2);self.update_sub(a, b, v, 2 * k + 2, height - 1, (l + r) / 2, r);self.update_node(k);}/* ary[i] = upop(ary[i], v) for i in [a, b) (half-inclusive) */#[inline]pub fn update(&mut self, a: usize, b: usize, v: R::U) {let n = self.n;let dep = self.dep;self.update_sub(a, b, v, 0, dep, 0, n);}/* l,r are for simplicity */fn query_sub(&mut self, a: usize, b: usize, k: usize, height: usize, l: usize, r: usize) -> R::T {self.lazy_evaluate_node(k, height);// [a,b) and [l,r) intersect?if r <= a || b <= l {return R::e();}if a <= l && r <= b {return self.dat[k];}let vl = self.query_sub(a, b, 2 * k + 1, height - 1, l, (l + r) / 2);let vr = self.query_sub(a, b, 2 * k + 2, height - 1, (l + r) / 2, r);self.update_node(k);R::biop(vl, vr)}/* [a, b) (note: half-inclusive) */#[inline]pub fn query(&mut self, a: usize, b: usize) -> R::T {let n = self.n;let dep = self.dep;self.query_sub(a, b, 0, dep, 0, n)}}enum V {}const B: usize = 3;impl ActionRing for V {type T = [MInt; B]; // datatype U = [[MInt; B]; B]; // action, (a, b) |-> x |-> ax + bfn biop(x: Self::T, y: Self::T) -> Self::T {let mut ans = [0.into(); B];for i in 0..B {ans[i] = x[i] + y[i];}ans}fn update(x: Self::T, o: Self::U, _height: usize) -> Self::T {let mut ans = [0.into(); B];for i in 0..B {for j in 0..B {ans[j] += x[i] * o[i][j];}}ans}fn upop(fst: Self::U, snd: Self::U) -> Self::U {let mut ans = [[0.into(); B]; B];for i in 0..B {for j in 0..B {for k in 0..B {ans[i][k] += fst[i][j] * snd[j][k];}}}ans}fn e() -> Self::T {[0.into(); B]}fn upe() -> Self::U { // identity for upoplet mut ans = [[0.into(); B]; B];for i in 0..B {ans[i][i] = 1.into();}ans}}fn main() {let out = std::io::stdout();let mut out = BufWriter::new(out.lock());macro_rules! puts {($($format:tt)*) => (let _ = write!(out,$($format)*););}input! {n: usize, q: usize,qlrk: [(i32, usize, usize, i64); q],}let mut a = vec![[MInt::new(0); 3]; n];for i in 0..n {a[i][2] = 1.into();}if n >= 2 {a[1][1] = 1.into();}for i in 2..n {a[i][1] = a[i - 1][1] + a[i - 2][1];}let mut st = LazySegTree::<V>::new(&a);let mut init = [[MInt::new(0); 3]; 3];init[1][1] = 1.into();init[2][2] = 1.into();for (q, l, r, k) in qlrk {let r = r + 1;if q == 0 {puts!("{}\n", st.query(l, r)[0] * k);} else if q == 1 {let mut mat = init;mat[2][0] = k.into();st.update(l, r, mat);} else if q == 2 {let mut mat = init;mat[0][0] = 1.into();mat[2][0] = k.into();st.update(l, r, mat);} else if q == 3 {let mut mat = init;mat[0][0] = k.into();st.update(l, r, mat);} else {let mut mat = init;mat[0][0] = 1.into();mat[1][0] = k.into();st.update(l, r, mat);}}}