← 返回题单

题单练习树状数组

← 上一题下一题 →

A6915 | $不同字符查询$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一个只包含小写拉丁字母的字符串 $s$，以及 $q$ 个关于该字符串的查询。 回忆一下，字符串 $s[l;r]$ 的子串是 $s_l s_{l+1}\dots s_r$。例如，"acgo" 的子串有 "ac”、"go"、"cg"、"acgo"，但没有 "og" 和 "top"。 查询有两种类型： $1\ pos\ c$（$1 \le pos \le |s|$，$c$ 为小写拉丁字母）：将 $s_{pos}$ 替换为 $c$（即 $s_{pos}:=c$）。 $2\ l\ r$（$1 \le l \le r \le |s|$）：计算子串 $s[l;r]$ 中不同字符的数量。

输入格式

第一行输入一个字符串 $s$，由不超过 $10^5$ 个小写拉丁字母组成。 第二行输入一个整数 $q$（$1 \le q \le 10^5$），表示查询的数量。 接下来的 $q$ 行，每行一个查询，格式如题目描述所示。保证至少有一个第二类查询。

输出格式

对于每个第二类查询，输出该查询所要求的子串中不同字符的数量。

输入输出样例

输入 #1

abacaba
5
2 1 4
1 4 b
1 5 b
2 4 6
2 1 7

输出 #1

3
1
2

输入 #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

输出 #2

C++ 编辑器

输入

输出