D. Distinct Characters Queries(set维护)_资讯

D. Distinct Characters Queries(set维护)

创始人

2024-05-02 18:24:59

0次

Problem - 1234D - Codeforces

给你一个由小写拉丁字母组成的字符串s和对这个字符串的q个查询。

回顾一下，字符串s的子串s[l;r]就是字符串slsl+1...sr。例如，"codeforces "的子串是 "code"、"force"、"f"、"for"，但不是 "coder "和 "top"。

有两种类型的查询。

1 pos c (1≤pos≤|s|，c为小写拉丁字母)：用c替换 spos (set spos:=c)。
2 l r (1≤l≤r≤|s|)：计算子串s[l;r]中不同字符的数量。
输入
输入的第一行包含一个由不超过105个小写拉丁字母组成的字符串s。

输入的第二行包含一个整数q（1≤q≤105）--查询的数量。

接下来的q行包含查询，每行一个。每个查询都是按照问题陈述中描述的格式给出的。保证至少有一个第二种类型的查询。

输出
对于每一个第二种类型的查询，打印出它的答案--在这个查询中所要求的子串中的明显字符数。

例子
inputCopy
abacaba
5
2 1 4
1 4 b
1 5 b
2 4 6
2 1 7
输出拷贝
3
1
2
输入拷贝
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
输出拷贝
5
2
5
2
6

题解:

用set存储每个字母的下标

每次要修改时就把当前s[i]的中的下标删去

再把要修改的字母把下标插入

更改此时的s[i] = c

如果要查询,我们直接进性26次二分找存储在当前字母中的下标是在l~r内

注意set.end()并不是存储数的最后一位

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define int long long
typedef pair PII;
char a[200050];
set st[27];
void solve()
{cin >> a+1;int n = strlen(a+1);for(int i  =1;i <= n;i++){st[a[i]-'a'].insert(i);}int q;cin >> q;while(q--){int p ;cin >>p;if(p == 1){int x;char c;cin >> x >> c;st[a[x]-'a'].erase(x);st[c-'a'].insert(x);a[x] = c;		}else{int l,r;cin >> l >> r;int s = 0;for(int j = 0;j < 26;j++){auto p = st[j].lower_bound(l);if(p!=st[j].end()&&*p <= r){s ++;}}cout << s<<"\n";}}
}
//cbc cbb
//7 3 1
//6 5 4 
signed main(){
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cout.tie(0);int t = 1;
//	cin >> t;while(t--){solve();} 
}
//5
//2 4 6 8 10 7 9 5 3 1
//1 3 5 7 9 6 8 4 2
//2 4 1 3

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：编程小技巧9-如何生成没有水印的代码图片（IDEA carbon-now-sh插件使用教程）

下一篇：CSS3知识点精学

D. Distinct Characters Queries(set维护)

相关内容

热门资讯