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: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007
import operator
class SegmentTree:
    def __init__(self, size, default, op = operator.add):
        self.size = 2**size.bit_length()
        self.dat = [default]*(self.size*2)
        self.op = op

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

    def add(self, i, x):
        i += self.size
        self.dat[i] = self.op(self.dat[i], x)
        while i > 0:
            i >>= 1
            self.dat[i] = self.op(self.dat[i], x)

    def get(self, a, b = None):
        if b is None:
            b = a + 1
        l, r = a + self.size, b + self.size
        res = None
        while l < r:
            if l & 1:
                if res is None:
                    res = self.dat[l]
                else:
                    res = self.op(res, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                if res is None:
                    res = self.dat[r]
                else:
                    res = self.op(res, self.dat[r])
            l >>= 1
            r >>= 1
        return res
def solve():
    n = I()
    S = list(input())
    m = ord("z")-ord("a")+1
    s = [SegmentTree(n,0) for i in range(m)]
    for i in range(n):
        k = ord(S[i])-ord("a")
        s[k].update(i,1)
    Q = I()
    for _ in range(Q):
        q = input().split()
        if q[0] == "1":
            i = int(q[1])-1
            if S[i] == q[2]:
                continue
            k = ord(S[i])-ord("a")
            s[k].update(i,0)
            k = ord(q[2])-ord("a")
            s[k].update(i,1)
            S[i] = q[2]
        else:
            l,r = q[1:]
            l = int(l)
            r = int(r)
            ans = 0
            for k in range(m):
                if s[k].get(l-1,r):
                    ans += 1
            print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
# 足す時はi番目に足し、返すのは累積和
class sumBIT():
    def __init__(self, N):
        self.N = N
        self.bit = [0 for _ in range(self.N+1)]
    
    def __str__(self):
        ret = []
        for i in range(1, self.N+1):
            ret.append(self.__getitem__(i))
        return "[" + ", ".join([str(a) for a in ret]) + "]"

    def __getitem__(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.N:
            self.bit[i] += x
            i += i & -i

import sys
input = sys.stdin.readline

N = int(input())
S = list(input().rstrip())
Q = int(input())
Query = [list(map(str, input().split())) for _ in range(Q)]

Alp = [chr(i) for i in range(97, 97+26)]
BITs = {}
for i, a in enumerate(Alp):
    bit = sumBIT(N+3)
    BITs[a] = bit

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

for WWW, x, y in Query:
    if WWW == "1":
        i = int(x)
        for alp in Alp:
            if BITs[alp][i+1] - BITs[alp][i] > 0:
                BITs[alp].add(i+1, -1)
                break
        BITs[y].add(i+1, 1)
    else:
        l = int(x)
        r = int(y)
        ans = 0
        for alp in Alp:
            if BITs[alp][r+1] - BITs[alp][l] > 0:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
import sys
range = xrange
input = raw_input

class segtree:
    def __init__(self, n):
        m = 1
        while m < n:
            m *= 2
        self.m = m
        self.data = [0]*(m + m)
    def add(self, i, x):
        i += self.m
        while i:
            self.data[i] += x
            i >>= 1

    def summer(self, l ,r):
        l += self.m
        r += self.m
        while l < r:
            if l & 1:
                if self.data[l]:
                    return True
                l += 1
            if r & 1:
                r -= 1
                if self.data[r]:
                    return True
            l >>= 1
            r >>= 1
        return False

orda = ord('a')

inp = sys.stdin.read().split(); ii = 0

n = int(inp[ii]); ii += 1
S = [ord(c) - orda for c in inp[ii]]; ii += 1

segs = [segtree(n) for _ in range(26)]
for i in range(n):
    segs[S[i]].add(i, 1)

q = int(inp[ii]); ii += 1
out = []
for _ in range(q):
    case = int(inp[ii]); ii += 1

    if case == 1:
        i = int(inp[ii]) - 1; ii += 1
        c = ord(inp[ii]) - orda; ii += 1

        segs[S[i]].add(i, -1)
        S[i] = c
        segs[S[i]].add(i, 1)
    else:
        l = int(inp[ii]) - 1; ii += 1
        r = int(inp[ii]); ii += 1
        out.append(sum(seg.summer(l,r) for seg in segs))
print '\n'.join(str(x) for x in out)

Submission status: Accepted

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

class Binary_Indexed_Tree():
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

    def add(self, i, x):
        i += 1
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def get(self, i):
        i += 1
        return self.sum_range(i, i)

    def sum(self, i):
        i += 1
        ret = 0
        while i:
            ret += self.data[i]
            i &= i-1
        return ret

    def sum_range(self, l, r):
        return self.sum(r)-self.sum(l-1)

n = int(input())
s = input()
m = 26
orda = ord("a")
segs = [Binary_Indexed_Tree(n) for i in range(m)]
s = list(map(lambda x: ord(x)-orda, list(s)))
for i, c in enumerate(s):
    segs[c].add(i,1)

q = int(input())
for _ in range(q):
    f,i,c = input().split()
    f = int(f)
    if f == 1:
        i = int(i)-1
        c = ord(c)-orda
        if s[i] != c:
            segs[s[i]].add(i, -1)
            s[i] = c
            segs[s[i]].add(i, 1)
    else:
        l = int(i)-1
        r = int(c)-1
        ans = 0
        for x in range(m):
            if segs[x].sum_range(l,r) > 0:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
class SegmentTree():
    """一点更新、区間取得クエリをそれぞれO(logN)で答えるデータ構造を構築する
    update: i番目をvalに変更する
    get_min: 区間[begin, end)の最小値を求める
    """
    def __init__(self, n):
        self.n = n
        self.INF = 0
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [self.INF] * (2*self.size - 1)

    def update(self, i, val):
        i += (self.size - 1)
        self.node[i] = val
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = self.node[2*i + 1] | self.node[2*i + 2]

    def get_min(self, begin, end):
        begin += (self.size - 1)
        end += (self.size - 1)
        s = 0
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                s = s | self.node[end]
            if (begin - 1) & 1:
                s = s | self.node[begin]
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2
        return s

import sys
input = sys.stdin.readline


n = int(input())
s = input()
q = int(input())
query = [list(input().split()) for i in range(q)] 

alph = "abcdefghijklmnopqrstuvwxyz"
to_int = {char: i for i, char in enumerate(alph)}
st = SegmentTree(n)

for i, char in enumerate(s[0:n]):
    st.update(i, 1 << to_int[char]) 

for num, l, r in query:
    if num == "1":
        st.update(int(l) - 1, 1 << to_int[r]) 
    else:
        tmp = st.get_min(int(l) - 1, int(r))
        print(bin(tmp).count("1"))

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int i:
        """
        ret = 0
        while i > 0:
            ret += self._bit[i - 1]
            i -= i & -i
        return ret

    def __len__(self):
        return self._size


N = int(sys.stdin.buffer.readline())
S = list(sys.stdin.buffer.readline().decode().rstrip())
Q = int(sys.stdin.buffer.readline())
queries = [sys.stdin.buffer.readline().decode().rstrip().split() for _ in range(Q)]

bits = [BinaryIndexedTree(size=N) for _ in range(26)]
for i, c in enumerate(S):
    bits[ord(c) - ord('a')].add(i, 1)

ans = []
for q, a, b in queries:
    if q == '1':
        i = int(a) - 1
        c = str(b)
        bits[ord(S[i]) - ord('a')].add(i, -1)
        S[i] = c
        bits[ord(S[i]) - ord('a')].add(i, 1)
    if q == '2':
        l = int(a) - 1
        r = int(b) - 1
        cnt = 0
        for bit in bits:
            if bit.sum(r + 1) - bit.sum(l) > 0:
                cnt += 1
        ans.append(cnt)

print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

class Node:
    def __init__(self,value,index=0):
        self.value = value
        self.index = index

    def __str__(self):
        return 'val : ' + str(self.value) + ' index : ' + str(self.index)

# 0-indexed SegmentTree
class SegmentTree:
    def __init__(self,N,default_list,default_value=INF):
        self.N0 = pow(2,(N-1).bit_length())
        self.nodes = [Node(default_value,i+1-self.N0) for i in range(2*self.N0-1)]
        for i in reversed(range(2*self.N0-1)):
            ind = i+1-self.N0
            if ind >= N:
                self.nodes[i].value = default_value
            elif N > ind >= 0:
                self.nodes[i].value = default_list[ind]
            else:
                self.nodes[i] = self.process(self.nodes[i*2+1],self.nodes[i*2+2])

    def __getitem__(self,key): # getiten : ST[i]
        return self.nodes[key+self.N0-1].value

    def __setitem__(self,i,x): # update : ST[i] = x
        i += self.N0 - 1
        self.nodes[i].value = x
        while i > 0:
            i = (i-1)//2
            self.nodes[i] = self.process(self.nodes[i*2+1],self.nodes[i*2+2])

    def __str__(self):
        return '['+', '.join(map(str,[self.nodes[i+self.N0-1].value for i in range(self.N0)]))+']'

    def query(self,L,R): #[L,R)の値
        retnode = Node(0,0)
        L += self.N0
        R += self.N0
        while L < R:
            if R&1 :
                R -= 1
                retnode = self.process(retnode,self.nodes[R-1])
            if L&1 :
                retnode = self.process(retnode,self.nodes[L-1])
                L += 1
            L >>= 1; R >>= 1
        return retnode

    def process(self,node_x,node_y): #x,yが子の時，親に返る値
        return Node(node_x.value|node_y.value)

N = inp()
S = list(input())

a = ord("a")
slist = []
for s in S:
    slist.append(1<<(ord(s)-a))


ST = SegmentTree(N, default_list=slist, default_value=0)

Q = inp()
ans = []
for _ in range(Q):
    a,b,c = input().split()
    if a == "2":
        ret = ST.query(int(b)-1,int(c))
        ans.append(str(bin(ret.value)).count("1"))
    else:
        tmp = 1<<(ord(c)-ord("a"))
        ST[int(b)-1] = tmp


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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from operator import or_
class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def binsearch(self, l, r, check, reverse = False):
        L, R = l+self.N0, r+self.N0
        SL, SR = [], []
        while L < R:
            if R & 1:
                R -= 1
                SR.append(R)
            if L & 1:
                SL.append(L)
                L += 1
            L >>= 1
            R >>= 1
        
        if reverse:
            for idx in (SR + SL[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx+1]):
                    idx = 2*idx + 1
                else:
                    idx = 2*idx
            return idx - self.N0
        else:
            for idx in (SL + SR[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx]):
                    idx = 2*idx
                else:
                    idx = 2*idx + 1
            return idx - self.N0
def popcount(i):
    assert 0 <= i < 0x100000000
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24


N = int(readline())
S = []
for s in readline().strip():
    S.append(1<<(ord(s) - 97))
Q = int(readline())
T = Segtree(S, 0, initialize = True, segf = or_)
Ans = []
for _ in range(Q):
    ty, x, y = readline().strip().split()
    ty = int(ty)
    x = int(x) - 1
    if ty == 1:
        k = 1<<(ord(y) - 97)
        T.update(x, k)
    else:
        y = int(y)
        Ans.append(popcount(T.query(x, y)))
print('\n'.join(map(str, Ans)))

Submission status: Runtime Error

Solution code:
class segtree:

    def __init__(self, n, identity):
        # identityは初期値
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2 ** (len(nb) - 1)
        else:
            self.num_end_leaves = 2 ** (len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity

    def update(self, x, val):
        actual_x = x + self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0:
            actual_x = actual_x // 2
            self.array[actual_x] = self.array[actual_x * 2] | self.array[actual_x * 2 + 1]

    def get(self, q_left, q_right, arr_ind=1, leaf_left=0, depth=0):
        width_of_floor = self.num_end_leaves // (2 ** depth)
        leaf_right = leaf_left + width_of_floor - 1

        if leaf_left > q_right or leaf_right < q_left:
            return self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left, q_right, 2 * arr_ind, leaf_left, depth + 1)
            val_r = self.get(q_left, q_right, 2 * arr_ind + 1, leaf_left + width_of_floor // 2, depth + 1)
            return val_l | val_r

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

N = int(input())
S = list(input())
Q = int(input())
T = {}
j = 1
for i in range(97, 97+26):
    T[chr(i)] = j
    j *= 2

s_tree = segtree(N, 0)

for i in range(N):
    s_tree.update(i+1, T[S[i]])

for i in range(Q):
    A = list(input().split())
    a, b, c = A
    if a == "2":
        K = bin(s_tree.get(int(b), int(c)))[2:]
        d = 0
        for i in K:
            if i == "1":
                d += 1
        print(d)
    else:
        s_tree.update(int(b), T[c])

Submission status: Runtime Error

Solution code:
N=int(input())
S=input()
Q=int(input())
a=list()
for i in range(0,Q):
    a.append(0)
for i in range(0,Q):
    a[i]=input()
for i in range(0,Q):
    if int(a[i][0])==1:
        S=S[0:int(a[i][2])]+a[i][4]+S[int(a[i][2])+1:N]
    if int(a[i][0])==2:
        b=set(list(S[int(a[i][2])-1:int(a[i][4])]))
        print(len(b))

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
s = list(s)
q = int(input())
qu = []
for i in range(q):
    a = list(map(str,input().split()))
    a[0] = int(a[0])
    a[1] = int(a[1])
    if a[0] == 2:
        a[2] = int(a[2])
    a[1] -= 1
    qu.append(a)
def trans(a):
    u = ord(a)
    return u-97
import bisect as bis
p = [[] for i in range(26)]
for i in range(n):
    p[trans(s[i])].append(i)
for i in range(26):
    p[i].sort()
for i in range(q):
    if qu[i][0] == 1:
        v = s[qu[i][1]] 
        s[qu[i][1]] = qu[i][2]
        v = trans(v)
        p[v].pop(bis.bisect_left(p[v],v))
        v = trans(qu[i][2]) 
        bis.insort(p[v], qu[i][1])
    else:
        ans = 0
        for j in range(26):
            if bis.bisect_right(p[j],qu[i][1]) < len(p[j]):
                if p[j][bis.bisect_right(p[j],qu[i][1])] <= qu[i][2] or p[j][bis.bisect_right(p[j],qu[i][1])-1] == qu[i][1]:
                    ans += 1
            else:
                h = bis.bisect_right(p[j],qu[i][1])-1
                if len(p[j]) != 0:
                    if p[j][h] == qu[i][1]:
                        ans += 1
                
        print(ans)

Submission status: Runtime Error

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
import bisect
def main():
    N = I()
    S_ = S()
    Q = I()
    D = {'a': [], 'b': [], 'c': [], 'd': [], 'e': [], 'f': [], 'g': [], 'h': [], 'i': [], 'j': [], 'k': [], 'l': [], 'm': [], 'n': [], 'o': [], 'p': [], 'q': [], 'r': [], 's': [], 't': [], 'u': [], 'v': [], 'w': [], 'x': [], 'y': [], 'z': []}

    for i in range(N):
        D[S_[i]].append(i)
    for i in range(Q):
        query = LS()
        if query[0] == '1':
            i_q = int(query[1]) - 1
            c_q = query[2]
            s_q = S_[i_q]
            if s_q != c_q:
                S_ = S_[:i_q] + c_q + S_[i_q:]
                D[c_q].append(i_q)
                D[c_q].sort()
                D[s_q].remove(i_q)
        if query[0] == '2':
            cnt = 0
            l_q = int(query[1]) - 1
            r_q = int(query[2]) - 1
            for value in D.values():
                l_i = bisect.bisect_left(value, l_q)
                r_i = bisect.bisect_right(value, r_q)
                if l_i != r_i:
                    cnt += 1
            print(cnt)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import random as r
class Skip_Node:
  def __init__(self,value):
    self.value=value
    self.height=1
    while r.random()<0.5:
      self.height+=1
    self.pointer=[None for i in range(self.height)]

class Skip_List:
  def __init__(self):
    self.max_height=1
    self.pointer=[None]
  
  def insert(self,value):
    node=Skip_Node(value)
    t=self.pointer[-1]
    bt=self
    for i in range(min(self.max_height,node.height)-1,-1,-1):
      while t!=None and t.value<value:
        bt,t=t,t.pointer[i]
      bt.pointer[i]=node
      node.pointer[i]=t
      t=bt
    for i in range(self.max_height,node.height):
      self.pointer.append(node)
  
  def find(self,value):
    t=self
    for i in range(self.max_height-1,-1,-1):
      while t.pointer[i]!=None and t.pointer[i].value<value:
        t=t.pointer[i]
    return t.pointer[0].value if t.pointer[0] else None
  
  def erase(self,value):
    t=self
    for i in range(self.max_height-1,-1,-1):
      while t.pointer[i].value!=None and t.pointer[i].value<value:
        t=t.pointer[i]
      if t.pointer[i].value==value:
        t.pointer[i]=t.pointer[i].pointer[i]
    
n=int(input())
s=list(input())
ls=len(s)
toa="abcdefghijklmnopqrstuvwxyz"
ato={}
for i in range(26):
  ato[toa[i]]=i
l=[Skip_List() for i in range(26)]
for i in range(ls):
  l[ato[s[i]]].insert(i)

q=int(input())
for i in range(q):
  t,a,b=input().split()
  if t=="1":
    a=int(a)-1
    l[ato[s[a]]].erase(a)
    s[a]=b
    l[ato[b]].insert(a)
  else:
    c=0
    a=int(a)-1
    b=int(b)
    for i in range(26):
      f=l[i].find(a)
      if f!=None and f<b:
        c+=1
    print(c)

Submission status: Runtime Error

Solution code:
import random as r
class Skip_Node:
  def __init__(self,value):
    self.value=value
    self.height=1
    while r.random()<0.5:
      self.height+=1
    self.pointer=[None for i in range(self.height)]

class Skip_List:
  def __init__(self):
    self.max_height=1
    self.pointer=[None]
  
  def insert(self,value):
    node=Skip_Node(value)
    t=self.pointer[-1]
    bt=self
    for i in range(min(self.max_height,node.height)-1,-1,-1):
      while t!=None and t.value<value:
        bt,t=t,t.pointer[i]
      bt.pointer[i]=node
      node.pointer[i]=t
      t=bt
    for i in range(self.max_height,node.height):
      self.pointer.append(node)
  
  def find(self,value):
    t=self
    for i in range(self.max_height-1,-1,-1):
      while t.pointer[i]!=None and t.pointer[i].value<value:
        t=t.pointer[i]
    return t.pointer[0].value if t.pointer[0] else None
  
  def erase(self,value):
    t=self
    for i in range(self.max_height-1,-1,-1):
      while t.pointer[i].value!=None and t.pointer[i].value<value:
        t=t.pointer[i]
      if t.pointer[i].value==value:
        t.pointer[i]=t.pointer[i].pointer[i]
    
n=int(input())
s=list(input())
ls=len(s)
toa="abcdefghijklmnopqrstuvwxyz"
ato={}
for i in range(26):
  ato[toa[i]]=i
l=[Skip_List() for i in range(26)]
for i in range(ls):
  l[ato[s[i]]].insert(i)

q=int(input())
for i in range(q):
  t,a,b=input().split()
  if t=="1":
    a=int(a)-1
    l[ato[s[a]]].erase(a)
    s[a]=b
    l[ato[b]].insert(a)
    print(s)
  else:
    c=0
    a=int(a)-1
    b=int(b)
    for i in range(26):
      f=l[i].find(a)
      if f!=None and f<b:
        c+=1
    print(c)

Submission status: Runtime Error

Solution code:
import random as r
class Skip_Node:
  def __init__(self,value):
    self.value=value
    self.height=1
    while r.random()<0.5:
      self.height+=1
    self.pointer=[None for i in range(self.height)]

class Skip_List:
  def __init__(self):
    self.max_height=1
    self.pointer=[None]
  
  def insert(self,value):
    node=Skip_Node(value)
    t=self.pointer[-1]
    bt=self
    for i in range(min(self.max_height,node.height)-1,-1,-1):
      while t!=None and t.value<value:
        bt,t=t,t.pointer[i]
      bt.pointer[i]=node
      node.pointer[i]=t
      t=bt
    for i in range(self.max_height,node.height):
      self.pointer.append(node)
  
  def find(self,value):
    t=self
    for i in range(self.max_height-1,-1,-1):
      while t.pointer[i]!=None and t.pointer[i].value<value:
        t=t.pointer[i]
    return t.pointer[0].value if t.pointer[0] else None
  
  def erase(self,value):
    t=self
    for i in range(self.max_height-1,-1,-1):
      while t.pointer[i].value!=None and t.pointer[i].value<value:
        t=t.pointer[i]
      if t.pointer[i].value==value:
        t.pointer[i]=t.pointer[i].pointer[i]
    
n=int(input())
s=list(input())
ls=len(s)
toa="abcdefghijklmnopqrstuvwxyz"
ato={}
for i in range(26):
  ato[toa[i]]=i
l=[Skip_List() for i in range(26)]
for i in range(ls):
  l[ato[s[i]]].insert(i)

q=int(input())
for i in range(q):
  t,a,b=input().split()
  if t=="1":
    a=int(a)-1
    l[ato[s[a]]].erase(a)
    s[a]=b
    l[ato[b]].insert(a)
  else:
    c=0
    for i in range(26):
      a=int(a)-1
      b=int(b)
      f=l[i].find(a)
      if f!=None and f<b:
        c+=1
    print(c)

Submission status: Runtime Error

Solution code:
import bisect
from collections import defaultdict
N = int(input())
S = input()
Q = int(input())

dict = defaultdict(list)
for i in range(N):
    dict[S[i]].append(i)
# print(dict)

ans = []

for _ in range(Q):
    a, b, c = input().split()
    a = int(a)

    if a == 1:
        b = int(b) - 1
        if S[b] == c:
            continue
        else:
            dict[S[b]].remove(b)
            idx = bisect_left(dict[c], b)
            dict[c].insert(idx, b)
            S[i] = c

    elif a == 2:
        b = int(b) - 1
        c = int(c) - 1
        char_n = 0
        for key, value in dict.items():
            if len(value)>0:
                x1 = bisect.bisect_left(value, b)
                x2 = bisect.bisect_right(value, c)
                if x2 - x1 > 0:
                    char_n += 1
        ans.append(char_n)

for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
import bisect
from collections import defaultdict
N = int(input())
S = input()
Q = int(input())

dict = defaultdict(list)
for i in range(N):
    dict[S[i]].append(i)
# print(dict)

ans = []

for _ in range(Q):
    a, b, c = input().split()
    a = int(a)

    if a == 1:
        b = int(b) - 1
        if S[b] == c:
            continue
        else:
            dict[S[b]].remove(b)
            idx = bisect_left(dict[c], b)
            dict[c].insert(idx, b)
            S[i] = c

    elif a == 2:
        b = int(b) - 1
        c = int(c) - 1
        char_n = 0
        for key, value in dict.items():
            x1 = bisect.bisect_left(value, b)
            x2 = bisect.bisect_right(value, c)
            if x2 - x1 > 0:
                char_n += 1
        ans.append(char_n)

for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
import bisect
from collections import defaultdict
N = int(input())
S = input()
Q = int(input())

dict = defaultdict(list)
for i in range(N):
    dict[S[i]].append(i)
# print(dict)

ans = []

for _ in range(Q):
    a, b, c = input().split()
    a = int(a)
    if a == 1:
        b = int(b) - 1
        dict[S[b]].remove(b)
        idx = bisect.bisect_left(dict[c], b)
        dict[c].insert(idx, b)

    elif a == 2:
        b = int(b) - 1
        c = int(c) - 1
        char_n = 0
        for key, value in dict.items():
            if len(value) > 0:
                x1 = bisect.bisect_left(value, b)
                x2 = bisect.bisect_right(value, c)
                if x2 - x1 > 0:
                    char_n += 1
        ans.append(char_n)

for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
import bisect
from collections import defaultdict
N = int(input())
S = input()
Q = int(input())

dict = defaultdict(list)
for i in range(N):
    dict[S[i]].append(i)
# print(dict)

ans = []

for _ in range(Q):
    a, b, c = input().split()
    a = int(a)
    if a == 1:
        b = int(b) - 1
        dict[S[b]].remove(b)
        idx = bisect.bisect_left(dict[c], b)
        dict[c].insert(idx, b)

    elif a == 2:
        b = int(b) - 1
        c = int(c) - 1
        char_n = 0
        for key, value in dict.items():
            x1 = bisect.bisect_left(value, b)
            x2 = bisect.bisect_right(value, c)
            if x2 - x1 > 0:
                char_n += 1
        ans.append(char_n)

for i in ans:
    print(i)