問題はこちら。

セグメント木のノードに持たせる情報の表現方法によっていろいろな実装が考えられるが Python + numpy → TLE, PyPy + defaultdict → TLE, PyPy + numpy → RE となったので普通にリストで管理したらPyPyで通った。numpy速いとかPyPyの辞書遅いとか何となく知ってるんだけどこのへんの見極めが一目でできるようになりたい。

import sys
readline = sys.stdin.readline


class SegmentTree():
   def __init__(self, size, string):
       self.half = 1 << (size - 1).bit_length()
       self.tree = [[0]*26 for _ in range(2*self.half)]
       for i, c in enumerate(string):
           j = ord(c) - ord('a')
           self.tree[i + self.half][j] += 1
       for i in reversed(range(self.half)):
           l, r = 2*i, 2*i + 1
           for j in range(26):
               self.tree[i][j] = self.tree[l][j] + self.tree[r][j]

   def update(self, i, c):
       i += self.half
       j = ord(c) - ord('a')
       self.tree[i] = [0]*26
       self.tree[i][j] += 1
       while i > 1:
           i //= 2
           l, r = 2*i, 2*i + 1
           for j in range(26):
               self.tree[i][j] = self.tree[l][j] + self.tree[r][j]

   def query(self, l, r):
       l += self.half
       r += self.half
       ret = [0]*26
       while l < r:
           if l & 1:
               for j in range(26):
                   ret[j] += self.tree[l][j]
               l += 1
           if r & 1:
               r -= 1
               for j in range(26):
                   ret[j] += self.tree[r][j]
           l //= 2; r //= 2
       return ret


def main():
   N = int(readline())
   S = readline().strip()
   Q = int(readline())

   SEG = SegmentTree(N, S)
   for _ in range(Q):
       t, x, y = readline().split()
       t = int(t)
       x = int(x)
       if t == 1:
           x -= 1
           SEG.update(x, y)
       else:
           y = int(y)
           x -= 1
           cnt = SEG.query(x, y)
           ans = 0
           for i in range(26):
               if cnt[i] > 0:
                   ans += 1
           print(ans)


if __name__ == "__main__":
   main()