結果
| 問題 | No.3507 RangeSum RangeUpdate RangeSqrt |
| コンテスト | |
| ユーザー |
 rhoo
|
| 提出日時 | 2026-03-20 22:47:30 |
| 言語 | Rust (1.94.0 + proconio + num + itertools) |
| 結果 |
AC
|
| 実行時間 | 255 ms / 2,000 ms |
| コード長 | 11,005 bytes |
| 記録 | |
| コンパイル時間 | 2,891 ms |
| コンパイル使用メモリ | 214,548 KB |
| 実行使用メモリ | 16,324 KB |
| 最終ジャッジ日時 | 2026-04-17 19:43:07 |
| 合計ジャッジ時間 | 9,209 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 29 |
コンパイルメッセージ
warning: associated items `new`, `set`, `get`, `max_right`, and `min_left` are never used
--> src/main.rs:155:8
|
154 | impl<F:MapMonoid> LazySegtree<F>{
| -------------------------------- associated items in this implementation
155 | fn new(n:usize)->Self{
| ^^^
...
182 | fn set(&mut self,mut i:usize,v:<F::M as Monoid>::S){
| ^^^
...
195 | fn get(&self,mut i:usize)-><F::M as Monoid>::S{
| ^^^
...
313 | fn max_right(&self,mut l:usize,mut f:impl FnMut(<F::M as Monoid>::S)->bool)->usize{
| ^^^^^^^^^
...
350 | fn min_left(&mut self,mut r:usize,mut f:impl FnMut(<F::M as Monoid>::S)->bool)->usize{
| ^^^^^^^^
|
= note: `#[warn(dead_code)]` (part of `#[warn(unused)]`) on by default
ソースコード
#![allow(non_snake_case)]
fn main(){
use proconio::*;
input!{
n:usize,
q:usize,
a:[usize;n],
}
type T=(usize,usize); // val, len
impl_monoid!(M,T,(0,0),|a:T,b:T|(a.0+b.0,a.1+b.1));
impl_mapmonoid!(F,M,usize,!0,|v:T,f:usize|if f!=!0{(v.1*f,v.1)}else{v},|new:usize,old:usize|if new==!0{old}else{new});
let mut seg=LazySegtree::<F>::from(a.iter().map(|&a|(a,1)).collect_vec());
#[derive(Clone,Copy,PartialEq,Eq,PartialOrd,Ord)]
struct Item{
l:usize,
r:usize,
v:usize,
}
impl Item{
fn new(l:usize)->Item{
Item{l,r:0,v:0}
}
}
let mut set=std::collections::BTreeSet::<Item>::new();
for i in 0..n{
if a[i]>1{
set.insert(Item{l:i,r:i+1,v:a[i]});
}
}
let mut rem=vec![];
for _ in 0..q{
input!{
t:usize,
}
match t{
0=>{
input!{
l:usize,
r:usize,
}
// sum of l..r
let ans=seg.prod(l..r).0;
print!("{}\n",ans);
},
1=>{
input!{
l:usize,
r:usize,
x:usize,
}
// assign x for l..r
seg.apply(l..r,x);
rem.clear();
rem.extend(set.range(..Item::new(l)).last().copied());
rem.extend(set.range(Item::new(l)..Item::new(r)).copied());
for &item in &rem{
if item.r<=l || r<=item.l{
continue;
}
set.remove(&item);
if item.l<=l && l<item.r{
set.insert(Item{r:l,..item});
}
if item.l<=r && r<item.r{
set.insert(Item{l:r,..item});
}
}
if x>1{
set.insert(Item{l,r,v:x});
}
},
2=>{
input!{
l:usize,
r:usize,
}
// sqrt l..r
rem.clear();
rem.extend(set.range(..Item::new(l)).last().copied());
rem.extend(set.range(Item::new(l)..Item::new(r)).copied());
for &item in &rem{
if item.r<=l || r<=item.l{
continue;
}
set.remove(&item);
if item.l<=l && l<item.r{
set.insert(Item{r:l,..item});
}
if item.l<=r && r<item.r{
set.insert(Item{l:r,..item});
}
let l=item.l.max(l);
let r=item.r.min(r);
let nv=item.v.isqrt();
seg.apply(l..r,nv);
if nv>1{
set.insert(Item{l,r,v:nv});
}
}
},
_=>panic!(),
}
}
}
use itertools::*;
// Compは(new,old)の順に引数を取る
#[derive(Clone)]
struct LazySegtree<F:MapMonoid>{
n:usize,
size:usize,
log:usize,
a:Vec<std::cell::Cell<<F::M as Monoid>::S>>,
lazy:Vec<std::cell::Cell<F::F>>,
}
impl<F:MapMonoid> From<Vec<<F::M as Monoid>::S>> for LazySegtree<F>{
fn from(v:Vec<<F::M as Monoid>::S>)->Self{
let n=v.len();
let size=n.next_power_of_two();
let log=size.trailing_zeros() as usize;
let mut a=vec![std::cell::Cell::new(F::M::e());2*size];
let mut it=v.iter().map(|&a|std::cell::Cell::new(a));
a[size..size+n].fill_with(||it.next().unwrap());
for i in (1..size).rev(){
a[i].set(F::M::op(a[i*2].get(),a[i*2+1].get()));
}
LazySegtree{
n,size,log,
a,lazy:vec![std::cell::Cell::new(F::id());size],
}
}
}
impl<F:MapMonoid> LazySegtree<F>{
fn new(n:usize)->Self{
let size=n.next_power_of_two();
let log=size.trailing_zeros() as usize;
Self{
n,size,log,
a:vec![std::cell::Cell::new(F::M::e());size*2],
lazy:vec![std::cell::Cell::new(F::id());size],
}
}
fn update(&self,k:usize){
self.a[k].set(F::M::op(self.a[2*k].get(),self.a[2*k+1].get()));
}
fn apply_node(&self,k:usize,f:F::F){
self.a[k].set(F::map(self.a[k].get(),f));
if k<self.size{
self.lazy[k].set(F::comp(f,self.lazy[k].get()));
}
}
fn push(&self,k:usize){
self.apply_node(2*k,self.lazy[k].get());
self.apply_node(2*k+1,self.lazy[k].get());
self.lazy[k].set(F::id());
}
fn set(&mut self,mut i:usize,v:<F::M as Monoid>::S){
assert!(i<self.n);
i+=self.size;
for k in (1..=self.log).rev(){
self.push(i>>k);
}
self.a[i].set(v);
for k in 1..=self.log{
self.update(i>>k);
}
}
fn get(&self,mut i:usize)-><F::M as Monoid>::S{
assert!(i<self.n);
i+=self.size;
for k in (1..=self.log).rev(){
self.push(i>>k);
}
self.a[i].get()
}
fn prod(&self,range:impl std::ops::RangeBounds<usize>)-><F::M as Monoid>::S{
use std::ops::Bound::*;
let mut u=match range.start_bound(){
Included(&a)=>a,
Excluded(&a)=>a+1,
Unbounded=>0,
};
let mut v=match range.end_bound(){
Included(&a)=>a+1,
Excluded(&a)=>a,
Unbounded=>self.n,
};
assert!(u<=v && v<=self.n);
if (u,v)==(0,self.n){
return self.a[1].get();
}
if u==v{
return F::M::e();
}
u+=self.size;
v+=self.size;
for i in (1..=self.log).rev(){
if u&!0<<i!=u{
self.push(u>>i);
}
if v&!0<<i!=v{
self.push(v>>i);
}
}
let mut um=F::M::e();
let mut vm=F::M::e();
while u<v{
if u&1!=0{
um=F::M::op(um,self.a[u].get());
u+=1;
}
if v&1!=0{
v-=1;
vm=F::M::op(self.a[v].get(),vm);
}
u>>=1;
v>>=1;
}
F::M::op(um,vm)
}
fn apply(&mut self,range:impl std::ops::RangeBounds<usize>,f:F::F){
use std::ops::Bound::*;
let mut u=match range.start_bound(){
Included(&a)=>a,
Excluded(&a)=>a+1,
Unbounded=>0,
};
let mut v=match range.end_bound(){
Included(&a)=>a+1,
Excluded(&a)=>a,
Unbounded=>self.n,
};
assert!(u<=v && v<=self.n);
if u==v{
return;
}
u+=self.size;
v+=self.size;
for i in (1..=self.log).rev(){
if u&!0<<i!=u{
self.push(u>>i);
}
if v&!0<<i!=v{
self.push(v-1>>i);
}
}
{
let mut u=u;
let mut v=v;
while u<v{
if u&1!=0{
self.apply_node(u,f);
u+=1;
}
if v&1!=0{
v-=1;
self.apply_node(v,f);
}
u>>=1;
v>>=1;
}
}
for i in 1..=self.log{
if u&!0<<i!=u{
self.update(u>>i);
}
if v&!0<<i!=v{
self.update(v-1>>i);
}
}
}
// l..rがtrueで、l..=rがfalse
fn max_right(&self,mut l:usize,mut f:impl FnMut(<F::M as Monoid>::S)->bool)->usize{
assert!(l<=self.n && f(F::M::e()));
if l==self.n{
return self.n;
}
l+=self.size;
for i in (1..=self.log).rev(){
self.push(l>>i);
}
let mut m=F::M::e();
loop{
l>>=l.trailing_zeros();
if !f(F::M::op(m,self.a[l].get())){
while l<self.size{
self.push(l);
l*=2;
let res=F::M::op(m,self.a[l].get());
if f(res){
m=res;
l+=1;
}
}
return l-self.size;
}
m=F::M::op(m,self.a[l].get());
l+=1;
if l&l.wrapping_neg()==l{
return self.n;
}
}
}
// l..rがtrueで、l-1..rがfalse
fn min_left(&mut self,mut r:usize,mut f:impl FnMut(<F::M as Monoid>::S)->bool)->usize{
assert!(r<=self.n && f(F::M::e()));
if r==0{
return 0;
}
r+=self.size;
for i in (1..=self.log).rev(){
self.push(r-1>>i);
}
let mut m=F::M::e();
loop{
r-=1;
r>>=r.trailing_ones();
r=r.max(1);
if !f(F::M::op(self.a[r].get(),m)){
while r<self.size{
self.push(r);
r=2*r+1;
let res=F::M::op(self.a[r].get(),m);
if f(res){
m=res;
r-=1;
}
}
return r+1-self.size;
}
m=F::M::op(self.a[r].get(),m);
if r&r.wrapping_neg()==r{
return 0;
}
}
}
}
trait Monoid{
type S:Copy;
fn e()->Self::S;
fn op(left:Self::S,right:Self::S)->Self::S;
}
#[macro_export]
macro_rules! impl_monoid{
($t:ident,$item:ty,$e:expr,$op:expr)=>{
#[derive(Clone,Copy)]
struct $t();
impl Monoid for $t{
type S=$item;
fn e()->$item{ $e }
fn op(left:$item,right:$item)->$item{
$op(left,right)
}
}
};
}
trait MapMonoid{
type M:Monoid;
type F:Copy;
fn id()->Self::F;
fn map(v:<Self::M as Monoid>::S,f:Self::F)-><Self::M as Monoid>::S;
fn comp(new:Self::F,old:Self::F)->Self::F;
}
#[macro_export]
macro_rules! impl_mapmonoid{
($t:ident,$monoid:ty,$f:ty,$id:expr,$map:expr,$comp:expr)=>{
#[derive(Clone,Copy)]
struct $t();
impl MapMonoid for $t{
type M=$monoid;
type F=$f;
fn id()->$f{ $id }
fn map(v:<$monoid as Monoid>::S,f:$f)-><$monoid as Monoid>::S{
$map(v,f)
}
fn comp(new:$f,old:$f)->$f{
$comp(new,old)
}
}
}
}