結果
問題 | No.2361 Many String Compare Queries |
ユーザー |
|
提出日時 | 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 |
ソースコード
use std::io::{Write, BufWriter};// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8macro_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/25662432fn 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: 1let 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/704334struct 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 1return 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/27734236pub trait ActionRing {type T: Clone + Copy; // datatype U: Clone + Copy + PartialEq + Eq; // actionfn 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 2LazySegTree {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 typeimpl ActionRing for Affine {type T = (AffineInt, AffineInt); // data, sizetype U = (AffineInt, AffineInt); // action, (a, b) |-> x |-> ax + bfn 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);}}