#|D. Distinct Characters Queries（set处理） Codeforces Round #590 (Div. 3) #|2019级暑期第二场训练赛|STL的

原题链接： https://codeforces.com/contest/1234/problem/D

文章图片

测试样例：

Input
abacaba
5
2 1 4
1 4 b
1 5 b
2 4 6
2 1 7
Output
3
1
2
Input
dfcbbcfeeedbaea
15
1 6 e
1 4 b
2 6 14
1 7 b
1 12 c
2 6 8
2 1 6
1 7 c
1 2 f
1 10 a
2 7 9
1 10 a
1 14 b
1 1 f
2 1 11
Output
5
2
5
2
6

解题思路：这道题本来想用线段树做，可却根本不知道结点元素值该存什么。这里我们可以使用set容器来处理，由于我们题目的关键就是查询区间 [ l , r ] [l,r] [l,r]有多少不同的字符。我们可以用26个set容器存储26个字符所对应的下标，那么我们查询统计的时候就可以利用函数low_bound来二分查找第一个大于等于 l l l的下标，再判断该下标是否存在以及是否在区间内即可。对于改写的时候也方便，我们获取原来字符串中位置字符，再将这个字符对应的下标删除，同时将新改的字符的下标放到对应set容器即可。OK，具体看代码。
【#|D. Distinct Characters Queries（set处理） Codeforces Round #590 (Div. 3)】AC代码：

/* *邮箱：unique_powerhouse@qq.com *blog:https://me.csdn.net/hzf0701 *注：文章若有任何问题请私信我或评论区留言，谢谢支持。 * */ #include //POJ不支持#define rep(i,a,n) for (int i=a; i<=n; i++)//i为循环变量，a为初始值，n为界限值，递增 #define per(i,a,n) for (int i=a; i>=n; i--)//i为循环变量， a为初始值，n为界限值，递减。 #define pb push_back #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define fi first #define se second #define mp make_pairusing namespace std; const int inf = 0x3f3f3f3f; //无穷大 const int maxn = 1e5; //最大值。 typedef long long ll; typedef long double ld; typedef pairpll; typedef pair pii; //*******************************分割线，以上为自定义代码模板***************************************//int t,q; set s[26]; //存储26个字符对应的下标。 string str; void change(int x,char ch){ char temp=str[x]; //将这个位置上的元素删掉，替换为ch。 s[temp-'a'].erase(x); str[x]=ch; s[ch-'a'].insert(x); } void query(int l,int r){ int ans=0; rep(i,0,25){ set::iterator it=s[i].lower_bound(l); if(it!=s[i].end()&&*it<=r) ans++; } cout<>str){ rep(i,0,25){ s[i].clear(); } int len=str.size(); rep(i,0,len-1){ s[str[i]-'a'].insert(i); } cin>>q; int op; int l,r,pos; char ch; while(q--){ cin>>op; if(op==1){ cin>>pos>>ch; change(pos-1,ch); //因为下标从0开始，我们自然要减1. } else{ cin>>l>>r; query(l-1,r-1); } } } return 0; }