【1234D】Distinct Characters Queries(数据结构)

发布时间 2023-08-30 20:03:54作者: Alric

题目大意:

有一个字符串(只有小写字母),支持两种操作:

  1. 修改某个位置的字母为另一个小写字母

  2. 查询一段区间不同的字母数量


由于小写字母只有26个,考虑将每个字母分开处理。

对于每个字母,使用一个set储存该字母所出现过的位置。

对于修改操作,使用erase和insert函数即可。

对于查询操作,我们分别判断每个字母是否在给定的区间\([l,r]\)内,判断的方法为:用lower_bound函数找到大于\(l\),且最接近\(l\)的位置,如果这个位置不在\(r\)的右边,则说明字母存在于区间内。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[100000+10];
ll n,q;
set<ll> sit[26];
int main(){
	cin >> (s+1) >> q;
	n=strlen(s+1);
	for(ll i=1;i<=n;i++){
		sit[s[i]-'a'].insert(i);
	}
	for(ll i=1;i<=q;i++){
		ll type;
		cin >> type;
		if(type==1){
			ll pos;
			char c;
			cin >> pos >> c;
			for(ll i=0;i<26;i++){
				sit[i].erase(pos);
			}
			sit[c-'a'].insert(pos);
		}else if(type==2){
			ll l,r,cnt=0;
			cin >> l >> r;
			for(ll i=0;i<26;i++){
				if(*sit[i].lower_bound(l)<=r&&sit[i].lower_bound(l)!=sit[i].end()){
					cnt++;
				}
			}
			cout << cnt << endl;
		}
	}
	return 0;
}