AtCoder Beginner Contest 417 F

https://atcoder.jp/contests/abc417/tasks/abc417_f

指定した範囲を平均するので、木を作ればよいです。

// Random Gathering
#![allow(non_snake_case)]

use std::cmp::{min, max};


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

// ax = by + 1 (a, b > 0)
fn linear_diophantine(a: i64, b: i64) -> Option<(i64, i64)> {
    if a == 1 {
        return Some((1, 0))
    }
    
    let q = b / a;
    let r = b % a;
    if r == 0 {
        return None
    }
    let (x1, y1) = linear_diophantine(r, a)?;
    Some((-q * x1 - y1, -x1))
}

fn inverse<const D: i64>(a: i64) -> i64 {
    let (x, _y) = linear_diophantine(a, D).unwrap();
    x.rem_euclid(D)
}


//////////////////// ModInt ////////////////////

use std::cmp::Ordering;
use std::ops::{Add, AddAssign, Sub, SubAssign,
               Mul, MulAssign, Div, DivAssign, Neg, Rem};

#[derive(Copy, Clone)]
struct ModInt<const D: i64>(i64);

impl<const D: i64> From<i64> for ModInt<D> {
    fn from(x: i64) -> Self {
        Self(x.rem_euclid(D))
    }
}
impl<const D: i64> PartialEq for ModInt<D> {
    fn eq(&self, other: &Self) -> bool {
        self.0 == other.0
    }
}

impl<const D: i64> PartialEq<i64> for ModInt<D> {
    fn eq(&self, other: &i64) -> bool {
        self.0 == *other
    }
}

impl<const D: i64> Eq for ModInt<D> {}

impl<const D: i64> PartialOrd for ModInt<D> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl<const D: i64> Ord for ModInt<D> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.0.cmp(&other.0)
    }
}

impl<const D: i64> Add for ModInt<D> {
    type Output = Self;
    
    fn add(self, other: Self) -> Self {
        Self((self.0 + other.0) % D)
    }
}

impl<const D: i64> Add<i64> for ModInt<D> {
    type Output = Self;
    
    fn add(self, other: i64) -> Self {
        Self((self.0 + other) % D)
    }
}

impl<const D: i64> Add<ModInt<D>> for i64 {
    type Output = ModInt<D>;
    
    fn add(self, other: ModInt<D>) -> ModInt<D> {
        ModInt::<D>((self + other.0).rem_euclid(D))
    }
}

impl<const D: i64> AddAssign for ModInt<D> {
    fn add_assign(&mut self, other: ModInt<D>) {
        self.0 = (self.0 + other.0).rem_euclid(D)
    }
}

impl<const D: i64> AddAssign<i64> for ModInt<D> {
    fn add_assign(&mut self, other: i64) {
        self.0 = (self.0 + other).rem_euclid(D)
    }
}

impl<const D: i64> Sub for ModInt<D> {
    type Output = Self;
    
    fn sub(self, other: Self) -> Self {
        Self((self.0 - other.0).rem_euclid(D))
    }
}

impl<const D: i64> Sub<i64> for ModInt<D> {
    type Output = Self;
    
    fn sub(self, other: i64) -> Self {
        Self((self.0 - other).rem_euclid(D))
    }
}

impl<const D: i64> Sub<ModInt<D>> for i64 {
    type Output = ModInt<D>;
    
    fn sub(self, other: ModInt<D>) -> ModInt<D> {
        ModInt::<D>((self - other.0).rem_euclid(D))
    }
}

impl<const D: i64> SubAssign for ModInt<D> {
    fn sub_assign(&mut self, other: Self) {
        self.0 = (self.0 - other.0).rem_euclid(D)
    }
}

impl<const D: i64> SubAssign<i64> for ModInt<D> {
    fn sub_assign(&mut self, other: i64) {
        self.0 = (self.0 - other).rem_euclid(D)
    }
}

impl<const D: i64> Mul for ModInt<D> {
    type Output = Self;
    
    fn mul(self, other: Self) -> Self {
        Self(self.0 * other.0 % D)
    }
}

impl<const D: i64> Mul<i64> for ModInt<D> {
    type Output = Self;
    
    fn mul(self, other: i64) -> Self {
        Self(self.0 * other % D)
    }
}

impl<const D: i64> Mul<ModInt<D>> for i64 {
    type Output = ModInt<D>;
    
    fn mul(self, other: ModInt<D>) -> ModInt<D> {
        ModInt::<D>(self * other.0 % D)
    }
}

impl<const D: i64> MulAssign for ModInt<D> {
    fn mul_assign(&mut self, other: Self) {
        self.0 = self.0 * other.0 % D
    }
}

impl<const D: i64> MulAssign<i64> for ModInt<D> {
    fn mul_assign(&mut self, other: i64) {
        self.0 = self.0 * other % D
    }
}

impl<const D: i64> Div for ModInt<D> {
    type Output = Self;
    
    fn div(self, other: Self) -> Self {
        Self(self.0 * inverse::<D>(other.0) % D)
    }
}

impl<const D: i64> Div<i64> for ModInt<D> {
    type Output = Self;
    
    fn div(self, other: i64) -> Self {
        Self(self.0 * inverse::<D>(other) % D)
    }
}

impl<const D: i64> Div<ModInt<D>> for i64 {
    type Output = ModInt<D>;
    
    fn div(self, other: ModInt<D>) -> ModInt<D> {
        ModInt::<D>(self * inverse::<D>(other.0) % D)
    }
}

impl<const D: i64> DivAssign for ModInt<D> {
    fn div_assign(&mut self, other: Self) {
        self.0 = self.0 * inverse::<D>(other.0) % D
    }
}

impl<const D: i64> DivAssign<i64> for ModInt<D> {
    fn div_assign(&mut self, other: i64) {
        self.0 = self.0 * inverse::<D>(other) % D
    }
}

impl<const D: i64> Neg for ModInt<D> {
    type Output = Self;
    
    fn neg(self) -> Self::Output {
        Self(if self.0 == 0 { 0 } else { D - self.0 })
    }
}

impl<const D: i64> Rem for ModInt<D> {
    type Output = Self;
    
    fn rem(self, other: ModInt<D>) -> ModInt<D> {
        ModInt::<D>(self.0 % other.0)
    }
}

impl<const D: i64> Rem<i64> for ModInt<D> {
    type Output = Self;
    
    fn rem(self, other: i64) -> Self {
        Self(self.0 % other)
    }
}

use std::iter::Sum;

impl<const D: i64> Sum for ModInt<D> {
    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
        iter.fold(Self::from(0), |acc, x| acc + x)
    }
}


//////////////////// Segment Tree ////////////////////

const D: i64 = 998244353;

type IntD = ModInt::<D>;

type Val = (IntD, bool);
type Range = (usize, usize);

struct SegmentTree {
    n: usize,
    v: Vec<Val>,
}

impl SegmentTree {
    fn sum(&self, rng: Range) -> IntD {
        self.sum_core(rng, 0, self.n, 0)
    }
    
    fn sum_core(&self, rng: Range, first: usize, last: usize, i: usize) -> IntD {
        if self.v[i].1 {
            let r1 = max(rng.0, first);
            let r2 = min(rng.1, last);
            self.v[i].0 * ((r2 - r1) as i64)
        }
        else {
            let mid = (first + last) / 2;
            if rng.1 <= mid {
                self.sum_core(rng, first, mid, i*2+1)
            }
            else if rng.0 >= mid {
                self.sum_core(rng, mid, last, i*2+2)
            }
            else {
                self.sum_core(rng, first, mid, i*2+1) +
                self.sum_core(rng, mid, last, i*2+2)
            }
        }
    }
    
    fn update(&mut self, rng: Range, s: IntD) {
        self.update_core(rng, 0, self.n, 0, s)
    }
    
    fn update_core(&mut self, rng: Range, first: usize, last: usize,
                                                    i: usize, s: IntD) {
        if rng.0 <= first && last <= rng.1 {
            self.v[i] = (s, true)
        }
        else {
            let mid = (first + last) / 2;
            if self.v[i].1 {
                self.v[i*2+1] = self.v[i];
                self.v[i*2+2] = self.v[i]
            }
            if rng.1 <= mid {
                self.update_core(rng, first, mid, i*2+1, s)
            }
            else if rng.0 >= mid {
                self.update_core(rng, mid, last, i*2+2, s)
            }
            else {
                self.update_core(rng, first, mid, i*2+1, s);
                self.update_core(rng, mid, last, i*2+2, s);
            }
            self.v[i] = (IntD::from(0), false)
        }
    }
    
    fn to_list(&self, m: usize) -> Vec<i64> {
        let mut A: Vec<i64> = vec![0; m];
        self.to_list_core((0, m), 0, self.n, 0, &mut A);
        A
    }
    
    fn to_list_core(&self, rng: Range, first: usize, last: usize,
                                            i: usize, A: &mut Vec<i64>) {
        if rng.0 <= first && last <= rng.1 && self.v[i].1 {
            for j in first..last {
                A[j] = self.v[i].0.0
            }
        }
        else {
            let mid = (first + last) / 2;
            if rng.1 <= mid {
                self.to_list_core(rng, first, mid, i*2+1, A)
            }
            else if rng.0 >= mid {
                self.to_list_core(rng, mid, last, i*2+2, A)
            }
            else {
                self.to_list_core(rng, first, mid, i*2+1, A);
                self.to_list_core(rng, mid, last, i*2+2, A)
            }
        }
    }
    
    fn ceil_two_pow(n: usize) -> usize {
        if n == 1 { 1 } else { SegmentTree::ceil_two_pow((n+1)/2) * 2 }
    }
    
    fn create(A: &Vec<i64>) -> SegmentTree {
        let m = A.len();
        let n = SegmentTree::ceil_two_pow(m);
        let mut v: Vec<Val> = vec![(IntD::from(0), false); n*2-1];
        for i in n-1..n-1+m {
            v[i] = (IntD::from(A[i+1-n]), true)
        }
        SegmentTree { n, v }
    }
}


//////////////////// process ////////////////////

fn read_range() -> Range {
    let v: Vec<usize> = read_vec();
    (v[0] - 1, v[1])
}

fn read_input() -> (Vec<i64>, Vec<Range>) {
    let v: Vec<usize> = read_vec();
    let M = v[1];
    let A: Vec<i64> = read_vec();
    let rngs: Vec<Range> = (0..M).map(|_| read_range()).collect();
    (A, rngs)
}

fn F(A: Vec<i64>, rngs: Vec<Range>) {
    let mut tree = SegmentTree::create(&A);
    for rng in rngs {
        let s = tree.sum(rng) / ((rng.1 - rng.0) as i64);
        tree.update(rng, s);
    }
    let v = tree.to_list(A.len());
    println!("{}", v.iter().map(|e| e.to_string()).collect::<Vec<_>>().join(" "))
}

fn main() {
    let (A, rngs) = read_input();
    F(A, rngs)
}