結果
| 問題 | No.3507 RangeSum RangeUpdate RangeSqrt |
| コンテスト | |
| ユーザー |
 titia
|
| 提出日時 | 2026-06-18 03:47:18 |
| 言語 | Rust (1.94.0 + proconio + num + itertools) |
| 結果 |
AC
|
| 実行時間 | 481 ms / 2,000 ms |
| コード長 | 6,950 bytes |
| 記録 | |
| コンパイル時間 | 1,403 ms |
| コンパイル使用メモリ | 193,192 KB |
| 実行使用メモリ | 7,296 KB |
| 最終ジャッジ日時 | 2026-06-18 03:47:30 |
| 合計ジャッジ時間 | 10,879 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 30 |
ソースコード
use std::io::{self, Read};
fn main() {
let mut s = String::new();
io::stdin().read_to_string(&mut s).unwrap();
let mut it = s.split_whitespace();
let n: usize = it.next().unwrap().parse().unwrap();
let q: usize = it.next().unwrap().parse().unwrap();
let mut a: Vec<i64> = (0..n)
.map(|_| it.next().unwrap().parse().unwrap())
.collect();
let sq = (n as f64).sqrt() as usize;
let len = (n + sq - 1) / sq;
let mut unit = vec![-1_i64; len];
let mut sum = vec![0_i64; len];
let mut one_or_zero = vec![0_i32; len];
for b in 0..len {
let mut one: i64 = -1;
let mut oneflag = 1;
let l = b * sq;
let r = std::cmp::min(n, l + sq);
for j in l..r {
if a[j] >= 2 {
oneflag = 0;
}
if one == -1 {
one = a[j];
} else if one == a[j] {
} else {
one = -2;
}
sum[b] += a[j];
}
if one >= 0 {
unit[b] = one;
}
one_or_zero[b] = oneflag;
}
let mut answers: Vec<i64> = Vec::new();
for _ in 0..q {
let typ: i32 = it.next().unwrap().parse().unwrap();
if typ == 0 {
let l: usize = it.next().unwrap().parse().unwrap();
let r: usize = it.next().unwrap().parse().unwrap();
let mut ans = 0_i64;
let mut now = l;
while now < r && now % sq != 0 {
let b = now / sq;
if unit[b] != -1 {
ans += unit[b];
} else {
ans += a[now];
}
now += 1;
}
while now < r && now + sq < r {
ans += sum[now / sq];
now += sq;
}
while now < r {
let b = now / sq;
if unit[b] != -1 {
ans += unit[b];
} else {
ans += a[now];
}
now += 1;
}
answers.push(ans);
} else if typ == 1 {
let l: usize = it.next().unwrap().parse().unwrap();
let r: usize = it.next().unwrap().parse().unwrap();
let x: i64 = it.next().unwrap().parse().unwrap();
let mut now = l;
while now < r && now % sq != 0 {
let b = now / sq;
if unit[b] != -1 {
let ume = unit[b];
unit[b] = -1;
sum[b] = 0;
let bl = b * sq;
let br = std::cmp::min(n, bl + sq);
for i in bl..br {
a[i] = ume;
sum[b] += a[i];
}
}
if x >= 2 {
one_or_zero[b] = 0;
}
sum[b] -= a[now];
a[now] = x;
sum[b] += a[now];
now += 1;
}
while now < r && now + sq < r {
let b = now / sq;
unit[b] = x;
if x <= 1 {
one_or_zero[b] = 1;
} else {
one_or_zero[b] = 0;
}
sum[b] = x * sq as i64;
now += sq;
}
while now < r {
let b = now / sq;
if unit[b] != -1 {
let ume = unit[b];
unit[b] = -1;
sum[b] = 0;
let bl = b * sq;
let br = std::cmp::min(n, bl + sq);
for i in bl..br {
a[i] = ume;
sum[b] += a[i];
}
}
if x >= 2 {
one_or_zero[b] = 0;
}
sum[b] -= a[now];
a[now] = x;
sum[b] += a[now];
now += 1;
}
} else {
let l: usize = it.next().unwrap().parse().unwrap();
let r: usize = it.next().unwrap().parse().unwrap();
let mut now = l;
while now < r && now % sq != 0 {
let b = now / sq;
if unit[b] != -1 {
let ume = unit[b];
unit[b] = -1;
sum[b] = 0;
let bl = b * sq;
let br = std::cmp::min(n, bl + sq);
for i in bl..br {
a[i] = ume;
sum[b] += a[i];
}
}
sum[b] -= a[now];
a[now] = ((a[now] as f64).sqrt()) as i64;
sum[b] += a[now];
now += 1;
}
while now < r && now + sq < r {
let b = now / sq;
if one_or_zero[b] == 1 {
now += sq;
} else if unit[b] != -1 {
let ume = ((unit[b] as f64).sqrt()) as i64;
unit[b] = ume;
sum[b] = ume * sq as i64;
now += sq;
} else {
let mut one: i64 = -1;
sum[b] = 0;
let mut oneflag = 1;
for i in now..(now + sq) {
a[i] = ((a[i] as f64).sqrt()) as i64;
sum[b] += a[i];
if a[i] >= 2 {
oneflag = 0;
}
if one == -1 {
one = a[i];
} else if one == a[i] {
} else {
one = -2;
}
}
if one >= 0 {
unit[b] = one;
sum[b] = one * sq as i64;
}
one_or_zero[b] = oneflag;
now += sq;
}
}
while now < r {
let b = now / sq;
if unit[b] != -1 {
let ume = unit[b];
unit[b] = -1;
sum[b] = 0;
let bl = b * sq;
let br = std::cmp::min(n, bl + sq);
for i in bl..br {
a[i] = ume;
sum[b] += a[i];
}
}
sum[b] -= a[now];
a[now] = ((a[now] as f64).sqrt()) as i64;
sum[b] += a[now];
now += 1;
}
}
}
let mut out = String::new();
for v in answers {
out.push_str(&format!("{}\n", v));
}
print!("{}", out);
}