AtCoder ABC #157 : E - Simple String Queries

こちらは割と簡単。
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;
		}
	}
	
}

まとめ

こちらは迷わず書けた。