結果
| 問題 | No.3507 RangeSum RangeUpdate RangeSqrt |
| コンテスト | |
| ユーザー |
 akakimidori
|
| 提出日時 | 2026-04-18 11:07:56 |
| 言語 | Rust (1.94.0 + proconio + num + itertools) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,569 bytes |
| 記録 | |
| コンパイル時間 | 5,788 ms |
| コンパイル使用メモリ | 221,612 KB |
| 実行使用メモリ | 17,628 KB |
| 最終ジャッジ日時 | 2026-04-18 11:08:20 |
| 合計ジャッジ時間 | 15,435 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 24 WA * 5 |
コンパイルメッセージ
warning: type alias `Map` is never used
--> src/main.rs:123:6
|
123 | type Map<K, V> = BTreeMap<K, V>;
| ^^^
|
= note: `#[warn(dead_code)]` (part of `#[warn(unused)]`) on by default
warning: type alias `Set` is never used
--> src/main.rs:124:6
|
124 | type Set<T> = BTreeSet<T>;
| ^^^
warning: type alias `Deque` is never used
--> src/main.rs:125:6
|
125 | type Deque<T> = VecDeque<T>;
| ^^^^^
ソースコード
// 0<=l<=r<=N ?
// l<r のtypo?
fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {
let n = sc.next::<usize>();
let q = sc.next::<usize>();
let mut map = std::collections::BTreeMap::new();
let mut seg = LazySegmentTree::build((0..n).map(|_| (0, 1)), n, R);
for i in 0..n {
let a = sc.next::<i64>();
map.insert(i, (i + 1, a));
seg.update(i, i + 1, a);
}
for _ in 0..q {
let op = sc.next::<u32>();
let l = sc.next::<usize>();
let r = sc.next::<usize>();
if op == 0 {
writeln!(out, "{}", seg.find(l, r).0).ok();
} else if op == 1 {
let v = sc.next::<i64>();
for &x in [l, r].iter() {
if let Some((&s, &(t, a))) = map.range(..x).next_back() {
if t > x {
map.remove(&s);
map.insert(s, (x, a));
map.insert(x, (t, a));
}
}
}
while let Some((&s, _)) = map.range(l..r).next() {
map.remove(&s);
}
map.insert(l, (r, v));
seg.update(l, r, v);
} else {
for &x in [l, r].iter() {
if let Some((&s, &(t, a))) = map.range(..x).next_back() {
if t > x {
map.remove(&s);
map.insert(s, (x, a));
map.insert(x, (t, a));
}
}
}
let mut memo = vec![];
while let Some((&s, &(t, a))) = map.range(l..r).next() {
map.remove(&s);
let na = (a as f64).sqrt().floor() as i64;
seg.update(s, t, na);
if na > 1 {
memo.push((s, t, na));
}
}
for (s, t, v) in memo {
map.insert(s, (t, v));
}
}
}
}
struct R;
impl TE for R {
type T = (i64, i64);
type E = i64;
fn fold(&self, l: &Self::T, r: &Self::T) -> Self::T {
(l.0 + r.0, l.1 + r.1)
}
fn eval(&self, x: &Self::T, f: &Self::E) -> Self::T {
if *f == -1 {
*x
} else {
(*f * x.1, x.1)
}
}
fn merge(&self, g: &Self::E, h: &Self::E) -> Self::E {
if *h == -1 {
*g
} else {
*h
}
}
fn e(&self) -> Self::T {
(0, 0)
}
fn id(&self) -> Self::E {
-1
}
}
// ---------- begin scannner ----------
#[allow(dead_code)]
mod scanner {
use std::str::FromStr;
pub struct Scanner<'a> {
it: std::str::SplitWhitespace<'a>,
}
impl<'a> Scanner<'a> {
pub fn new(s: &'a String) -> Scanner<'a> {
Scanner {
it: s.split_whitespace(),
}
}
pub fn next<T: FromStr>(&mut self) -> T {
self.it.next().unwrap().parse::<T>().ok().unwrap()
}
pub fn next_bytes(&mut self) -> Vec<u8> {
self.it.next().unwrap().bytes().collect()
}
pub fn next_chars(&mut self) -> Vec<char> {
self.it.next().unwrap().chars().collect()
}
pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
(0..len).map(|_| self.next()).collect()
}
}
}
// ---------- end scannner ----------
use std::io::Write;
use std::collections::*;
type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;
fn main() {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
let mut sc = scanner::Scanner::new(&s);
let out = std::io::stdout();
let mut out = std::io::BufWriter::new(out.lock());
run(&mut sc, &mut out);
}
// ---------- begin Lazy Segment Tree ----------
pub trait TE {
type T: Clone;
type E: Clone;
fn fold(&self, l: &Self::T, r: &Self::T) -> Self::T;
fn eval(&self, x: &Self::T, f: &Self::E) -> Self::T;
fn merge(&self, g: &Self::E, h: &Self::E) -> Self::E;
fn e(&self) -> Self::T;
fn id(&self) -> Self::E;
}
pub struct LazySegmentTree<R: TE> {
n: usize,
size: usize,
bit: u32,
op: R,
data: Vec<(R::T, R::E)>,
}
impl<R: TE> LazySegmentTree<R> {
pub fn new(n: usize, op: R) -> Self {
assert!(n > 0);
let size = n.next_power_of_two();
let bit = size.trailing_zeros();
let data = vec![(op.e(), op.id()); 2 * size];
Self {
n,
size,
bit,
op,
data,
}
}
pub fn build<I>(init: I, n: usize, op: R) -> Self
where
I: Iterator<Item = R::T>,
{
let mut seg = Self::new(n, op);
for (data, ini) in seg.data[seg.size..].iter_mut().zip(init) {
data.0 = ini;
}
for i in (1..seg.size).rev() {
seg.pull(i);
}
seg
}
pub fn update(&mut self, l: usize, r: usize, f: R::E) {
assert!(l <= r && r <= self.n);
if l == r {
return;
}
self.push_range(l, r);
let mut s = l + self.size;
let mut t = r + self.size;
while s < t {
if s & 1 == 1 {
self.apply(s, &f);
s += 1;
}
if t & 1 == 1 {
t -= 1;
self.apply(t, &f);
}
s >>= 1;
t >>= 1;
}
let l = l + self.size;
let r = r + self.size;
for k in 1..=self.bit {
if (l >> k) << k != l {
self.pull(l >> k);
}
if (r >> k) << k != r {
self.pull((r - 1) >> k);
}
}
}
pub fn find(&mut self, l: usize, r: usize) -> R::T {
assert!(l <= r && r <= self.n);
if l == r {
return self.op.e();
}
self.push_range(l, r);
let mut l = l + self.size;
let mut r = r + self.size;
let mut p = self.op.e();
let mut q = self.op.e();
while l < r {
if l & 1 == 1 {
p = self.op.fold(&p, &self.data[l].0);
l += 1;
}
if r & 1 == 1 {
r -= 1;
q = self.op.fold(&self.data[r].0, &q);
}
l >>= 1;
r >>= 1;
}
self.op.fold(&p, &q)
}
pub fn set_at(&mut self, x: usize, v: R::T) {
assert!(x < self.n);
let x = x + self.size;
for k in (1..=self.bit).rev() {
self.push(x >> k);
}
self.data[x].0 = v;
for k in 1..=self.bit {
self.pull(x >> k);
}
}
pub fn max_right<P>(&mut self, l: usize, f: P) -> usize
where
P: Fn(&R::T) -> bool,
{
assert!(l <= self.n);
assert!(f(&self.op.e()));
if l == self.n {
return self.n;
}
self.push_range(l, self.n);
let mut l = l + self.size;
let mut sum = self.op.e();
while {
l >>= l.trailing_zeros();
let v = self.op.fold(&sum, &self.data[l].0);
if !f(&v) {
while l < self.size {
self.push(l);
l <<= 1;
let v = self.op.fold(&sum, &self.data[l].0);
if f(&v) {
sum = v;
l += 1;
}
}
return l - self.size;
}
sum = v;
l += 1;
l.count_ones() > 1
} {}
self.n
}
pub fn min_left<P>(&mut self, r: usize, f: P) -> usize
where
P: Fn(&R::T) -> bool,
{
assert!(r <= self.n);
assert!(f(&self.op.e()));
if r == 0 {
return 0;
}
self.push_range(0, r);
let mut r = r + self.size;
let mut sum = self.op.e();
while {
r -= 1;
while r > 1 && r & 1 == 1 {
r >>= 1;
}
let v = self.op.fold(&self.data[r].0, &sum);
if !f(&v) {
while r < self.size {
self.push(r);
r = 2 * r + 1;
let v = self.op.fold(&self.data[r].0, &sum);
if f(&v) {
sum = v;
r -= 1;
}
}
return r + 1 - self.size;
}
sum = v;
(r & (!r + 1)) != r
} {}
0
}
fn push_range(&mut self, l: usize, r: usize) {
let l = l + self.size;
let r = r + self.size;
for k in (1..(self.bit + 1)).rev() {
if (l >> k) << k != l {
self.push(l >> k);
}
if (r >> k) << k != r {
self.push((r - 1) >> k);
}
}
}
fn apply(&mut self, x: usize, f: &R::E) {
self.data[x].0 = self.op.eval(&self.data[x].0, f);
self.data[x].1 = self.op.merge(&self.data[x].1, f);
}
fn push(&mut self, x: usize) {
let f = std::mem::replace(&mut self.data[x].1, self.op.id());
self.apply(2 * x, &f);
self.apply(2 * x + 1, &f);
}
fn pull(&mut self, x: usize) {
self.data[x].0 = self.op.fold(&self.data[2 * x].0, &self.data[2 * x + 1].0);
}
}
// ---------- end Lazy Segment Tree ----------