Problem:


Score : 500 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters.

Process Q queries of the following two types:

Type 1: change the i_q-th character of S to c_q. (Do nothing if the i_q-th character is already c_q.)

Type 2: answer the number of different characters occurring in the substring of S between the l_q-th and r_q-th characters (inclusive).

Constraints

N, Q, i_q, l_q, and r_q are integers.

S is a string consisting of lowercase English letters.

c_q is a lowercase English letter.

1 \leq N \leq 500000

1 \leq Q \leq 20000

|S| = N

1 \leq i_q \leq N

1 \leq l_q \leq r_q \leq N

There is at least one query of type 2 in each testcase.

Input

Input is given from Standard Input in the following format:

N
S
Q
Query_1
\vdots
Query_Q

Here, Query_i in the 4-th through (Q+3)-th lines is one of the following:

1 i_q c_q

2 l_q r_q

Output

For each query of type 2, print a line containing the answer.

Sample Input 1

7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7

Sample Output 1

3
1
5

In the first query, cdbb contains three kinds of letters: b , c , and d, so we print 3.

In the second query, S is modified to abcdzbd.

In the third query, a contains one kind of letter: a, so we print 1.

In the fourth query, S is modified to abcazbd.

In the fifth query, S does not change and is still abcazbd.

In the sixth query, abcazbd contains five kinds of letters: a, b, c, d, and z, so we print 5.



Sample input:
7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7


Sample output:
3
1
5

Submission status: Runtime Error

Solution code:
class SegmentTree():
    def __init__(self, size):
        self.size = 2**(size-1).bit_length()
        self.val = [0]*(self.size*2)
    
    def update(self, i, x):
        i += self.size
        self.val[i] = x
        
        while i > 0:
            i = i >> 1
            self.val[i] = self.val[2*i] + self.val[2*i+1]
    
    def query(self, l, r):
        l += self.size
        r += self.size

        l_sum = 0
        r_sum = 0

        while l < r:
            if l & 1:
                l_sum += self.val[l]
                l += 1
            l = l >> 1

            if r & 1:
                r -= 1
                r_sum += self.val[r]
            r = r >> 1

        return l_sum + r_sum

def convertAlphabetToNumber(s):
    return ord(s) - ord('a')

N = int(input())
S = input()
Q = int(input())
query = [input().split() for i in range(Q)]

for i in range(Q):
    query[i][0] = int(query[i][0])
    query[i][1] = int(query[i][1])
    if query[i][0] == 2:
        query[i][2] = int(query[i][2])

alphabet_position = [SegmentTree(N) for i in range(28)]

for i in range(N):
    num = convertAlphabetToNumber(S[i])
    alphabet_position[num].update(i + 1, 1)

for i in range(Q):
    if query[i][0] == 1:
        for j in range(28):
            if j == convertAlphabetToNumber(query[i][2]):
                alphabet_position[j].update(query[i][1], 1)
            else:
                alphabet_position[j].update(query[i][1], 0)
    else:
        cnt = 0
        for j in range(28):
            if alphabet_position[j].query(query[i][1], query[i][2] + 1) > 0:
                cnt += 1
        print(cnt)

Submission status: Runtime Error

Solution code:
import sys
from operator import or_

input = sys.stdin.readline


class SegmentTree:
    def __init__(self, N, X):
        self.N = N
        self.func = or_
        self.__build(X)

    def __build(self, X):
        # Initialize all nodes
        self.node = [set() for _ in range(2 * self.N)]

        # Elementary intervals are stored
        for i, s in enumerate(X, self.N):
            self.node[i].add(s)

        # The internal nodes correspond to intervals that are the union of elementary intervals
        for i in range(self.N - 1, 0, -1):
            self.node[i] = self.func(self.node[i << 1], self.node[i << 1 | 1])

    def update(self, i, s):
        i += self.N - 1
        if s in self.node[i]:
            return
        self.node[i] = set([s])
        while i > 1:
            i >>= 1
            self.node[i] = self.func(self.node[i << 1], self.node[i << 1 | 1])

    def query(self, l, r):
        """Query for right half-open interval [l, r).

        Args:
            l (int): index (1-based index)
            r (int): index (1-based index)
        """
        dst_l = set()
        dst_r = set()
        l += self.N - 1
        r += self.N - 1
        while l < r:
            if l & 1:
                dst_l = self.func(dst_l, self.node[l])
                l += 1
            if r & 1:
                r -= 1
                dst_r = self.func(self.node[r], dst_r)
            l >>= 1
            r >>= 1
        return self.func(dst_l, dst_r)


def main():
    N = int(input())
    S = input().rstrip()

    S = list(S)
    st = SegmentTree(N, S)

    ans = []
    Q = int(input())
    for _ in range(Q):
        query = input().split()
        q = int(query[0])
        if q == 1:
            i = int(query[1])
            c = query[2]
            st.update(i, c)
        else:
            l = int(query[1])
            r = int(query[2])
            res = st.query(l, r + 1)
            ans.append(len(res))

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()
!

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
Q = int(input())
for _ in range(Q):
    q = input().split()
    if q[0] == '1':
        S = S[:int(q[1])-1]+q[2]+S[int(q[1]):]
        print(S)
    else:
        T = S[int(q[1])-1:int(q[2])]
        Chrs = set(list(T))
        print(len(Chrs))

Submission status: Runtime Error

Solution code:
class BIT():
  def __init__(self, n):
    self.s = [0] * (n+1)
    self.n = n

  def add(self, idx, val):
    while idx < self.n+1:
      self.s[idx] += val
      idx += idx&(-idx)

  def get(self, idx):
    res = 0
    while idx > 0:
      res += self.s[idx]
      idx -= idx&(-idx)

n = int(input())
S = [ ord(s)-ord('a') for s in input()[::-1] ]
bits = [BIT(n) for i in range(26)]

for i,s in enumerate(S):
  bits[s].add(i+1,1)

Q = int(input())
ans = []
for _ in range(Q):
  flg,x,y = map(str, input().split())
  if flg == "1":
    i = int(x)
    c = ord(y) - ord('a')
    bits[S[i-1]].add(i, -1)
    bits[c].add(i, 1)
    S[i-1] = c
  else:
    l = int(x)
    r = int(y)
    res = 0
    for i in range(26):
      res += bits[i].get(r) > bits[i].get(l-1)
    ans.append(res)

for a in ans: print(a)

Submission status: Runtime Error

Solution code:
N = int(input())
S = list(input())
Q = int(input())

D = {chr(ord('a') + i): [] for i in range(26)}
for i, s in enumerate(S):
    D[s].append(i)

for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1]), query[2]
        i -= 1
        s = S[i]
        if s == x:
            continue

        D[s].remove(i)
        next_i = bisect_left(D[x], i)
        D[x].insert(next_i, i)
        S[i] = x

    if query[0] == '2':
        l, r = int(query[1]), int(query[2])
        l, r = l - 1, r - 1
        ans = 0
        for i in range(26):
            s = chr(ord('a') + i)

            li = bisect_left(D[s], l)
            ri = bisect_right(D[s], r)

            if ri - li > 0:
                ans += 1

        print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left,bisect
n = int(input())
s = list(input())
q = int(input())
al=[[] for i in range(26)]
for i in range(n):
    al[ord(s[i])-ord("a")].append(i)

for i in range(q):
    a , b , x = input().split()
    if a == "1":
        al[ord(s[int(b)-1])-ord("a")].pop(al[ord(s[int(b)-1])-ord("a")],int(b)-1)
        al[ord(x)-ord("a")].insert(bisect_left(al[ord(x)-ord("a")],int(b)-1),int(b)-1)
        s[int(b)-1] = x
    elif a == "2":
        b = int(b)-1
        x = int(x)-1
        cou = 0
        for j in range(26):
            l = bisect_left(al[j],b)
            r = bisect(al[j],x)
            if l != r:
                cou += 1
        print(cou)

Submission status: Runtime Error

Solution code:
import heapq
from bisect import bisect_left,bisect
n = int(input())
s = list(input())
q = int(input())
al=[[] for i in range(26)]
for i in range(26):
    heapq.heapify(al[i])

for i in range(n):
    heapq.heappush(al[ord(s[i])-ord("a")],i)

for i in range(q):
    a , b , x = input().split()
    if a == "1":
        al[ord(s[int(b)-1])-ord("a")].remove(int(b)-1)
        heapq.heappush(al[ord(x)-ord("a")],int(b)-1)
    elif a == "2":
        b = int(b)-1
        x = int(x)-1
        cou = 0
        for j in range(26):
            l = bisect_left(al[j],b)
            r = bisect(al[j],x)
            if l != r:
                cou += 1
        print(cou)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
class BIT:
  def __init__(self, logn):
    self.n = 1<<logn
    self.data = [0]*(self.n+1)
    self.el = [0]*(self.n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
  def bisect(self, x):
    w = i = 0
    k = self.n
    while k:
      if i+k <= self.n and w + self.data[i+k] <= x:
        w += self.data[i+k]
        i += k
      k >>= 1
    return i+1

N = I()
A = list(S())
Q = I()

dic = {l:BIT(int_log(N,2)+1) for l in AZ}

for i in range(N):
  s = A[i]
  dic[s].add(i+1,1)

def change(i,y):
  prev = A[i]
  if prev == y:
    pass
  else:
    A[i] = y
    dic[prev].add(i,-1)
    dic[y].add(i,1)
  
def count(x,y):
  ret = 0
  for l in AZ:
    if dic[l].sum(x-1) != dic[l].sum(y):
      ret += 1
  print(ret)

for _ in range(Q):
  t,x,y = SL()
  if t == "1":
    change(int(x),y)
  else:
    count(int(x),int(y))

Submission status: Runtime Error

Solution code:
N = int(input())
s = input()
S = []
for k in range(N):
  S.append(s[k])
Q = int(input())
a = ord('a')
alpha = [[] for _ in range(ord('z') - a + 1)]
for k in range(N):
  alpha[ord(S[k])- a].append(k)



for k in range(Q):
  q = input()
  if q[0] == '1':
    if S[int(q[2])-1] != q[4]:
      del alpha[ord(S[int(q[2])-1])-a][alpha[ord(S[int(q[2])-1])-a].index(int(q[2])-1)]
      for j in range(len(alpha[ord(q[4])-a])):
        if alpha[ord(q[4])-a][j] > int(q[2])-1:
          alpha[ord(q[4])-a] = alpha[ord(q[4])-a][0:j] + [int(q[2])-1] + alpha[ord(q[4])-a][j:]
          break
      else:
        alpha[ord(q[4])-a].append(int(q[2])-1)
      if len(alpha[ord(q[4])-a]) == 0:
        alpha[ord(q[4])-a].append(int(q[2])-1)
      S[int(q[2])-1] = q[4]
  if q[0] == '2':
    l = int(q[2])-1
    r = int(q[4])-1
    ans = 0
    for j in range(len(alpha)):
      if len(alpha[j]) == 1:
        if l <= alpha[j][0] <= r:
          ans += 1
      elif len(alpha[j]) > 1:
        if r < alpha[j][0] or alpha[j][-1] < l:
          break
        else:
          ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll big=1e18;
const double PI=2*asin(1);

int segtree[(1<<24)][26];

void init(int i, char aft) {
  i += (1<<23) - 1;
  while(i!=0) {
    segtree[i][aft-'a']++;
    i = (i-1)/2;
  }
}

void change(int i, char aft, char bef) {
  i += (1<<23)-1;
  while(i!=0) {
    segtree[i][bef-'a']--;
    segtree[i][aft-'a']++;
    i = (i-1)/2;
  }
}

int solve(int l, int r) {
  l += (1<<23)-1;
  r += (1<<23)-1;
  map<int, int> amap;
  while(l<r) {
    if(l%2==0) {
      for(int i=0;i<26;++i) amap[i] += segtree[l][i];
      l++;
    }
    l /= 2;
    if(r%2==0) {
      for(int i=0;i<26;++i) amap[i] += segtree[r-1][i];
      r--;
    }
    r /= 2;
  }
  int ans = 0;
  for(int i=0;i<26;++i) {
    if(amap[i]>0) ans++;
  }
  return ans;
}

int main() {
  int N;
  cin>>N;
  string S;
  cin>>S;
  for(int i=0;i<N;++i) {
    init(i, S[i]);
  }
  int Q;
  cin>>Q;
  int query;
  int l, r;
  int index;
  char aft, bef;
  vector<int> answer;
  for(int i=0;i<Q;++i) {
    cin>>query;
    if(query==1) {
      cin>>index>>aft;
      index--;
      bef = S[index];
      change(index, aft, bef);
      S[index] = aft;
    }
    else {
      cin>>l>>r;
      l--;
      answer.push_back(solve(l, r));
    }
  }
  for(int i=0;i<answer.size();++i) cout<<answer[i]<<endl;
}

Submission status: Runtime Error

Solution code:
# return the maximal range b, e such that l <= ary[b:e] <= r
def max_range(ary, l, r):
    glb = greatest_lower_bound(ary, l-1) + 1
    lub = least_upper_bound(ary, r+1)
    return glb, lub


# return greatest i such that ary[i] <= q or -1
# if not exists
def greatest_lower_bound(ary, q):
    b, e = -1, len(ary) - 1
    while b < e:
        m = e - (e - b) // 2
        if ary[m] > q:
            e = m - 1
        else:
            b = m
    return b

# return smallest i such that ary[i] >= q or len(ary)
# if not exists
def least_upper_bound(ary, q):
    b, e = 0, len(ary)
    while b < e:
        m = b + (e - b) // 2
        if ary[m] < q:
            b = m + 1
        else:
            e = m
    return e


def is_sorted(ary):
    return all(ary[i] <= ary[i+1] for i in range(len(ary) - 1))

def main():
    n = int(input())
    s = input()
    q = int(input())

    ai = ord('a')
    # locs[i] = set(p1, p2, ...)
    # the i'th letter of the alphabet occurs at s[p1], s[p2], ...
    locs = [[] for _ in range(26)]

    for i, c in enumerate(s):
        ci = ord(c) - ai
        locs[ci].append(i)

    for ci in range(26):
        locs[ci].sort()

    for _ in range(q):
        t, v1, v2 = input().split()
        if t == '1':
            i = int(v1) - 1
            c_old = ord(s[i]) - ai
            c_new = ord(v2) - ai
            old_ind = greatest_lower_bound(locs[c_old], i)
            new_ind = greatest_lower_bound(locs[c_new], i)
            old_val = locs[c_old].pop(old_ind)
            assert old_val == i
            locs[c_new].insert(new_ind + 1, i)
            assert is_sorted(locs[c_new])

        elif t == '2':
            l, r = int(v1), int(v2)
            # count number of different characters of each letter in s[l:r+1]
            num_dif_chars = 0
            for ci in range(26):
                lb, ub = max_range(locs[ci], l, r)
                # print('ranges', locs[ci], locs[ci][lb:ub], l, r)
                if lb < ub:
                    num_dif_chars += 1

            print(num_dif_chars)


main()

Submission status: Runtime Error

Solution code:
#A1 ~ Aiまでの和 O(logN)
def BIT_query(BIT,idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(BIT,idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return


alps = 'abcdefghijklmnopqrstuvwxyz'

n = int(input())
s = input()
char_hd_d = {}
for alp in alps:
    char_hd_d[alp] = [0]*(n+1)

for i, si in enumerate(s):
    BIT_update(char_hd_d[si], i+1, 1)

q = int(input())
ansl = []
for _ in range(q):
    command, a, b = input().split()
    if command == '1':
        i = int(a)
        c = b
        i_char = s[i-1]
        BIT_update(char_hd_d[i_char], i, -1)
        BIT_update(char_hd_d[c], i, 1)
        s[i-1] = c 
    else:
        l,r = int(a),int(b)
        cnt = 0
        for alp in alps:
            if BIT_query(char_hd_d[alp], r) - BIT_query(char_hd_d[alp], l-1) > 0:
                cnt += 1
        ansl.append(cnt)

for a in ansl:
    print(a)

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
import bisect

alp = [set() for _ in range(26)]

for i in range(n):
    x = ord(s[i]) - 97
    alp[x].add(i)
    
q = int(input())
for i in range(q):
    a,b,c = input().split()
    
    if a == "1":
        bb = int(b)
        x = ord(s[bb-1]) - 97
        alp[x].remove(bb-1)
        
        y = ord(c) - 97
        alp[y].add(bb-1)
        
    else:
        ans = 0
        l,r = int(b)-1,int(c)-1
        for j in range(26):
            if alp[j] != set():
                b = list(alp[j])
                b.sort()
                
                c = bisect.bisect(b,l-1)
                if c == len(b):
                    continue
                else:
                    if b[c] <= r:
                        ans += 1
                        
        print(ans)

Submission status: Runtime Error

Solution code:
# Segment tree (Bitwise Or)
from operator import or_


class SegmentTree:
    _f = None
    _data = None
    _offset = None
    _size = None

    def __init__(self, size, f):
        self._f = f
        self._size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

    def build(self, iterable):
        f = self._f
        data = self._data
        data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            data[i] = f(data[i * 2 + 1], data[i * 2 + 2])

    def update(self, index, value):
        f = self._f
        data = self._data
        i = self._offset + index
        data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            data[i] = f(data[i * 2 + 1], data[i * 2 + 2])

    def query(self, start, stop):
        def iter_segments(data, l, r):
            while l < r:
                if l & 1 == 0:
                    yield data[l]
                if r & 1 == 0:
                    yield data[r - 1]
                l = l // 2
                r = (r - 1) // 2
        f = self._f
        it = iter_segments(self._data, start + self._offset,
                           stop + self._offset)
        result = next(it)
        for e in it:
            result = f(result, e)
        return result


N = int(input())
S = input()

st = SegmentTree(N, or_)
st.build(S)

Q = int(input())
for _ in range(Q):
    q = input().split()
    if q[0] == '1':
        i, c = q[1:]
        i = int(i) - 1
        st.update(i, c)
    elif q[0] == '2':
        l, r = map(int, q[1:])
        print(bin(st.query(l - 1, r)).count('1'))

Submission status: Runtime Error

Solution code:
N = int(input())
S = ["*"]*(N+1)
S[1:] = list(input())
Q = int(input())
q1,q2,q3 = [0]*Q,[0]*Q,[0]*Q
for i in range(Q):
    tmp = input().split()
    q1[i],q2[i] = map(int,tmp[:2])
    if q1[i] == 2:
        q3[i] = int(tmp[2])
    else:
        q3[i] = tmp[2]

class BIT:
    def __init__(self, n, init_list):
        self.num = n + 1
        self.tree = [0] * self.num
        for i, e in enumerate(init_list):
            self.update(i, e)

    #a_kにxを加算
    def update(self, k, x):
        k = k + 1
        while k < self.num:
            self.tree[k] += x
            k += (k & (-k))
        return

    def query1(self, r):
        ret = 0
        while r > 0:
            ret += self.tree[r]
            r -= r & (-r)
        return ret

    #通常のスライスと同じ。lは含み、rは含まない
    def query2(self, l, r):
        return self.query1(r) - self.query1(l)

s_pos = [BIT(N+1,[0]*(N+1)) for _ in range(26)]

for i in range(1,N+1):
    s_pos[ord(S[i]) - ord("a")].update(i,1)

alphabets = [chr(ord("a") + i) for i in range(26)]

for i in range(Q):
    if q1[i] == 1:
        s_pos[ord(S[q2[i]]) - ord("a")].update(q2[i],-1)
        S[i] = q3[i]
        s_pos[ord(q3[i]) - ord("a")].update(q2[i],1)
    else:
        ans = 0
        for c in alphabets:
            if s_pos[ord(c) - ord("a")].query2(q2[i],q3[i]+1) > 0:
                ans += 1
        print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def solve():
    N = int(input())
    S = list(input())
    Q = int(input())
    set_dic = {}

    for i, s in enumerate(S):
        if s not in set_dic.keys():
            set_dic[s] = {i+1}
        else:
            set_dic[s].add(i+1)

    anslist = []

    for _ in range(Q):
        query1, query2, query3 = input().split()
        if query1 == "1":
            i = int(query2)
            c = query3
            set_dic[c].discard(i)
            if c not in set_dic.keys():
                set_dic[c] = {i}
            else:
                set_dic[c].add(i)
        else:
            l = int(query2)
            r = int(query3)
            ansset = set()
            ans = 0
            for eachset in set_dic.values():
                for i in range(l, r + 1):
                    if i in eachset:
                        ans += 1
                        break
            anslist.append(ans)

    for i in anslist:
        print(i)

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
def solve():
    N = int(input())
    S = list(input())
    Q = int(input())
    set_dic = {}

    for i, s in enumerate(S):
        if s not in set_dic.keys():
            set_dic[s] = {i+1}
        else:
            set_dic[s].add(i+1)

    anslist = []

    for _ in range(Q):
        query1, query2, query3 = input().split()
        if query1 == "1":
            i = int(query2)
            c = query3
            set_dic[c].discard(i)
            if c not in set_dic.keys():
                set_dic[c] = {i}
            else:
                set_dic[c].add(i)
        else:
            l = int(query2)
            r = int(query3)
            ansset = set()
            ans = 0
            for eachset in set_dic.values():
                for i in range(l, r + 1):
                    if i in eachset:
                        ans += 1
                        break
            anslist.append(ans)

    for i in anslist:
        print(i)

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
N = int(input())
S = list(input())
Q = int(input())
set_dic = {}

for i, s in enumerate(S):
    if s not in set_dic.keys():
        set_dic[s] = {i+1}
    else:
        set_dic[s].add(i+1)

anslist = []
count = 0

for _ in range(Q):
    query1,query2,query3 = input().split()
    if query1 == "1":
        i = int(query2)
        c = query3
        for l in set_dic.values():
            l.discard(i)
        if c not in set_dic.keys():
            set_dic[c] = {i}
        else:
            set_dic[c].add(i)
    else:
        l = int(query2)
        r = int(query4)
        ansset = set()
        for i in range(l, r + 1):
            for key, eachset in set_dic.items():
                if i in eachset:
                    ansset.add(key)
                    break
        ans = len(ansset)
        anslist.append(ans)
        count += 1

for i in anslist:
    print(i)

Submission status: Runtime Error

Solution code:
N = int(input())
S = list(input())
Q = int(input())
set_dic = {}

for i, s in enumerate(S):
    if s not in set_dic.keys():
        set_dic[s] = {i+1}
    else:
        set_dic[s].add(i+1)

anslist = []
count = 0

for _ in range(Q):
    query = list(input())
    if query[0] == "1":
        i = int(query[2])
        c = query[4]
        for l in set_dic.values():
            l.discard(i)
        if c not in set_dic.keys():
            set_dic[c] = {i}
        else:
            set_dic[c].add(i)
    else:
        l = int(query[2])
        r = int(query[4])
        ansset = set()
        for i in range(l, r + 1):
            for key, eachset in set_dic.items():
                if i in eachset:
                    ansset.add(key)
                    break
        ans = len(ansset)
        anslist.append(ans)
        count += 1

for i in anslist:
    print(i)

Submission status: Runtime Error

Solution code:
N = int(input())
S = list(input())
Q = int(input())
set_dic = {}

for i, s in enumerate(S):
    if s not in set_dic.keys():
        set_dic[s] = {i+1}
    else:
        set_dic[s].add(i+1)

anslist = []
count = 0

for _ in range(Q):
    query = input()
    if query[0] == "1":
        i = int(query[2])
        c = query[4]
        for l in set_dic.values():
            l.discard(i)
        if c not in set_dic.keys():
            set_dic[c] = {i}
        else:
            set_dic[c].add(i)
    else:
        l = int(query[2])
        r = int(query[4])
        ansset = set()
        for i in range(l, r + 1):
            for key, eachset in set_dic.items():
                if i in eachset:
                    ansset.add(key)
                    break
        ans = len(ansset)
        anslist.append(ans)
        count += 1

for i in anslist:
    print(i)

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
Q = int(input())
set_dic = {}

for i, s in enumerate(S):
    if s not in set_dic.keys():
        set_dic[s] = {i+1}
    else:
        set_dic[s].add(i+1)

anslist = []
count = 0

for _ in range(Q):
    query = input()
    if query[0] == "1":
        """
        i = int(query[2])
        c = query[4]
        for l in set_dic.values():
            l.discard(i)
        if c not in set_dic.keys():
            set_dic[c] = {i}
        else:
            set_dic[c].add(i)
            """
    else:"""
        l = int(query[2])
        r = int(query[4])
        ansset = set()
        for i in range(l, r + 1):
            for key, eachset in set_dic.items():
                if i in eachset:
                    ansset.add(key)
                    break
        ans = len(ansset)
        anslist.append(ans)"""
        count += 1

"""for i in anslist:
    print(i)"""
for _ in range(count):
    print(8)

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
Q = int(input())
set_dic = {}

for i, s in enumerate(S):
    if s not in set_dic.keys():
        set_dic[s] = {i+1}
    else:
        set_dic[s].add(i+1)

anslist = []

for _ in range(Q):
    query = input()
    if query[0] == "1":
        """
        i = int(query[2])
        c = query[4]
        for l in set_dic.values():
            l.discard(i)
        if c not in set_dic.keys():
            set_dic[c] = {i}
        else:
            set_dic[c].add(i)
            """
    else:
        l = int(query[2])
        r = int(query[4])
        ansset = set()
        for i in range(l, r + 1):
            for key, eachset in set_dic.items():
                if i in eachset:
                    ansset.add(key)
                    break
        ans = len(ansset)
        anslist.append(ans)

for i in anslist:
    print(i)

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
Q = int(input())
set_dic = {}

for i, s in enumerate(S):
    if s not in set_dic.keys():
        set_dic[s] = {i+1}
    else:
        set_dic[s].add(i+1)

anslist = []

for _ in range(Q):
    query = input()
    if query[0] == "1":
        i = int(query[2])
        c = query[4]
        for l in set_dic.values():
            l.discard(i)
        if c not in set_dic.keys():
            set_dic[c] = {i}
        else:
            set_dic[c].add(i)
    else:
        l = int(query[2])
        r = int(query[4])
        ansset = set()
        for i in range(l, r + 1):
            for key, eachset in set_dic.items():
                if i in eachset:
                    ansset.add(key)
                    break
        ans = len(ansset)
        anslist.append(ans)

for i in anslist:
    print(i)

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
Q = int(input())
set_dic = {}
for i, s in enumerate(S):
    if s not in set_dic.keys():
        set_dic[s] = {i+1}
    else:
        set_dic[s].add(i+1)

anslist = []
for _ in range(Q):
    query = input()
    if query[0] == "1":
        i = int(query[2])
        c = query[4]
        for l in set_dic.values():
            l.discard(i)
        if c not in set_dic.keys():
            set_dic[c] = {i}
        else:
            set_dic[c].add(i)
    else:
        l = int(query[2])
        r = int(query[4])
        ans = 0
        for eachset in set_dic.values():
            for i in range(l, r+1):
                if i in eachset:
                    ans += 1
                    break
        anslist.append(ans)

for i in anslist:
    print(i)