算法
(平衡二分搜索木) $O(26*Q\log N)$
这题的普遍做法是利用线段树或树状数组通过统计每个区间中每个字母的出现次数来实现快速查询,比较模版。
这里介绍一种用 set
的做法:我们可以利用 set
的 erase
函数以 $O(\log N)$ 的时间处理类型 $1$ 的单点修改,以及 insert
函数能以 $O(\log N)$ 的时间处理类型 $2$ 的查询,方法是利用每个字母的 lower_bound
函数来找到它在 $l_q$ 之后首次出现的位置,然后将这个值与 $r_q$ 进行比较。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::string;
using std::vector;
using std::set;
int main() {
int n, q;
string s;
cin >> n >> s >> q;
vector<set<int>> is(26);
rep(i, n) is[s[i] - 'a'].insert(i);
rep(qi, q) {
int ty;
cin >> ty;
if (ty == 1) {
int i; char c;
cin >> i >> c;
--i;
is[s[i] - 'a'].erase(i);
s[i] = c;
is[s[i] - 'a'].insert(i);
}
else {
int l, r;
cin >> l >> r;
--l;
int ans = 0;
rep(i, 26) {
auto it = is[i].lower_bound(l);
if (it != is[i].end() && *it < r) ++ans;
}
cout << ans << '\n';
}
}
return 0;
}