結果
| 問題 | No.2361 Many String Compare Queries |
| ユーザー |
 koba-e964
|
| 提出日時 | 2023-06-24 16:11:37 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 11,094 bytes |
| コンパイル時間 | 14,748 ms |
| コンパイル使用メモリ | 380,256 KB |
| 実行使用メモリ | 37,132 KB |
| 最終ジャッジ日時 | 2024-07-01 19:08:57 |
| 合計ジャッジ時間 | 18,588 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 7 WA * 7 |
ソースコード
#[allow(unused_imports)]use std::cmp::*;#[allow(unused_imports)]use std::collections::*;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:tt ]) => {{let len = read_value!($next, usize);read_value!($next, [$t; len])}};($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)]);}}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);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];ans += (left + right) as i64 * (len - 1) as i64;puts!("{}\n", ans);}}