Submission #61465394

---

Source Code Expand

fn main() {
  input! {
    n: usize, q: usize,
    a: [Mint; n],
  }

  let mut list = a.into_iter().collect::<SplayTreeList::<RangeAffineRangeSum>>();
  for _ in 0 .. q {
    input!(t: usize);
    if t == 0 {
      input!(l: usize, r: usize, b: Mint, c: Mint);
      list.apply_range(l .. r, (b, c));
    } else {
      input!(l: usize, r: usize);
      println!("{}", list.prod(l .. r).0);
    }
  }
}


enum RangeAffineRangeSum {}
impl SplayTreeHelper for RangeAffineRangeSum {
  type Value = Mint;
  type Summary = (Mint, Mint);
  type Action = (Mint, Mint);

  fn value_map(&(b, c): &Self::Action, a: &mut Self::Value) {
    *a = b * *a + c;
  }

  fn summarize(&a: &Self::Value) -> Self::Summary {
    (a, Mint::from(1))
  }

  fn sum_empty() -> Self::Summary {
    (Mint::from(0), Mint::from(0))
  }

  fn sum_concat(&(x1, n1): &Self::Summary, &(x2, n2): &Self::Summary) -> Self::Summary {
    (x1 + x2, n1 + n2)
  }

  fn sum_map(&(b, c): &Self::Action, &(x, n): &Self::Summary) -> Self::Summary {
    (b * x + c * n, n)
  }

  fn compose(&(b1, c1): &Self::Action, &(b2, c2): &Self::Action) -> Self::Action {
    (b1 * b2, b1 * c2 + c1)
  }
}

use ac_library::ModInt998244353 as Mint;
use proconio::input;

use splay_tree_list::{List as SplayTreeList, Helper as SplayTreeHelper};
pub mod splay_tree_list {
  use std::{cell::UnsafeCell, iter::FromIterator, mem::replace, ops::RangeBounds};

  pub trait Helper {
      /// 要素
      type Value;
      /// 集約値
      type Summary: Clone;
      /// 作用
      type Action: Clone;
  
      /// 要素への作用
      fn value_map(f: &Self::Action, x: &mut Self::Value) {
          let _ = (f, x);
      }
  
      /// 要素の集約値
      fn summarize(x: &Self::Value) -> Self::Summary;

      /// 集約値の単位元（空のリストに対する集約値）
      fn sum_empty() -> Self::Summary;

      /// 集約値の連結
      fn sum_concat(x: &Self::Summary, y: &Self::Summary) -> Self::Summary;

      /// 左右反転したときの集約値（連結が非可換な場合に定義）
      fn sum_rev(x: &Self::Summary) -> Self::Summary {
          x.clone()
      }

      /// 集約値への作用
      fn sum_map(f: &Self::Action, x: &Self::Summary) -> Self::Summary {
          let _ = f;
          x.clone()
      }
      
      /// 作用の合成（f∘g）
      fn compose(f: &Self::Action, g: &Self::Action) -> Self::Action {
          let _ = g;
          f.clone()
      }
  }

  pub struct List<H: Helper> {
      root: UnsafeCell<Option<Box<Node<H>>>>,
  }
  impl<H: Helper> List<H> {
      pub fn new() -> Self {
          Self { root: UnsafeCell::new(None) }
      }
      
      pub fn is_empty(&self) -> bool {
          unsafe { &*self.root.get() }.is_none()
      }

      pub fn len(&self) -> usize {
          unsafe { &*self.root.get() }.as_ref().map(|root| root.len() ).unwrap_or(0)
      }

      pub fn front(&self) -> Option<&H::Value> {
          if self.is_empty() {
              None
          } else {
              Some(&self[0])
          }
      }

      pub fn back(&self) -> Option<&H::Value> {
          if self.is_empty() {
              None
          } else {
              Some(&self[self.len() - 1])
          }
      }

      pub fn set(&mut self, index: usize, value: H::Value) {
          assert!(index < self.len());
          let mut root = self.root.get_mut().take().unwrap();
          root = root.set_value(index, value);
          *self.root.get_mut() = Some(root);
      }

      pub fn reverse(&mut self) {
          if let Some(root) = self.root.get_mut() {
              root.reverse();
          }
      }

      pub fn reverse_range(&mut self, range: impl RangeBounds<usize>) {
          let (l, r) = self.range(range);
          assert!(l <= r && r <= self.len());
          let [left, mut mid, right] = Node::split3(self.root.get_mut().take(), l, r);
          if let Some(node) = mid.as_mut() {
              node.reverse();
          }
          *self.root.get_mut() = Node::merge3(left, mid, right);
      }

      pub fn rotate_left(&mut self, n: usize) {
          assert!(n <= self.len());
          let [mut left, mut right] = Node::split(self.root.get_mut().take(), n);
          if let Some(left) = left.as_mut() {
              left.reverse();
          }
          if let Some(right) = right.as_mut() {
              right.reverse();
          }
          *self.root.get_mut() = Node::merge(left, right);
          self.reverse();
      }

      pub fn rotate_right(&mut self, n: usize) {
          assert!(n <= self.len());
          self.rotate_left(self.len() - n);
      }

      pub fn swap(&mut self, i: usize, j: usize) {
          assert!(i < self.len() && j < self.len());
          if i == j {
              return;
          }
          let (i, j) = (i.min(j), i.max(j));
          let [rest, y, c] = Node::split3(self.root.get_mut().take(), j, j + 1);
          let [a, x, b] = Node::split3(rest, i, i + 1);
          *self.root.get_mut() = Node::merge3(Node::merge3(a, y, b), x, c);
      }

      pub fn append(&mut self, other: &mut Self) {
          let root = Node::merge(self.root.get_mut().take(), other.root.get_mut().take());
          *self.root.get_mut() = root;
      }

      pub fn split_off(&mut self, index: usize) -> Self {
          let [root, other_root] = Node::split(self.root.get_mut().take(), index);
          *self.root.get_mut() = root;
          Self { root: UnsafeCell::new(other_root) }
      }

      pub fn insert(&mut self, index: usize, value: H::Value) {
          assert!(index <= self.len());
          let [before, after] = Node::split(self.root.get_mut().take(), index);
          *self.root.get_mut() = Node::merge3(before, Some(Node::new(value)), after);
      }

      pub fn push_front(&mut self, value: H::Value) {
          *self.root.get_mut() = Node::merge(Some(Node::<H>::new(value)), self.root.get_mut().take());
      }

      pub fn push_back(&mut self, value: H::Value) {
          *self.root.get_mut() = Node::merge(self.root.get_mut().take(), Some(Node::<H>::new(value)));
      }

      pub fn pop_front(&mut self) -> Option<H::Value> {
          if self.is_empty() {
              None
          } else {
              let [node, rest] = Node::split(self.root.get_mut().take(), 1);
              let value = Node::into_inner(node).pop();
              *self.root.get_mut() = rest;
              value
          }
      }

      pub fn pop_back(&mut self) -> Option<H::Value> {
          if self.is_empty() {
              None
          } else {
              let index = self.len() - 1;
              let [rest, node] = Node::split(self.root.get_mut().take(), index);
              let value = Node::into_inner(node).pop();
              *self.root.get_mut() = rest;
              value
          }
      }

      pub fn remove(&mut self, index: usize) -> Option<H::Value> {
          if index < self.len() {
              let [before, node, after] = Node::split3(self.root.get_mut().take(), index, index + 1);
              let value = Node::into_inner(node).pop();
              *self.root.get_mut() = Node::merge(before, after);
              value
          } else {
              None
          }
      }

      pub fn prod(&self, range: impl RangeBounds<usize>) -> H::Summary {
          let (l, r) = self.range(range);
          assert!(l <= r && r <= self.len());
          let [left, mut mid, right] = Node::split3(unsafe { (&mut *self.root.get()).take() }, l, r);
          let summary = mid.as_mut().map(|node| node.summary() ).unwrap_or_else(H::sum_empty);
          unsafe {
              *self.root.get() = Node::merge3(left, mid, right);
          }
          summary
      }

      pub fn apply_range(&mut self, range: impl RangeBounds<usize>, f: H::Action) {
          let (l, r) = self.range(range);
          assert!(l <= r && r <= self.len());
          let [left, mut mid, right] = Node::split3(self.root.get_mut().take(), l, r);
          if let Some(node) = mid.as_mut() {
              node.apply(&f);
          }
          *self.root.get_mut() = Node::merge3(left, mid, right);
      }

      fn range(&self, range: impl RangeBounds<usize>) -> (usize, usize) {
          use std::ops::Bound::*;
          let l = match range.start_bound() { Included(&l) => l, Excluded(&l) => l + 1, Unbounded => 0 };
          let r = match range.end_bound() { Excluded(&r) => r, Included(&r) => r + 1, Unbounded => self.len() };
          (l, r)
      }
  }
  impl<H: Helper> FromIterator<H::Value> for List<H> {
      fn from_iter<T: IntoIterator<Item = H::Value>>(iter: T) -> Self {
          Self { root: UnsafeCell::new(Node::<H>::from_iter(iter.into_iter())) }
      }
  }
  impl<H: Helper> From<Vec<H::Value>> for List<H> {
      fn from(value: Vec<H::Value>) -> Self {
          Self::from_iter(value)
      }
  }
  impl<H: Helper> std::ops::Index<usize> for List<H> {
      type Output = H::Value;
      fn index(&self, index: usize) -> &Self::Output {
          assert!(index < self.len());
          let root = unsafe { (&mut *self.root.get()).as_mut().unwrap_unchecked() };
          root.value(index)
      }
  }
  impl<H: Helper> IntoIterator for List<H> {
      type IntoIter = <Vec<H::Value> as IntoIterator>::IntoIter;
      type Item = H::Value;
      fn into_iter(mut self) -> Self::IntoIter {
          Node::into_inner(self.root.get_mut().take()).into_iter()
      }
  }
  impl<H: Helper> std::fmt::Debug for List<H> where H::Value: std::fmt::Debug {
      fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
          match self.len() {
              0 => f.write_str("[]"),
              1 => f.write_fmt(format_args!("[{:?}]", &self[0])),
              _ => {
                  f.write_fmt(format_args!("[{:?}", &self[0]))?;
                  for i in 1 .. self.len() {
                      f.write_fmt(format_args!(", {:?}", &self[i]))?;
                  }
                  f.write_str("]")
              }
          }
      }
  }

  pub struct Node<H: Helper> {
      children: [Option<Box<Self>>; 2],
      len: u32,
      reversed: bool,
      value: H::Value,
      summary: H::Summary,
      lazy: Option<H::Action>,
  }
  
  impl<H: Helper> std::fmt::Debug for Node<H> where H::Value: std::fmt::Debug, H::Summary: std::fmt::Debug, H::Action: std::fmt::Debug {
      fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
          let lazy = self.lazy.as_ref().map(|lazy| format!(", lazy={:?}", lazy) ).unwrap_or_else(|| "".to_string() );
          let reversed = if self.reversed { ", reversed" } else { "" };
          f.write_fmt(format_args!("Node(len={}, value={:?}, summary={:?}{}{}) [{:?}, {:?}]", self.len, &self.value, &self.summary, lazy, reversed, &self.children[0], &self.children[1]))
      }
  }
  
  impl<H: Helper> Node<H> {
      pub fn new(value: H::Value) -> Box<Self> {
          Box::new(Self {
              children: [None, None],
              len: 1,
              reversed: false,
              summary: H::summarize(&value),
              value,
              lazy: None,
          })
      }
  
      pub fn from_iter(iter: impl Iterator<Item = H::Value>) -> Option<Box<Self>> {
          let mut node = None;
          for value in iter {
              node = Self::merge(node, Some(Self::new(value)));
          }
          node
      }
  
      pub fn len(self: &Box<Self>) -> usize {
          self.len as usize
      }
  
      pub fn into_inner(node: Option<Box<Self>>) -> Vec<H::Value> {
          fn dfs<H: Helper>(node: Option<Box<Node<H>>>, values: &mut Vec<H::Value>) {
              let Some(mut node) = node else { return };
              node.push();
              dfs(node.children[0].take(), values);
              values.push(node.value);
              dfs(node.children[1].take(), values);
          }
          
          let mut values = Vec::with_capacity(node.as_ref().map(|node| node.len() ).unwrap_or(0));
          dfs(node, &mut values);
          values
      }
  
      // update self.len, self.summary
      fn update(&mut self) {
          self.summary = H::summarize(&self.value);
          self.len = 1;
          if let Some(child) = &self.children[0] {
              self.len += child.len;
              self.summary = H::sum_concat(&child.summary, &self.summary);
          }
          if let Some(child) = &self.children[1] {
              self.len += child.len;
              self.summary = H::sum_concat(&self.summary, &child.summary);
          }
      }
  
      // self.lazy, self.reversed の遅延を解消し、 self.value, self.children に反映する
      fn push(&mut self) {
          if let Some(lazy) = self.lazy.take() {
              H::value_map(&lazy, &mut self.value);
              for child in &mut self.children.iter_mut().filter_map(Option::as_mut) {
                  child.apply(&lazy);
              }
          }
          if replace(&mut self.reversed, false) {
              self.children.swap(0, 1);
              for child in &mut self.children.iter_mut().filter_map(Option::as_mut) {
                  child.reverse();
              }
          }
      }
  
      pub fn apply(&mut self, f: &H::Action) {
          if let Some(lazy) = &self.lazy {
              self.lazy = Some(H::compose(f, lazy));
          } else {
              self.lazy = Some(f.clone());
          }
          self.summary = H::sum_map(f, &self.summary);
      }
  
      pub fn reverse(&mut self) {
          self.reversed ^= true;
          self.summary = H::sum_rev(&self.summary);
      }
  
      pub fn summary(&mut self) -> H::Summary {
          self.push();
          self.summary.clone()
      }
  
      fn rotate(mut self: Box<Self>, dir: bool) -> Box<Self> {
          let Some(mut child) = self.children[dir as usize].take() else { return self };
          self.children[dir as usize] = child.children[!dir as usize].take();
          self.update();
          child.children[!dir as usize] = Some(self);
          child.update();
          child
      }
  
      pub fn value<'a>(self: &'a mut Box<Self>, index: usize) -> &'a H::Value {
          // Box をコピー（以降コピー元の値を参照してはいけない）
          let mut node = unsafe { Box::from_raw((*self).as_mut() as *mut Self) };
          node = node.splay(index);
          node.push();
          unsafe {
              // write でコピー元の Box が破棄されることを回避
              (self as *mut Box<Self>).write(node);
          }
          &self.value
      }
  
      pub fn set_value(self: Box<Self>, index: usize, value: H::Value) -> Box<Self> {
          let mut node = self.splay(index);
          node.push();
          node.value = value;
          node
      }
  
      pub fn splay(mut self: Box<Self>, mut index: usize) -> Box<Self> {
          debug_assert!(index < self.len as usize);
          self.push();
          let left_len = self.children[0].as_ref().map(|child| child.len ).unwrap_or(0) as usize;
          if index < left_len {
              self.children[0] = self.children[0].take().map(|child| child.splay(index) );
              self.update();
              return self.rotate(false);
          }
          index -= left_len;
          if index == 0 {
              return self;
          }
          index -= 1;
          self.children[1] = self.children[1].take().map(|child| child.splay(index) );
          self.update();
          self.rotate(true)
      }
  
      pub fn merge(left: Option<Box<Self>>, right: Option<Box<Self>>) -> Option<Box<Self>> {
          let Some(mut right) = right else { return left };
          right = right.splay(0);
          right.push();
          right.children[0] = left;
          right.update();
          Some(right)
      }
  
      pub fn split(node: Option<Box<Self>>, index: usize) -> [Option<Box<Self>>; 2] {
          let Some(mut node) = node else { return [None, None] };
          debug_assert!(index <= node.len as usize);
          if index == node.len as usize {
              return [Some(node), None];
          }
          node = node.splay(index);
          node.push();
          let left = node.children[0].take();
          node.update();
          [left, Some(node)]
      }
  
      pub fn split3(node: Option<Box<Self>>, l: usize, r: usize) -> [Option<Box<Self>>; 3] {
          if l == 0 {
              let [mid, right] = Self::split(node, r);
              return [None, mid, right];
          }
          let Some(mut node) = node else { return [None, None, None] };
          node = node.splay(l - 1);
          node.push();
          let [mid, right] = Self::split(node.children[1].take(), r - l);
          node.update();
          [Some(node), mid, right]
      }
  
      pub fn merge3(left: Option<Box<Self>>, mid: Option<Box<Self>>, right: Option<Box<Self>>) -> Option<Box<Self>> {
          let rest = Self::merge(mid, right);
          let Some(mut left) = left else { return rest };
          left.push();
          if left.children[1].is_none() {
              left.children[1] = rest;
              left.update();
              Some(left)
          } else {
              Self::merge(Some(left), rest)
          }
      }
  }
  
}

Submission Info

Judge Result