結果
| 問題 |
No.749 クエリ全部盛り
|
| ユーザー |
 LyricalMaestro
|
| 提出日時 | 2025-05-24 20:10:03 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 986 ms / 3,000 ms |
| コード長 | 7,396 bytes |
| コンパイル時間 | 13,031 ms |
| コンパイル使用メモリ | 398,064 KB |
| 実行使用メモリ | 231,972 KB |
| 最終ジャッジ日時 | 2025-05-24 20:10:25 |
| 合計ジャッジ時間 | 16,870 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 20 |
コンパイルメッセージ
warning: variable does not need to be mutable --> src/main.rs:21:13 | 21 | let mut lazy_array = vec![UNIT_MATRIX; 2 * n]; | ----^^^^^^^^^^ | | | help: remove this `mut` | = note: `#[warn(unused_mut)]` on by default
ソースコード
use std::io::{self, BufRead};
const MOD: i64 = 1_000_000_007;
const UNIT_MATRIX: [i64; 9] = [1, 0, 0, 0, 1, 0, 0, 0, 1];
struct LazySegmentTree {
size: usize,
array: Vec<[i64; 3]>,
lazy_array: Vec<[i64; 9]>,
tmp_matrix: [i64; 9],
tmp_vector: [i64; 3],
}
impl LazySegmentTree {
fn new(init_array: &[[i64; 3]]) -> Self {
let mut n = 1;
while n < init_array.len() {
n *= 2;
}
let mut array = vec![[0; 3]; 2 * n];
let mut lazy_array = vec![UNIT_MATRIX; 2 * n];
for (i, &a) in init_array.iter().enumerate() {
array[n + i] = a;
}
for i in (1..n).rev() {
let left = array[2 * i];
let right = array[2 * i + 1];
let mut current = array[i];
Self::op(&mut current, &left, &right);
array[i] = current;
}
LazySegmentTree {
size: n,
array,
lazy_array,
tmp_matrix: [0; 9],
tmp_vector: [0; 3],
}
}
fn op(res: &mut [i64; 3], left: &[i64; 3], right: &[i64; 3]) {
for i in 0..3 {
res[i] = (left[i] + right[i]) % MOD;
}
}
fn op2(&mut self, matrix: &[i64; 9], array: &mut [i64; 9]) {
for i in 0..3 {
for j in 0..3 {
let mut y = 0;
for k in 0..3 {
y = (y + matrix[i * 3 + k] * array[k * 3 + j]) % MOD;
}
self.tmp_matrix[i * 3 + j] = y;
}
}
array.copy_from_slice(&self.tmp_matrix);
}
fn op3(&mut self, matrix: &[i64; 9], array: &mut [i64; 3]) {
for i in 0..3 {
let mut y = 0;
for j in 0..3 {
y = (y + matrix[i * 3 + j] * array[j]) % MOD;
}
self.tmp_vector[i] = y;
}
array.copy_from_slice(&self.tmp_vector);
}
fn is_unit_matrix(array: &[i64; 9]) -> bool {
array == &UNIT_MATRIX
}
fn propagate(&mut self, i: usize) {
if Self::is_unit_matrix(&self.lazy_array[i]) {
return;
}
let v = self.lazy_array[i];
if i < self.size {
let mut left_lazy = self.lazy_array[2 * i];
let mut right_lazy = self.lazy_array[2 * i + 1];
self.op2(&v, &mut left_lazy);
self.op2(&v, &mut right_lazy);
self.lazy_array[2 * i] = left_lazy;
self.lazy_array[2 * i + 1] = right_lazy;
let mut left_array = self.array[2 * i];
let mut right_array = self.array[2 * i + 1];
self.op3(&v, &mut left_array);
self.op3(&v, &mut right_array);
self.array[2 * i] = left_array;
self.array[2 * i + 1] = right_array;
}
self.lazy_array[i] = UNIT_MATRIX;
}
fn get_target_indices(&self, l: usize, r: usize) -> Vec<usize> {
let mut ids = vec![];
let mut l = l + self.size;
let mut r = r + self.size;
let lm = (l / (l & l.wrapping_neg())) >> 1;
let rm = (r / (r & r.wrapping_neg())) >> 1;
while 0 < l && l < r {
if r <= rm {
ids.push(r);
}
if l <= lm {
ids.push(l);
}
l >>= 1;
r >>= 1;
}
while l > 0 {
ids.push(l);
l >>= 1;
}
ids
}
fn add(&mut self, l: usize, r: usize, x: &[i64; 9]) {
let ids = self.get_target_indices(l, r);
for &i in ids.iter().rev() {
self.propagate(i);
}
let mut l = self.size + l;
let mut r = self.size + r;
while l < r {
if r & 1 != 0 {
r -= 1;
let mut lazy = self.lazy_array[r];
let mut arr = self.array[r];
self.op2(x, &mut lazy);
self.op3(x, &mut arr);
self.lazy_array[r] = lazy;
self.array[r] = arr;
}
if l & 1 != 0 {
let mut lazy = self.lazy_array[l];
let mut arr = self.array[l];
self.op2(x, &mut lazy);
self.op3(x, &mut arr);
self.lazy_array[l] = lazy;
self.array[l] = arr;
l += 1;
}
l >>= 1;
r >>= 1;
}
for &i in ids.iter() {
if i < self.size {
let left = self.array[2 * i];
let right = self.array[2 * i + 1];
let mut current = self.array[i];
Self::op(&mut current, &left, &right);
self.array[i] = current;
}
}
}
fn get_max(&mut self, l: usize, r: usize) -> [i64; 3] {
for &i in self.get_target_indices(l, r).iter().rev() {
self.propagate(i);
}
let mut l = l + self.size;
let mut r = r + self.size;
let mut s = [0; 3];
while l < r {
if r & 1 != 0 {
r -= 1;
let val = self.array[r];
let temp_s = s;
Self::op(&mut s, &temp_s, &val);
}
if l & 1 != 0 {
let val = self.array[l];
let temp_s = s;
Self::op(&mut s, &temp_s, &val);
l += 1;
}
l >>= 1;
r >>= 1;
}
s
}
}
fn main() {
let stdin = io::stdin();
let mut lines = stdin.lock().lines();
let first_line = lines.next().unwrap().unwrap();
let mut it = first_line.split_whitespace();
let n: usize = it.next().unwrap().parse().unwrap();
let q: usize = it.next().unwrap().parse().unwrap();
let mut queries = vec![];
for _ in 0..q {
let line = lines.next().unwrap().unwrap();
let mut it = line.split_whitespace();
let t = it.next().unwrap().parse::<usize>().unwrap();
let l = it.next().unwrap().parse::<usize>().unwrap();
let r = it.next().unwrap().parse::<usize>().unwrap();
let k = it.next().unwrap().parse::<i64>().unwrap();
queries.push((t, l, r, k));
}
let mut fibo = vec![0; n];
if n > 1 {
fibo[1] = 1;
}
for i in 2..n {
fibo[i] = (fibo[i - 1] + fibo[i - 2]) % MOD;
}
let mut array = vec![[0, 1, 0]; n];
for i in 0..n {
array[i][2] = fibo[i];
}
let mut tree = LazySegmentTree::new(&array);
let mut matrix1 = [0, -1, 0, 0, 1, 0, 0, 0, 1];
let mut matrix2 = [1, -1, 0, 0, 1, 0, 0, 0, 1];
let mut matrix3 = [-1, 0, 0, 0, 1, 0, 0, 0, 1];
let mut matrix4 = [1, 0, -1, 0, 1, 0, 0, 0, 1];
for (t, l, r, k) in queries {
match t {
0 => {
let s = tree.get_max(l, r + 1);
println!("{}", (s[0] * k) % MOD);
}
1 => {
matrix1[1] = k;
tree.add(l, r + 1, &matrix1);
}
2 => {
matrix2[1] = k;
tree.add(l, r + 1, &matrix2);
}
3 => {
matrix3[0] = k;
tree.add(l, r + 1, &matrix3);
}
4 => {
matrix4[2] = k;
tree.add(l, r + 1, &matrix4);
}
_ => {}
}
}
}