こちらは割と簡単。
https://atcoder.jp/contests/abc157/tasks/abc157_e
問題
文字列に対し、以下のクエリが与えられる。
- 1文字変更する。
- 区間を示すクエリが与えられる。区間内にある文字種を答える。
解法
BITを26個(アルファベットの個数)作り、a~zが区間内に何個あるか求め、1個以上となる文字種を答えればよい。
int N; string S; int Q; template<class V, int ME> class BIT { public: V bit[1<<ME]; V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;} void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;} }; BIT<int,20> bt[26]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>S; FOR(i,N) bt[S[i]-'a'].add(i,1); cin>>Q; while(Q--) { cin>>i; if(i==1) { cin>>x>>s; x--; bt[S[x]-'a'].add(x,-1); S[x]=s[0]; bt[S[x]-'a'].add(x,1); } else { int L,R; cin>>L>>R; L--,R--; int cnt=0; FOR(i,26) { if(bt[i](R)-bt[i](L-1)) cnt++; } cout<<cnt<<endl; } } }
まとめ
こちらは迷わず書けた。