本文共 2675 字，大约阅读时间需要 8 分钟。

You are given a string ss consisting of lowercase Latin letters and qq queries for this string.

Recall that the substring s[l;r]s[l;r] of the string ss is the string slsl+1…srslsl+1…sr. For example, the substrings of “codeforces” are “code”, “force”, “f”, “for”, but not “coder” and “top”.

There are two types of queries:

1 pos c1 pos c (1≤pos≤|s|1≤pos≤|s|, cc is lowercase Latin letter): replace sposspos with cc (set spos:=cspos:=c);

2 l r2 l r (1≤l≤r≤|s|1≤l≤r≤|s|): calculate the number of distinct characters in the substring s[l;r]s[l;r]. Input The first line of the input contains one string ss consisting of no more than 105105 lowercase Latin letters.

The second line of the input contains one integer qq (1≤q≤1051≤q≤105) — the number of queries.

The next qq lines contain queries, one per line. Each query is given in the format described in the problem statement. It is guaranteed that there is at least one query of the second type.

Output

For each query of the second type print the answer for it — the number of distinct characters in the required substring in this query.

Examples

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 题意：给你一串字符串，问区间[l,r]有多少个不同的字符。 思路：跟之前的染色之后问有多少种颜色类似。因为小写字母就26个，所以每一种字母就代表那个位置为1.利用或运算。 代码如下：

#include
   
    #define ll long longusing namespace std;const int maxx=1e5+100;struct node{
   	int l;	int r;	ll sum;}p[maxx<<2];char s[maxx];int n,m;inline void pushup(int cur){
   	p[cur].sum=p[cur<<1].sum|p[cur<<1|1].sum;}inline void build(int l,int r,int cur){
   	p[cur].l=l;	p[cur].r=r;	p[cur].sum=0;	if(l==r)	{
   		p[cur].sum=1ll<<(s[l]-'a'+1);		return ;	}	int mid=l+r>>1;	build(l,mid,cur<<1);	build(mid+1,r,cur<<1|1);	pushup(cur);}inline void update(int pos,int v,int cur){
   	int L=p[cur].l;	int R=p[cur].r;	if(L==R)	{
   		p[cur].sum=(1ll<
    
     >1;	if(pos<=mid) update(pos,v,cur<<1);	else update(pos,v,cur<<1|1);	pushup(cur);}inline ll query(int l,int r,int cur){
   	int L=p[cur].l;	int R=p[cur].r;	if(l<=L&&R<=r) return p[cur].sum;	int mid=L+R>>1;	if(r<=mid) return query(l,r,cur<<1);	else if(l>mid) return query(l,r,cur<<1|1);	else return (query(l,mid,cur<<1)|query(mid+1,r,cur<<1|1));}int main(){
   	int op,l,r;char c[2];	scanf("%s",s+1);	n=strlen(s+1);	build(1,n,1);	scanf("%d",&m);	while(m--)	{
   		scanf("%d",&op);		if(op==1) 		{
   			scanf("%d%s",&l,c);			update(l,c[0]-'a'+1,1);		}		else if(op==2)		{
   			scanf("%d%d",&l,&r);			ll sum=query(l,r,1);			int ans=0;			while(sum)			{
   				ans+=(sum&1);				sum>>=1;			}			cout<
     
      <
     
    
   

努力加油a啊，(^o)/~

转载地址：http://qytvi.baihongyu.com/