UPC-Simple String Queries(二维树状数组)

你的偶像光芒万丈，你不能一身戾气。

Simple String Queries

You are given a string S of length N consisting of lowercase English letters.

Process Q queries of the following two types:

Type 1: change the iq-th character of S to cq. (Do nothing if the iq-th character is already cq.)

Type 2: answer the number of different characters occurring in the substring of S between the lq-th and rq-th characters (inclusive).

Constraints

·N, Q, iq, lq, and rq are integers.

·S is a string consisting of lowercase English letters.

·cq is a lowercase English letter.

·1≤N≤500000

·1≤Q≤20000

·|S|=N

·1≤iq≤N

·1≤lq≤rq≤N

·There is at least one query of type 2 in each testcase.

输入

Input is given from Standard Input in the following format:

N

S

Q

Query1

⋮

QueryQ

Here,Queryi in the 4-th through (Q+3)-th lines is one of the following:

1 iq cq

2 lq rq

输出

For each query of type 2, print a line containing the answer.

样例输入 Copy

7

abcdbbd

6

2 3 6

1 5 z

2 1 1

1 4 a

1 7 d

2 1 7

样例输出 Copy

3

1

5

提示

In the first query, cdbb contains three kinds of letters: b , c , and d, so we print 3.

In the second query, S is modified to abcdzbd.

In the third query, a contains one kind of letter: a, so we print 1.

In the fourth query, S is modified to abcazbd.

In the fifth query, S does not change and is still abcazbd.

In the sixth query, abcazbd contains five kinds of letters: a, b, c, d, and z, so we print 5.

题意： 给你一个字符串和若干次操作，操作1是更改字符串里的一个字母，操作2是查询该区间里不同字母的数量。要求输出操作2的查询结果。

思路： 裸的树状数组的单点修改和区间查询，我们用一个二维数组记录每个字母在此之前出现的次数，然后按照树状数组的思路写就可以了。

本题要注意：数组要开到5e5+10左右。每次更改时要把之前的字母删去。每次更改时要修改字符串里的字母。

代码：

#include<iostream>
using namespace std;
int n,m;
int tr[26][500010];
int lowbit(int x){
    return x&-x;
}
void add(int i,int x,int y){
    for(int j=i;j<=n;j+=lowbit(j))
        tr[x][j]+=y;
}
int ask(int x,int y){
    int res=0;
        for(int j=x;j;j-=lowbit(j))
            res+=tr[y][j];
    return res;
}
char s[500010];
int main(){
    cin>>n;
    cin>>s+1;
    for(int i=1;i<=n;i++){
        int x=s[i]-'a';
        add(i,x,1);
    }
    cin>>m;
    while(m--){
        int a,b,c;char ch;
        cin>>a;
        if(a==1){
            cin>>b>>ch;
            c=ch-'a';
            add(b,s[b]-'a',-1);
            add(b,c,1);
            s[b]=ch;
        }
        else{
            int res=0;
            cin>>b>>c;
            for(int i=0;i<26;i++){
                int sum=ask(c,i)-ask(b-1,i);
                if(sum>0) res++;
            }
            cout<<res<<endl;
        }
    }
    return 0;
}