ABC157E

問題

E - Simple String Queries

解法

クエリの回数分、文字目から文字目まで調べるのでは間に合わない。

そこで、各アルファベット毎に、以上で初めて登場する位置を探索し、その位置が以下だった場合、種類を増やすことにする。

始めて登場する位置は、各アルファベット毎に位置を昇順に持っておいたものから、二分探索することで求めることができる。

文字を変更する場合、変更前の文字は削除する位置を二分探索で探し、変更後の文字は挿入する位置を二分探索で探せばよい。

計算量は。ただし、に26の定数倍がある。

コード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#define all(x) (x).begin(),(x).end()

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N; cin >> N;
  string S; cin >> S;
  vector<vector<int>> v(26);
  for (int i = 0; i < N; i++) {
    v[S[i]-'a'].push_back(i);
  }
  int Q; cin >> Q;
  for (int k = 0; k < Q; k++) {
    int type; cin >> type;
    if (type == 1) {
      int i; cin >> i; i--;
      char c; cin >> c;
      if (S[i] == c) continue;
      int j = S[i] - 'a';
      v[j].erase(lower_bound(all(v[j]), i));
      S[i] = c;
      j = c - 'a';
      v[j].insert(lower_bound(all(v[j]), i), i);
    }
    else {
      int l, r; cin >> l >> r; l--; r--;
      int ans = 0;
      for (int i = 0; i < 26; i++) {
        if (v[i].empty()) continue;
        int index = lower_bound(all(v[i]), l) - v[i].begin();
        if (index < v[i].size() && v[i][index] <= r) ans++;
      }
      cout << ans << "\n";
    }
  }
}

感想

セグメント木を多少触ったばかりだったので、流石にその方法で解くことはできなかった。

また、この解法では位置を持っておくためにvectorを使用しているが、今回の場合はsetというデータ構造の方が明らかに便利なので、次からはそちらを使うようにしたい。