← 返回题目列表

AtCoder · abc157_e

E. 简单字符串查询

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

给你一个字符串 S 长度 N 由小写英文字母组成。

流程 Q 以下两种类型的查询:

  • 类型 1:更改 i_q- 第一个字符 S to c_q。 (如果 i_q- 第一个字符已经 c_q.)
  • 类型 2:回答子串中出现的不同字符的个数 S 之间 l_q-th 和 r_q个字符(含)。

约束

  • N, Q, i_q, l_q,和 r_q 是整数。
  • S 是由小写英文字母组成的字符串。
  • c_q 是一个小写英文字母。
  • 1 \leq N \leq 500000
  • 1 \leq Q \leq 20000
  • |S| = N
  • 1 \leq i_q \leq N
  • 1 \leq l_q \leq r_q \leq N
  • 至少有一个类型为 每个测试用例中的 2 。

输入

输入由标准输入按以下格式给出:

N
S
Q
Query_1
\vdots
Query_Q

在这里, Query_i 在 4-th 至 (Q+3)-第行是以下之一:

1 i_q c_q
2 l_q r_q

输出

对于每个类型的查询 2,打印包含答案的行。


示例输入 1

7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7

示例输出 1

3
1
5

在第一个查询中, cdbb 包含三种字母: b , c ,和 d,所以我们打印 3.

在第二个查询中, S 修改为 abcdzbd.

在第三个查询中, a 包含一种字母: a,所以我们打印 1.

在第四个查询中, S 修改为 abcazbd.

在第五个查询中, S 没有改变,仍然是 abcazbd.

在第六个查询中, abcazbd 包含五种字母: a, b, c, d,和 z,所以我们打印 5.