管理する情報

文字列 \(S\) に加えて次の情報を、順序集合データ構造（C++ 標準の std::set、Rust 標準の std::collections::BTreeSet など）で管理します。

1. \(S\) において \(i\) 文字目が \(i + 1\) 文字目よりも大きいような \(0 \le i \le N\) 全体の集合 \(D\)（ただし \(S\) の \(0\) 文字目は a 、\(N + 1\) 文字目は z であると解釈します。）

2. 各アルファベット \(c\) について、その \(S\) における出現位置 \(1 \le i \le N\) 全体の集合 \(P _ c\)

これは \(O(\sigma + N \sigma \log N)\) 時間で前計算することができます。

クエリの捌き方

問題の 2 種類のクエリには次のように対応します。

• \(S\) の \(i\) 文字目を文字 \(c\) で置き換えるクエリ （\(O ( \log N )\) 時間）:
  • \(i - 1, i\) を適宜 \(D\) に挿入または削除します。
  • \(i\) を \(P _ { S _ i }, P _ c\) に挿入または削除します。
  • \(S\) を更新します。
• \(S\) の \(l\) 文字目から \(r\) 文字目までからなる文字列が \(T\) の部分文字列であるかどうかを判定するクエリ （\(O ( \sigma \lg N)\) 時間） :
  • ソート済みであるかどうかは \(D\) を見れば \(O ( \log N )\) 時間でわかります。
  • 特定の文字 \(c\) が \(l\) 文字目から \(r\) 文字目登場するかどうかやその区間にすべて登場しているかどうかは、\(P _ c\) を見れば \(O ( \lg N )\) 時間でわかります。

実装例 (Rust, 334 ms)

提出へのリンク

実装の簡単のため、前後に番兵を入れています。

use proconio::input;
use std::{iter::once, mem::replace, collections::BTreeSet};

fn main() {
  input! { n: usize, s: String, q: usize }
  let mut s = once(0).chain(s.chars().map(|c| c as usize - b'a' as usize)).chain(once(25)).collect::<Vec<_>>();
  let mut positions = vec![BTreeSet::new(); 26];
  let mut descents = BTreeSet::new();
  for i in 1..=n {
    positions[s[i]].insert(i);
    if s[i] > s[i + 1] {
      descents.insert(i);
    }
  }
  for _ in 0..q {
    input! { query_type: u8 }
    match query_type {
      1 => {
        input! { i: usize, c1: char }
        let c1 = c1 as usize - b'a' as usize;
        let c0 = replace(&mut s[i], c1);
        if c0 != c1 {
          positions[c0].remove(&i);
          positions[c1].insert(i);
          for &i in &[i - 1, i] {
            if s[i] > s[i + 1] {
              descents.insert(i);
            } else {
              descents.remove(&i);
            }
          }
        }
      }
      2 => {
        input! { start: usize, end: usize }
        let end = end + 1;
        let ans = descents.range(start..end - 1).next().is_none() && {
          let min_char = positions.iter().position(|set| set.range(start..end).next().is_some()).unwrap();
          let max_char = positions.iter().rposition(|set| set.range(start..end).next().is_some()).unwrap();
          min_char == max_char || positions[min_char + 1..max_char].iter().all(|set| set.range(..start).next().is_none() && set.range(end..).next().is_none())
        };
        println!("{}", ["No", "Yes"][ans as usize]);
      }
      _ => unreachable!(),
    }
  }
}