結果

問題 No.2361 Many String Compare Queries
ユーザー koba-e964
提出日時 2023-06-26 11:18:39
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 847 ms / 2,500 ms
コード長 17,442 bytes
コンパイル時間 17,183 ms
コンパイル使用メモリ 377,540 KB
実行使用メモリ 59,424 KB
最終ジャッジ日時 2024-07-03 05:49:26
合計ジャッジ時間 24,027 ms
ジャッジサーバーID
(参考情報)
judge1 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
($($r:tt)*) => {
let stdin = std::io::stdin();
let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
let mut next = move || -> String{
bytes.by_ref().map(|r|r.unwrap() as char)
.skip_while(|c|c.is_whitespace())
.take_while(|c|!c.is_whitespace())
.collect()
};
input_inner!{next, $($r)*}
};
}
macro_rules! input_inner {
($next:expr) => {};
($next:expr,) => {};
($next:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($next, $t);
input_inner!{$next $($r)*}
};
}
macro_rules! read_value {
($next:expr, ( $($t:tt),* )) => { ($(read_value!($next, $t)),*) };
($next:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
};
($next:expr, chars) => {
read_value!($next, String).chars().collect::<Vec<char>>()
};
($next:expr, usize1) => (read_value!($next, usize) - 1);
($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error"));
}
// https://github.com/rust-lang-ja/ac-library-rs/blob/master/src/string.rs
// Verified by: https://atcoder.jp/contests/abc213/submissions/25662432
fn sa_naive<T: Ord>(s: &[T]) -> Vec<usize> {
let n = s.len();
let mut sa: Vec<usize> = (0..n).collect();
sa.sort_by(|&(mut l), &(mut r)| {
if l == r {
return std::cmp::Ordering::Equal;
}
while l < n && r < n {
if s[l] != s[r] {
return s[l].cmp(&s[r]);
}
l += 1;
r += 1;
}
if l == n {
std::cmp::Ordering::Less
} else {
std::cmp::Ordering::Greater
}
});
sa
}
fn sa_doubling(s: &[i32]) -> Vec<usize> {
let n = s.len();
let mut sa: Vec<usize> = (0..n).collect();
let mut rnk: Vec<i32> = s.to_vec();
let mut tmp = vec![0; n];
let mut k = 1;
while k < n {
let cmp = |&x: &usize, &y: &usize| {
if rnk[x] != rnk[y] {
return rnk[x].cmp(&rnk[y]);
}
let rx = if x + k < n { rnk[x + k] } else { -1 };
let ry = if y + k < n { rnk[y + k] } else { -1 };
rx.cmp(&ry)
};
sa.sort_by(cmp);
tmp[sa[0]] = 0;
for i in 1..n {
tmp[sa[i]] = tmp[sa[i - 1]]
+ if cmp(&sa[i - 1], &sa[i]) == std::cmp::Ordering::Less {
1
} else {
0
};
}
std::mem::swap(&mut tmp, &mut rnk);
k *= 2;
}
sa
}
trait Threshold {
fn threshold_naive() -> usize;
fn threshold_doubling() -> usize;
}
enum DefaultThreshold {}
impl Threshold for DefaultThreshold {
fn threshold_naive() -> usize {
10
}
fn threshold_doubling() -> usize {
40
}
}
// |returned| = |s|
// Complexity: O(|s| upper)
#[allow(clippy::cognitive_complexity)]
fn sa_is<T: Threshold>(s: &[usize], upper: usize) -> Vec<usize> {
let n = s.len();
match n {
0 => return vec![],
1 => return vec![0],
2 => return if s[0] < s[1] { vec![0, 1] } else { vec![1, 0] },
_ => (),
}
if n < T::threshold_naive() {
return sa_naive(s);
}
if n < T::threshold_doubling() {
let s: Vec<i32> = s.iter().map(|&x| x as i32).collect();
return sa_doubling(&s);
}
let mut sa = vec![0; n];
let mut ls = vec![false; n];
for i in (0..n - 1).rev() {
ls[i] = if s[i] == s[i + 1] {
ls[i + 1]
} else {
s[i] < s[i + 1]
};
}
let mut sum_l = vec![0; upper + 1];
let mut sum_s = vec![0; upper + 1];
for i in 0..n {
if !ls[i] {
sum_s[s[i]] += 1;
} else {
sum_l[s[i] + 1] += 1;
}
}
for i in 0..=upper {
sum_s[i] += sum_l[i];
if i < upper {
sum_l[i + 1] += sum_s[i];
}
}
// sa's origin is 1.
let induce = |sa: &mut [usize], lms: &[usize]| {
for elem in sa.iter_mut() {
*elem = 0;
}
let mut buf = sum_s.clone();
for &d in lms {
if d == n {
continue;
}
let old = buf[s[d]];
buf[s[d]] += 1;
sa[old] = d + 1;
}
buf.copy_from_slice(&sum_l);
let old = buf[s[n - 1]];
buf[s[n - 1]] += 1;
sa[old] = n;
for i in 0..n {
let v = sa[i];
if v >= 2 && !ls[v - 2] {
let old = buf[s[v - 2]];
buf[s[v - 2]] += 1;
sa[old] = v - 1;
}
}
buf.copy_from_slice(&sum_l);
for i in (0..n).rev() {
let v = sa[i];
if v >= 2 && ls[v - 2] {
buf[s[v - 2] + 1] -= 1;
sa[buf[s[v - 2] + 1]] = v - 1;
}
}
};
// origin: 1
let mut lms_map = vec![0; n + 1];
let mut m = 0;
for i in 1..n {
if !ls[i - 1] && ls[i] {
lms_map[i] = m + 1;
m += 1;
}
}
let mut lms = Vec::with_capacity(m);
for i in 1..n {
if !ls[i - 1] && ls[i] {
lms.push(i);
}
}
assert_eq!(lms.len(), m);
induce(&mut sa, &lms);
if m > 0 {
let mut sorted_lms = Vec::with_capacity(m);
for &v in &sa {
if lms_map[v - 1] != 0 {
sorted_lms.push(v - 1);
}
}
let mut rec_s = vec![0; m];
let mut rec_upper = 0;
rec_s[lms_map[sorted_lms[0]] - 1] = 0;
for i in 1..m {
let mut l = sorted_lms[i - 1];
let mut r = sorted_lms[i];
let end_l = if lms_map[l] < m { lms[lms_map[l]] } else { n };
let end_r = if lms_map[r] < m { lms[lms_map[r]] } else { n };
let same = if end_l - l != end_r - r {
false
} else {
while l < end_l {
if s[l] != s[r] {
break;
}
l += 1;
r += 1;
}
l != n && s[l] == s[r]
};
if !same {
rec_upper += 1;
}
rec_s[lms_map[sorted_lms[i]] - 1] = rec_upper;
}
let rec_sa = sa_is::<T>(&rec_s, rec_upper);
for i in 0..m {
sorted_lms[i] = lms[rec_sa[i]];
}
induce(&mut sa, &mut sorted_lms);
}
for elem in sa.iter_mut() {
*elem -= 1;
}
sa
}
fn suffix_array_lowercase(s: &[char]) -> Vec<usize> {
let s: Vec<usize> = s.iter().map(|&x| (x as u8 - b'a') as usize).collect();
sa_is::<DefaultThreshold>(&s, 25)
}
// s.len() == sa.len() must hold.
// Verified by: https://yukicoder.me/submissions/704334
struct LCP {
inv_sa: Vec<usize>,
spt: Vec<Vec<usize>>,
}
impl LCP {
pub fn new<T: Ord>(s: &[T], sa: &[usize]) -> LCP {
let n = sa.len();
assert_eq!(s.len(), n);
let mut inv_sa = vec![0; n];
for i in 0..n {
inv_sa[sa[i]] = i;
}
let lcp = Self::create_lcp(s, sa);
let spt = Self::create_sparse_table(&lcp);
LCP {
inv_sa: inv_sa,
spt: spt,
}
}
fn create_lcp<T: Ord>(s: &[T], sa: &[usize]) -> Vec<usize> {
let n = s.len();
let mut rank = vec![0; n];
let mut lcp = vec![0; n - 1];
for i in 0..n {
rank[sa[i]] = i;
}
let mut h: usize = 0;
for i in 0..n {
if rank[i] == 0 {
continue;
}
let j = sa[rank[i] - 1];
h = h.saturating_sub(1);
while j + h < n && i + h < n {
if s[j + h] != s[i + h] {
break;
}
h += 1;
}
lcp[rank[i] - 1] = h;
}
return lcp;
}
fn create_sparse_table(lcp: &[usize]) -> Vec<Vec<usize>> {
let n = lcp.len();
let mut h: usize = 1;
while (1 << h) <= n {
h += 1;
}
let mut st: Vec<Vec<usize>> = vec![Vec::new(); h];
st[0] = Vec::from(lcp);
for j in 1 .. h {
st[j] = vec![0; n + 1 - (1 << j)];
for i in 0 .. n + 1 - (1 << j) {
st[j][i] = std::cmp::min(
st[j - 1][i],
st[j - 1][i + 1_usize.wrapping_shl(j as u32 - 1)]);
}
}
return st;
}
pub fn get_lcp(&self, f: usize, s: usize) -> usize {
let n = self.inv_sa.len();
if f == n || s == n {
return 0;
}
let f = self.inv_sa[f];
let s = self.inv_sa[s];
let (f, s) =
if f > s {
(s, f)
} else {
(f, s)
};
assert!(f < s);
let usize_size = usize::max_value().count_ones();
let diff = usize_size - 1 - (s - f).leading_zeros(); // topmost 1
return std::cmp::min(self.spt[diff as usize][f],
self.spt[diff as usize][s - 1_usize.wrapping_shl(diff)]);
}
}
// Lazy Segment Tree. This data structure is useful for fast folding and updating on intervals of an array
// whose elements are elements of monoid T. Note that constructing this tree requires the identity
// element of T and the operation of T. This is monomorphised, because of efficiency. T := i64, biop = max, upop = (+)
// Reference: https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp
// Verified by: https://judge.yosupo.jp/submission/68794
// https://atcoder.jp/contests/joisc2021/submissions/27734236
pub trait ActionRing {
type T: Clone + Copy; // data
type U: Clone + Copy + PartialEq + Eq; // action
fn biop(x: Self::T, y: Self::T) -> Self::T;
fn update(x: Self::T, a: Self::U) -> Self::T;
fn upop(fst: Self::U, snd: Self::U) -> Self::U;
fn e() -> Self::T;
fn upe() -> Self::U; // identity for upop
}
pub struct LazySegTree<R: ActionRing> {
n: usize,
dep: usize,
dat: Vec<R::T>,
lazy: Vec<R::U>,
}
impl<R: ActionRing> LazySegTree<R> {
pub fn new(n_: usize) -> Self {
let mut n = 1;
let mut dep = 0;
while n < n_ { n *= 2; dep += 1; } // n is a power of 2
LazySegTree {
n: n,
dep: dep,
dat: vec![R::e(); 2 * n],
lazy: vec![R::upe(); n],
}
}
#[allow(unused)]
pub fn with(a: &[R::T]) -> Self {
let mut ret = Self::new(a.len());
let n = ret.n;
for i in 0..a.len() {
ret.dat[n + i] = a[i];
}
for i in (1..n).rev() {
ret.update_node(i);
}
ret
}
#[inline]
pub fn set(&mut self, idx: usize, x: R::T) {
debug_assert!(idx < self.n);
self.apply_any(idx, |_t| x);
}
#[inline]
pub fn apply(&mut self, idx: usize, f: R::U) {
debug_assert!(idx < self.n);
self.apply_any(idx, |t| R::update(t, f));
}
pub fn apply_any<F: Fn(R::T) -> R::T>(&mut self, idx: usize, f: F) {
debug_assert!(idx < self.n);
let idx = idx + self.n;
for i in (1..self.dep + 1).rev() {
self.push(idx >> i);
}
self.dat[idx] = f(self.dat[idx]);
for i in 1..self.dep + 1 {
self.update_node(idx >> i);
}
}
pub fn get(&mut self, idx: usize) -> R::T {
debug_assert!(idx < self.n);
let idx = idx + self.n;
for i in (1..self.dep + 1).rev() {
self.push(idx >> i);
}
self.dat[idx]
}
/* [l, r) (note: half-inclusive) */
#[inline]
pub fn query(&mut self, rng: std::ops::Range<usize>) -> R::T {
let (l, r) = (rng.start, rng.end);
debug_assert!(l <= r && r <= self.n);
if l == r { return R::e(); }
let mut l = l + self.n;
let mut r = r + self.n;
for i in (1..self.dep + 1).rev() {
if ((l >> i) << i) != l { self.push(l >> i); }
if ((r >> i) << i) != r { self.push((r - 1) >> i); }
}
let mut sml = R::e();
let mut smr = R::e();
while l < r {
if (l & 1) != 0 {
sml = R::biop(sml, self.dat[l]);
l += 1;
}
if (r & 1) != 0 {
r -= 1;
smr = R::biop(self.dat[r], smr);
}
l >>= 1;
r >>= 1;
}
R::biop(sml, smr)
}
/* ary[i] = upop(ary[i], v) for i in [l, r) (half-inclusive) */
#[inline]
pub fn update(&mut self, rng: std::ops::Range<usize>, f: R::U) {
let (l, r) = (rng.start, rng.end);
debug_assert!(l <= r && r <= self.n);
if l == r { return; }
let mut l = l + self.n;
let mut r = r + self.n;
for i in (1..self.dep + 1).rev() {
if ((l >> i) << i) != l { self.push(l >> i); }
if ((r >> i) << i) != r { self.push((r - 1) >> i); }
}
{
let l2 = l;
let r2 = r;
while l < r {
if (l & 1) != 0 {
self.all_apply(l, f);
l += 1;
}
if (r & 1) != 0 {
r -= 1;
self.all_apply(r, f);
}
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for i in 1..self.dep + 1 {
if ((l >> i) << i) != l { self.update_node(l >> i); }
if ((r >> i) << i) != r { self.update_node((r - 1) >> i); }
}
}
#[inline]
fn update_node(&mut self, k: usize) {
self.dat[k] = R::biop(self.dat[2 * k], self.dat[2 * k + 1]);
}
fn all_apply(&mut self, k: usize, f: R::U) {
self.dat[k] = R::update(self.dat[k], f);
if k < self.n {
self.lazy[k] = R::upop(self.lazy[k], f);
}
}
fn push(&mut self, k: usize) {
let val = self.lazy[k];
self.all_apply(2 * k, val);
self.all_apply(2 * k + 1, val);
self.lazy[k] = R::upe();
}
}
enum Affine {}
type AffineInt = i64; // Change here to change type
impl ActionRing for Affine {
type T = (AffineInt, AffineInt); // data, size
type U = (AffineInt, AffineInt); // action, (a, b) |-> x |-> ax + b
fn biop((x, s): Self::T, (y, t): Self::T) -> Self::T {
(x + y, s + t)
}
fn update((x, s): Self::T, (a, b): Self::U) -> Self::T {
(x * a + b * s, s)
}
fn upop(fst: Self::U, snd: Self::U) -> Self::U {
let (a, b) = fst;
let (c, d) = snd;
(a * c, b * c + d)
}
fn e() -> Self::T {
(0.into(), 0.into())
}
fn upe() -> Self::U { // identity for upop
(1.into(), 0.into())
}
}
fn main() {
let out = std::io::stdout();
let mut out = BufWriter::new(out.lock());
macro_rules! puts {($($format:tt)*) => (let _ = write!(out,$($format)*););}
input! {
n: usize, q: usize,
s: chars,
lr: [(usize1, usize); q],
}
let sa = suffix_array_lowercase(&s);
let mut acc = vec![0; n + 1];
for i in 0..n {
acc[i + 1] = acc[i] + (n - sa[i]) as i64;
}
let lcp = LCP::new(&s, &sa);
let mut right_vals = vec![0; n + 1];
let mut st = LazySegTree::<Affine>::new(n);
let mut stc = LazySegTree::<Affine>::new(n);
for i in 0..n {
st.set(i, (0, 1));
stc.set(i, (0, 1));
}
for i in (0..n).rev() {
let cur = if i == n - 1 { 0 } else { lcp.get_lcp(sa[i], sa[i + 1]) };
let count = st.query(cur + 1..n).0;
st.update(cur + 1..n, (0, 0));
stc.update(cur + 1..n, (0, 0));
st.update(cur..cur + 1, (1, count + 1));
stc.update(cur..cur + 1, (1, (count + 1) * cur as i64));
right_vals[i] = stc.query(0..n).0;
}
// eprintln!("right_vals = {:?}", right_vals);
for (l, r) in lr {
let len = r - l;
let left = {
let mut pass = 0;
let mut fail = lcp.inv_sa[l] + 1;
while fail - pass > 1 {
let mid = (fail + pass) / 2;
if lcp.get_lcp(sa[lcp.inv_sa[l] - mid], l) >= len {
pass = mid;
} else {
fail = mid;
}
}
pass
};
let right = {
let mut pass = 1;
let mut fail = n - lcp.inv_sa[l] + 1;
while fail - pass > 1 {
let mid = (fail + pass) / 2;
if lcp.get_lcp(sa[lcp.inv_sa[l] + mid - 1], l) >= len {
pass = mid;
} else {
fail = mid;
}
}
pass
};
let mut ans = acc[lcp.inv_sa[l] - left]; // [0, lcp.inv_sa[l] - left)
ans += (left + right) as i64 * (len - 1) as i64; // [lcp.inv_sa[l] - left, lcp.inv_sa[l] + right)
// [lcp.inv_sa[l] + right, n)
ans += right_vals[lcp.inv_sa[l] + right - 1];
puts!("{}\n", ans);
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0