题面

You are given a string s consisting of lowercase Latin letters and q queries for this string.

Recall that the substring s[l;r] of the string s is the string slsl+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 c (1≤pos≤|s|, c is lowercase Latin letter): replace spos with c (set spos:=c); 2 l r (1≤l≤r≤|s|): calculate the number of distinct characters in the substring s[l;r]. Input The first line of the input contains one string s consisting of no more than 105 lowercase Latin letters.

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

The next q 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.

题意

两种操作：1，在一个字符串中查询一个范围内不同的字符个数 2，将第pos位置的字符换成c 用压位来存不同的字符，建立一个可以维护区间不同字符个数和种类的线段树 类似线段树经典涂色问题。也可以用bitset但我不会。

代码(C++)

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; struct node{ int l,r,lazy,v; }tree[4000005]; int cnt=0; char a[500005]; long long get(int x) { long long tmp=1; for(int i=1;i<=x;i++) tmp*=2; return tmp; } void pushdown(int k) { if(tree[k].lazy>0) { tree[2*k].lazy=tree[k].lazy; tree[2*k+1].lazy=tree[k].lazy; tree[2*k].v=tree[k].lazy; tree[2*k+1].v=tree[k].lazy; tree[k].lazy=0; } } void pushup(int k) { tree[k].v=tree[2*k].v|tree[2*k+1].v; } void build(int now,int l,int r) { tree[now].l=l; tree[now].r=r; if(l==r) { tree[now].v=get(a[l]-'a'); return; } int mid=(l+r)/2; build(2*now,l,mid); build(2*now+1,mid+1,r); pushup(now); } void update(int k,int l,int r,int pos,char c) { if(l==r) { pushdown(k); long long tmp=get(c-'a'); tree[k].v=tmp; tree[k].lazy=tmp; return; } pushdown(k); int mid=(l+r)/2; if(mid>=pos) update(2*k,l,mid,pos,c); else update(2*k+1,mid+1,r,pos,c); pushup(k); } long long query(int l,int r,int left,int right,int now) { if(l<=left&&r>=right) return tree[now].v; pushdown(now); int mid=(left+right)/2; long long temp=0; if(l<=mid) { temp=temp|query(l,r,left,mid,2*now); } if(mid<r) { temp=temp|query(l,r,mid+1,right,2*now+1); } return temp; } void getAns(long long n) { int res=0; while(n!=0) { if(n%2==1) res++; n=n/2; } printf("%d\n",res); } int main() { cin>>a+1; int q; int n=strlen(a+1); build(1,1,n); cin>>q; while(q--) { int op; cin>>op; if(op==1) { int pos; char c; cin>>pos>>c; update(1,1,n,pos,c); } if(op==2) { int l,r; cin>>l>>r; getAns(query(l,r,1,n,1)); } } //system("pause"); return 0; }