ABC157 E - Simple String Queries (500)
それぞれの文字までの各アルファベットの数を累積和で持つと更新が重いので駄目
Binary Indexed Treeを26個使ってそれぞれのアルファベットの出現位置を管理する
最初の文字列での出現位置を事前に追加する
文字の更新は、元々あった文字を1減らして新しい文字の方を1増やす
種類を求めるクエリは、それぞれのアルファベットで範囲内にその要素が1個以上あるかどうかの和を答える
事前構築が$ O(N \log N)でクエリに答えるのが$ O(Q \log N)、合わせて$ O((N+Q) \log N)