結果
| 問題 |
No.2992 Range ABCD String Query
|
| ユーザー |
 akakimidori
|
| 提出日時 | 2024-12-22 19:25:35 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 249 ms / 6,000 ms |
| コード長 | 12,117 bytes |
| コンパイル時間 | 13,444 ms |
| コンパイル使用メモリ | 395,424 KB |
| 実行使用メモリ | 51,952 KB |
| 最終ジャッジ日時 | 2024-12-22 19:26:04 |
| 合計ジャッジ時間 | 26,682 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 41 |
コンパイルメッセージ
warning: type alias `Map` is never used --> src/main.rs:4:6 | 4 | type Map<K, V> = BTreeMap<K, V>; | ^^^ | = note: `#[warn(dead_code)]` on by default warning: type alias `Set` is never used --> src/main.rs:5:6 | 5 | type Set<T> = BTreeSet<T>; | ^^^ warning: type alias `Deque` is never used --> src/main.rs:6:6 | 6 | type Deque<T> = VecDeque<T>; | ^^^^^
ソースコード
use std::collections::*;
use std::io::Write;
type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;
fn main() {
input! {
n: usize,
q: usize,
s: bytes,
ask: [(u8, usize1, String); q],
}
type Mat = Matrix<V, 4, 4>;
let mut mat = vec![];
for i in 0..4 {
let mut m = Mat::one();
for j in 0..4 {
if i != j {
m[j][j] = V(1);
}
}
let mut trans = Mat::zero();
for i in 0..4 {
for j in 0..=i {
trans[j][i] = V::one();
}
}
mat.push(trans * m);
}
let mut seg = SegmentTreePURQ::new(n, Mat::one(), |a, b| *a * *b);
for (i, s) in s.iter().enumerate() {
seg.update_tmp(i, mat[(*s - b'A') as usize]);
}
seg.update_all();
let out = std::io::stdout();
let mut out = std::io::BufWriter::new(out.lock());
for (op, x, c) in ask {
if op == 1 {
let c = c.bytes().next().unwrap();
seg.update(x, mat[(c - b'A') as usize]);
} else {
let l = x;
let r = c.parse::<usize>().unwrap();
let m = seg.find(l, r);
let ans = m[0].iter().fold(V::zero(), |s, a| s + *a).0;
writeln!(out, "{}", ans).ok();
}
}
}
use std::ops::*;
#[derive(Clone, Copy)]
struct V(i32);
impl Add for V {
type Output = Self;
fn add(self, rhs: Self) -> Self {
V(self.0.min(rhs.0))
}
}
impl Mul for V {
type Output = Self;
fn mul(self, rhs: Self) -> Self {
V(self.0 + rhs.0)
}
}
const INF: i32 = 10i32.pow(9);
impl Zero for V {
fn zero() -> Self {
V(INF)
}
fn is_zero(&self) -> bool {
self.0 == INF
}
}
impl One for V {
fn one() -> Self {
V(0)
}
fn is_one(&self) -> bool {
self.0 == 0
}
}
// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
input_inner!{iter, $($r)*}
};
($($r:tt)*) => {
let s = {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
s
};
let mut iter = s.split_whitespace();
input_inner!{iter, $($r)*}
};
}
#[macro_export]
macro_rules! input_inner {
($iter:expr) => {};
($iter:expr, ) => {};
($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($iter, $t);
input_inner!{$iter $($r)*}
};
}
#[macro_export]
macro_rules! read_value {
($iter:expr, ( $($t:tt),* )) => {
( $(read_value!($iter, $t)),* )
};
($iter:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
};
($iter:expr, chars) => {
read_value!($iter, String).chars().collect::<Vec<char>>()
};
($iter:expr, bytes) => {
read_value!($iter, String).bytes().collect::<Vec<u8>>()
};
($iter:expr, usize1) => {
read_value!($iter, usize) - 1
};
($iter:expr, $t:ty) => {
$iter.next().unwrap().parse::<$t>().expect("Parse error")
};
}
// ---------- end input macro ----------
// ---------- begin trait ----------
pub trait Zero: Sized + Add<Self, Output = Self> {
fn zero() -> Self;
fn is_zero(&self) -> bool;
}
pub trait One: Sized + Mul<Self, Output = Self> {
fn one() -> Self;
fn is_one(&self) -> bool;
}
pub trait Group: Zero + Sub<Output = Self> + Neg<Output = Self> {}
pub trait SemiRing: Zero + One {}
pub trait Ring: SemiRing + Group {}
pub trait Field: Ring + Div<Output = Self> {}
impl<T> Group for T where T: Zero + Sub<Output = Self> + Neg<Output = Self> {}
impl<T> SemiRing for T where T: Zero + One {}
impl<T> Ring for T where T: SemiRing + Group {}
impl<T> Field for T where T: Ring + Div<Output = Self> {}
// ---------- end trait ----------
// ---------- begin const matrix ----------
#[derive(Clone, Copy, Debug)]
pub struct Matrix<T, const R: usize, const C: usize>([[T; C]; R]);
impl<T, const R: usize, const C: usize> Matrix<T, R, C> {
pub fn new(a: [[T; C]; R]) -> Self {
Self(a)
}
pub fn iter(&self) -> impl Iterator<Item = &[T; C]> {
self.0.iter()
}
pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut [T; C]> {
self.0.iter_mut()
}
pub fn swap_row(&mut self, x: usize, y: usize) {
assert!(x < R && y < R);
self.0.swap(x, y);
}
pub fn swap_col(&mut self, x: usize, y: usize) {
assert!(x < C && y < C);
for mat in self.iter_mut() {
mat.swap(x, y);
}
}
}
impl<T, const R: usize, const C: usize> Zero for Matrix<T, R, C>
where
T: Zero + Copy,
{
fn zero() -> Self {
Self::new([[T::zero(); C]; R])
}
fn is_zero(&self) -> bool {
self.iter().flatten().all(|a| a.is_zero())
}
}
impl<T, const R: usize, const C: usize> Matrix<T, R, C>
where
T: Add<Output = T> + Copy,
{
pub fn matadd(&self, rhs: &Self) -> Self {
let mut res = self.clone();
for (res, rhs) in res.iter_mut().zip(rhs.iter()) {
for (res, rhs) in res.iter_mut().zip(rhs.iter()) {
*res = *res + *rhs;
}
}
res
}
}
impl<T, const R: usize, const C: usize> Add for Matrix<T, R, C>
where
T: Add<Output = T> + Copy,
{
type Output = Self;
fn add(self, rhs: Self) -> Self::Output {
self.matadd(&rhs)
}
}
impl<T, const R: usize, const C: usize> Matrix<T, R, C>
where
T: Sub<Output = T> + Copy,
{
pub fn matsub(&self, rhs: &Self) -> Self {
let mut res = self.clone();
for (res, rhs) in res.iter_mut().zip(rhs.iter()) {
for (res, rhs) in res.iter_mut().zip(rhs.iter()) {
*res = *res - *rhs;
}
}
res
}
}
impl<T, const R: usize, const C: usize> Sub for Matrix<T, R, C>
where
T: Sub<Output = T> + Copy,
{
type Output = Self;
fn sub(self, rhs: Self) -> Self::Output {
self.matsub(&rhs)
}
}
impl<T, const N: usize> One for Matrix<T, N, N>
where
T: Zero + One + Copy,
{
fn one() -> Self {
let mut res = Self::zero();
for (i, a) in res.iter_mut().enumerate() {
a[i] = T::one();
}
res
}
fn is_one(&self) -> bool {
self.iter().enumerate().all(|(i, a)| {
a.iter()
.enumerate()
.all(|(j, a)| (i == j && a.is_one()) || (i != j && a.is_zero()))
})
}
}
impl<T, const R: usize, const C: usize> Matrix<T, R, C>
where
T: Zero + Mul<Output = T> + Copy,
{
pub fn matmul<const M: usize>(&self, rhs: &Matrix<T, C, M>) -> Matrix<T, R, M> {
let mut res = Matrix::<T, R, M>::zero();
for (res, a) in res.iter_mut().zip(self.iter()) {
for (a, b) in a.iter().zip(rhs.iter()) {
for (res, b) in res.iter_mut().zip(b.iter()) {
*res = *res + *a * *b;
}
}
}
res
}
}
impl<T, const N: usize> Matrix<T, N, N>
where
T: SemiRing + Copy,
{
pub fn matpow(&self, mut n: usize) -> Self {
let mut t = Self::one();
let mut r = *self;
while n > 0 {
if n & 1 == 1 {
t = t * r;
}
r = r * r;
n >>= 1;
}
t
}
// I + A + .. + A^(n-1)
pub fn powsum(&self, n: usize) -> Self {
if n == 0 {
return Self::zero();
}
if n & 1 == 1 {
Self::one() + *self * self.powsum(n - 1)
} else {
(Self::one() + *self) * (*self * *self).powsum(n / 2)
}
}
}
impl<T, const R: usize, const C: usize, const M: usize> Mul<Matrix<T, C, M>> for Matrix<T, R, C>
where
T: Zero + Mul<Output = T> + Copy,
{
type Output = Matrix<T, R, M>;
fn mul(self, rhs: Matrix<T, C, M>) -> Self::Output {
self.matmul(&rhs)
}
}
impl<T, const R: usize, const C: usize> Index<usize> for Matrix<T, R, C> {
type Output = [T; C];
fn index(&self, x: usize) -> &Self::Output {
&self.0[x]
}
}
impl<T, const R: usize, const C: usize> IndexMut<usize> for Matrix<T, R, C> {
fn index_mut(&mut self, x: usize) -> &mut Self::Output {
&mut self.0[x]
}
}
// ---------- end const matrix ----------
// ---------- begin segment tree Point Update Range Query ----------
pub struct SegmentTreePURQ<T, F> {
n: usize,
size: usize,
data: Vec<T>,
e: T,
op: F,
}
impl<T, F> SegmentTreePURQ<T, F>
where
T: Clone,
F: Fn(&T, &T) -> T,
{
pub fn new(n: usize, e: T, op: F) -> Self {
assert!(n > 0);
let size = n.next_power_of_two();
let data = vec![e.clone(); 2 * size];
SegmentTreePURQ {
n,
size,
data,
e,
op,
}
}
pub fn update_tmp(&mut self, x: usize, v: T) {
assert!(x < self.n);
self.data[x + self.size] = v;
}
pub fn update_all(&mut self) {
for i in (1..self.size).rev() {
self.data[i] = (self.op)(&self.data[2 * i], &self.data[2 * i + 1]);
}
}
pub fn update(&mut self, x: usize, v: T) {
assert!(x < self.n);
let mut x = x + self.size;
self.data[x] = v;
x >>= 1;
while x > 0 {
self.data[x] = (self.op)(&self.data[2 * x], &self.data[2 * x + 1]);
x >>= 1;
}
}
pub fn find(&self, l: usize, r: usize) -> T {
assert!(l <= r && r <= self.n);
if l == r {
return self.e.clone();
}
let mut l = self.size + l;
let mut r = self.size + r;
let mut x = self.e.clone();
let mut y = self.e.clone();
while l < r {
if l & 1 == 1 {
x = (self.op)(&x, &self.data[l]);
l += 1;
}
if r & 1 == 1 {
r -= 1;
y = (self.op)(&self.data[r], &y);
}
l >>= 1;
r >>= 1;
}
(self.op)(&x, &y)
}
pub fn max_right<P>(&self, l: usize, f: P) -> usize
where
P: Fn(&T) -> bool,
{
assert!(l <= self.n);
assert!(f(&self.e));
if l == self.n {
return self.n;
}
let mut l = l + self.size;
let mut sum = self.e.clone();
while {
l >>= l.trailing_zeros();
let v = (self.op)(&sum, &self.data[l]);
if !f(&v) {
while l < self.size {
l <<= 1;
let v = (self.op)(&sum, &self.data[l]);
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>(&self, r: usize, f: P) -> usize
where
P: Fn(&T) -> bool,
{
assert!(r <= self.n);
assert!(f(&self.e));
if r == 0 {
return 0;
}
let mut r = r + self.size;
let mut sum = self.e.clone();
while {
r -= 1;
while r > 1 && r & 1 == 1 {
r >>= 1;
}
let v = (self.op)(&self.data[r], &sum);
if !f(&v) {
while r < self.size {
r = 2 * r + 1;
let v = (self.op)(&self.data[r], &sum);
if f(&v) {
sum = v;
r -= 1;
}
}
return r + 1 - self.size;
}
sum = v;
(r & (!r + 1)) != r
} {}
0
}
}
// ---------- end segment tree Point Update Range Query ----------