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: Time Limit Exceeded

Solution code:
# BinarySearchTreeの実装
from random import random
class Treap():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.p = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None
        self.debris = []

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        if self.debris == []:
            self.data.append(None)
            self.p.append(random())
            self.left.append(None)
            self.right.append(None)
            self.parent.append(None)
            return len(self.data) - 1
        else:
            return self.debris.pop(-1)

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.p = [random()]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
            self.debris = []
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
            
            # heap
            while self.parent[i] != None and self.p[i] > self.p[self.parent[i]]:
                if self.left[self.parent[i]] == i:
                    self.rotateRight(self.parent[i])
                else:
                    self.rotateLeft(self.parent[i])
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:
            while self.left[i] != None and self.right[i] != None:
                if self.right[self.left[i]] == None or self.left[self.right[i]] == None:
                    break
                elif random() > 0.5:
                    self.rotateLeft(i)
                else:
                    self.rotateRight(i)

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            elif self.right[i] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
            elif self.left[self.right[i]] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.parent[self.left[i]] = j
            else:
                j = self.left[i]
                self.parent[j] = self.parent[i]
                self.right[j] = self.right[i]
                self.parent[self.right[i]] = j

            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j
            
            # iの初期化
            self.data[i] = None
            self.left[i] = None
            self.right[i] = None
            self.parent[i] = None
            self.debris.append(i)

    def rotateRight(self, u):
        w = self.left[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.left[u] = self.right[w]
        if self.right[w] != None:
            self.parent[self.right[w]] = u
        self.parent[u] = w
        self.right[w] = u
    
    def rotateLeft(self, u):
        w = self.right[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.right[u] = self.left[w]
        if self.left[w] != None:
            self.parent[self.left[w]] = u
        self.parent[u] = w
        self.left[w] = u

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False

import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

n = int(input())
s = list(input())
q = int(input())

# alphabet毎に整理
alp = [Treap() for _ in range(26)]
from random import shuffle
l = [i for i in range(n)]
shuffle(l)
for i in l:
    alp[order(s[i])].add(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        alp[order(s[b])].remove(b)
        alp[order(c)].add(b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i.search(b, c):
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
# BinarySearchTreeの実装
from random import random
class Treap():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.p = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None
        self.debris = []

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        if self.debris == []:
            self.data.append(None)
            self.p.append(random())
            self.left.append(None)
            self.right.append(None)
            self.parent.append(None)
            return len(self.data) - 1
        else:
            return self.debris.pop(-1)

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.p = [random()]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
            self.debris = []
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
            
            # heap
            while self.parent[i] != None and self.p[i] > self.p[self.parent[i]]:
                if self.left[self.parent[i]] == i:
                    self.rotateRight(self.parent[i])
                else:
                    self.rotateLeft(self.parent[i])
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:
            while self.left[i] != None and self.right[i] != None:
                if self.right[self.left[i]] == None or self.left[self.right[i]] == None:
                    break
                elif random() > 0.5:
                    self.rotateLeft(i)
                else:
                    self.rotateRight(i)

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            elif self.right[i] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
            elif self.left[self.right[i]] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.parent[self.left[i]] = j
            elif self.right[self.left[i]] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
                self.right[j] = self.right[i]
                self.parent[self.right[i]] = j
            else:
                print('error')
            '''
            else:
                j = self.right[i]
                while self.left[j] != None:
                    j = self.left[j]
                self.left[self.parent[j]] = self.right[j]
                if self.right[j] != None:
                    self.parent[self.right[j]] = self.parent[j]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.right[j] = self.right[i]
                self.parent[self.left[i]] = j
                self.parent[self.right[i]] = j
            '''
            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j
            
            # iの初期化
            self.data[i] = None
            self.left[i] = None
            self.right[i] = None
            self.parent[i] = None
            self.debris.append(i)

    def rotateRight(self, u):
        w = self.left[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.left[u] = self.right[w]
        if self.right[w] != None:
            self.parent[self.right[w]] = u
        self.parent[u] = w
        self.right[w] = u
    
    def rotateLeft(self, u):
        w = self.right[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.right[u] = self.left[w]
        if self.left[w] != None:
            self.parent[self.left[w]] = u
        self.parent[u] = w
        self.left[w] = u

    def exist(self, x):
        return self.data[self.find(x)] == x

    def empty(self):
        return self.root == None

    def debug(self):
        if self.root == None:
            return 'empty'
        tree = [[self.root]]
        flag = True
        while flag:
            l = []
            for i in tree[-1]:
                if i == '  ':
                    l.append('  ')
                    l.append('  ')
                    continue
                elif self.left[i] == None:
                    l.append('  ')
                else:
                    l.append(self.left[i])
                if self.right[i] == None:
                    l.append('  ')
                else:
                    l.append(self.right[i])
            flag = False
            for i in l:
                if i == '  ':
                    continue
                else:
                    tree.append(l)
                    flag = True
                    break
        for i in range(len(tree)):
            l = []
            for j in tree[i]:
                if j == '  ':
                    l.append(j)
                else:
                    k = str(self.data[j])
                    if len(k) == 1:
                        k = ' ' + k
                    l.append(k)
            n = len(tree) - i
            m = (2**n-1) * '  '
            l = (m.join(l))
            print((2**(n-1)-1) * '  ' + l)
        print()

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False

import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

n = int(input())
s = list(input())
q = int(input())

# alphabet毎に整理
alp = [Treap() for _ in range(26)]
from random import shuffle
l = [i for i in range(n)]
shuffle(l)
for i in l:
    alp[order(s[i])].add(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        alp[order(s[b])].remove(b)
        alp[order(c)].add(b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i.search(b, c):
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from operator import or_


def read():
    N = int(input().strip())
    S = input().strip()
    Q = int(input().strip())
    return N, S, Q


class SegmentTree():
    
    def __init__(self, size, op=min, init_value=10**8):
        """初期化"""
        self.size = size
        self.op = op
        self.init_value = init_value
        n = 2 ** ((size-1).bit_length())
        treesize = n << 1
        st = [init_value] * treesize
        self.st = st
        self.offset = len(st) >> 1

    @classmethod
    def from_array(cls, a, op=min, init_value=10**8):
        st = cls(len(a), op=op, init_value=init_value)
        for i, x in enumerate(a):
            st.update(i, x)
        return st

    def update(self, key, value):
        """値の更新"""
        k = self.offset + key
        self.st[k] = value
        k >>= 1
        while k > 0:
            self.st[k] = self.op(self.st[k << 1], self.st[(k << 1) + 1])
            k >>= 1

    def query(self, a, b):
        """区間[a, b) に対する累積操作
        """
        a += self.offset
        b += self.offset - 1
        s = self.init_value
        op = self.op
        while a < b:
            if a & 1:
                s = op(s, self.st[a])
                a += 1
            a >>= 1
            if not b & 1:
                s = op(s, self.st[b])
                b -= 1
            b >>= 1
        if a == b:
            s = op(s, self.st[a])
        return s


def solve_online(N, S, Q):
    tree = SegmentTree(N, op=or_, init_value=0)
    for i, s in enumerate(S):
        c = ord(s) - 97
        tree.update(i, 1 << c)

    for _ in range(Q):
        op, a, b = input().strip().split()
        if op == "1":
            i, c = int(a)-1, ord(b) - 97
            tree.update(i, 1 << c)
        elif op == "2":
            l, r = int(a)-1, int(b)-1
            b = tree.query(l, r+1)
            s = str(bin(b)).count("1")
            print(s)


if __name__ == '__main__':
    inputs = read()
    outputs = solve_online(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from operator import or_


def read():
    N = int(input().strip())
    S = input().strip()
    Q = int(input().strip())
    return N, S, Q


class SegmentTree():
    
    def __init__(self, size, op=min, init_value=10**8):
        """初期化"""
        self.size = size
        self.op = op
        self.init_value = init_value
        n = 2 ** ((size-1).bit_length())
        treesize = n * 2
        st = [init_value] * treesize
        self.st = st
        self.offset = len(st) // 2

    @classmethod
    def from_array(cls, a, op=min, init_value=10**8):
        st = cls(len(a), op=op, init_value=init_value)
        for i, x in enumerate(a):
            st.update(i, x)
        return st

    def update(self, key, value):
        """値の更新"""
        k = self.offset + key
        self.st[k] = value
        k >>= 1
        while k > 0:
            self.st[k] = self.op(self.st[k * 2], self.st[k * 2 + 1])
            k >>= 1

    def _query_bottomup(self, a, b):
        """区間[a, b) に対する累積操作
        """
        a += self.offset
        b += self.offset - 1
        s = self.init_value
        op = self.op
        while a < b:
            if a & 1:
                s = op(s, self.st[a])
                a += 1
            a >>= 1
            if not b & 1:
                s = op(s, self.st[b])
                b -= 1
            b >>= 1
        if a == b:
            s = op(s, self.st[a])
        return s

    def query(self, a, b):
        """区間[a, b) に対する累積操作"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        return self._query_bottomup(a, b)


def solve_online(N, S, Q):
    tree = SegmentTree(N, op=or_, init_value=0)
    z = ord("a")
    for i in range(N):
        c = ord(S[i]) - z
        tree.update(i, 1 << c)

    for _ in range(Q):
        op, a, b = input().strip().split()
        if op == "1":
            i, c = int(a)-1, ord(b) - z
            tree.update(i, 1 << c)
        elif op == "2":
            l, r = int(a)-1, int(b)-1
            b = tree.query(l, r+1)
            s = str(bin(b)).count("1")
            print(s)


if __name__ == '__main__':
    inputs = read()
    outputs = solve_online(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from operator import or_


def read():
    N = int(input().strip())
    S = input().strip()
    Q = int(input().strip())
    return N, S, Q


class SegmentTree():
    
    def __init__(self, size, op=min, init_value=10**8):
        """初期化"""
        self.size = size
        self.op = op
        self.init_value = init_value
        n = 2 ** ((size-1).bit_length())
        treesize = n * 2
        st = [init_value] * treesize
        self.st = st
        self.offset = len(st) // 2

    @classmethod
    def from_array(cls, a, op=min, init_value=10**8):
        st = cls(len(a), op=op, init_value=init_value)
        for i, x in enumerate(a):
            st.update(i, x)
        return st

    def update(self, key, value):
        """値の更新"""
        k = self.offset + key
        self.st[k] = value
        k >>= 1
        while k > 0:
            self.st[k] = self.op(self.st[k * 2], self.st[k * 2 + 1])
            k >>= 1

    def _query_bottomup(self, a, b):
        """区間[a, b) に対する累積操作
        """
        a += self.offset
        b += self.offset - 1
        s = self.init_value
        op = self.op
        while a < b:
            if a & 1:
                s = op(s, self.st[a])
                a += 1
            a >>= 1
            if not b & 1:
                s = op(s, self.st[b])
                b -= 1
            b >>= 1
        if a == b:
            s = op(s, self.st[a])
        return s

    def query(self, a, b):
        """区間[a, b) に対する累積操作"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        return self._query_bottomup(a, b)


def solve_online(N, S, Q):
    tree = SegmentTree(N, op=or_, init_value=0)
    for i in range(N):
        c = ord(S[i]) - ord("a")
        tree.update(i, 1 << c)

    for _ in range(Q):
        op, a, b = input().strip().split()
        if op == "1":
            i, c = int(a)-1, ord(b) - ord("a")
            tree.update(i, 1 << c)
        elif op == "2":
            l, r = int(a)-1, int(b)-1
            b = tree.query(l, r+1)
            s = 0
            while b > 0:
                if b & 1:
                    s += 1
                b >>= 1
            print(s)


if __name__ == '__main__':
    inputs = read()
    outputs = solve_online(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def ctoi(c):
    return ord(c)-97
class BIT:
    def __init__(self, n):
        self.unit_sum=0 # to be set
        self.n=n
        self.dat=[0]*(n+1)#[1,n]
    def add(self,a,x): #a(1-)
        i=a
        while i<=self.n:
            self.dat[i]+=x
            i+=i&-i
    def sum(self,a,b=None): 
        if b!=None:
            return self.sum(b-1)-self.sum(a-1) #[a,b) a(1-),b(1-)
        res=self.unit_sum
        i=a
        while i>0:
            res+=self.dat[i]
            i-=i&-i
        return res  #Σ[1,a] a(1-)   
    def __str__(self):
        self.ans=[]
        for i in range(1,self.n):
            self.ans.append(self.sum(i,i+1))
        return ' '.join(map(str,self.ans))

def main():
    n=int(input())
    S=list(input())
    q=int(input())
    BIT_tree=[]
    for i in range(26):
        obj=BIT(n+1)
        BIT_tree.append(obj)
    for i in range(n):
        BIT_tree[ctoi(S[i])].add(i+1,1)
    for _ in range(q):
        query=input().split()
        if query[0]=="1":
            index,x=int(query[1])-1,query[2]
            BIT_tree[ctoi(S[index])].add(index+1,-1)
            BIT_tree[ctoi(x)].add(index+1,1)
            S[index]=x
        else:
            l,r=int(query[1])-1,int(query[2])-1
            ans=0
            for c in range(26):
                if BIT_tree[c].sum(l+1,r+2):
                    ans+=1
            print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from bisect import bisect_left,bisect
def main():
    n=int(input())
    S=list(input())
    q=int(input())
    set_s={chr(ord('a')+i):[] for i in range(26)}
    for i,s in enumerate(S):
        set_s[s].append(i)
    for _ in range(q):
        query=input().split()
        if query[0]=="1":
            i,c=int(query[1])-1,query[2]
            if S[i]==c:continue
            set_s[S[i]].remove(i)
            set_s[c].insert(bisect_left(set_s[c],i),i)
            S[i]=c
        else:
            l,r=int(query[1])-1,int(query[2])-1
            ans=0
            for i in range(26):
                ss=chr(ord('a')+i)
                if bisect(set_s[ss],r)>bisect_left(set_s[ss],l):
                    ans+=1
            print(ans)


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from operator import or_


def read():
    N = int(input().strip())
    S = input().strip()
    Q = int(input().strip())
    return N, S, Q


class SegmentTree():
    
    def __init__(self, size, op=min, init_value=10**8):
        """初期化"""
        self.size = size
        self.op = op
        self.init_value = init_value
        n = 2 ** ((size-1).bit_length())
        treesize = n * 2
        st = [init_value for i in range(treesize)]
        self.st = st

    @classmethod
    def from_array(cls, a, op=min, init_value=10**8):
        st = cls(len(a), op=op, init_value=init_value)
        for i, x in enumerate(a):
            st.update(i, x)
        return st

    def update(self, key, value):
        """値の更新"""
        offset = len(self.st) // 2
        k = offset + key
        self.st[k] = value
        k >>= 1
        while k > 0:
            self.st[k] = self.op(self.st[k * 2], self.st[k * 2 + 1])
            k >>= 1

    def _query_bottomup(self, a, b):
        """区間[a, b) に対する累積操作
        """
        offset = len(self.st) // 2
        a += offset
        b += offset - 1
        s = self.init_value
        while a < b:
            if a & 1 == 1:
                s = self.op(s, self.st[a])
                a += 1
            a >>= 1
            if b & 1 == 0:
                s = self.op(s, self.st[b])
                b -= 1
            b >>= 1
        if a == b:
            s = self.op(s, self.st[a])
        return s

    def _query_topdown(self, a, b, k, l, r):
        """区間[a, b) に対する累積操作
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        if r <= a or b <= l:
            return self.init_value
        if a <= l and r <= b:
            return self.st[k]
        mid = (l + r) // 2
        lv = self._query_topdown(a, b, k * 2, l, mid)
        rv = self._query_topdown(a, b, k * 2 + 1, mid, r)
        return self.op(lv, rv)

    def query(self, a, b):
        """区間[a, b) に対する累積操作"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        # return self._query_topdown(a, b, k=1, l=0, r=len(self.st)//2)
        return self._query_bottomup(a, b)


def solve_online(N, S, Q):
    tree = SegmentTree(N, op=or_, init_value=0)
    C = [ord(s) - ord("a") for s in S]
    for i in range(N):
        c = ord(S[i]) - ord("a")
        tree.update(i, 1 << c)

    for _ in range(Q):
        op, a, b = input().strip().split()
        if op == "1":
            i, c = int(a)-1, ord(b) - ord("a")
            tree.update(i, 1 << c)
        elif op == "2":
            l, r = int(a)-1, int(b)-1
            b = tree.query(l, r+1)
            s = 0
            while b > 0:
                if b & 1 == 1:
                    s += 1
                b >>= 1
            print(s)


if __name__ == '__main__':
    inputs = read()
    outputs = solve_online(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from operator import or_


def read():
    N = int(input().strip())
    S = input().strip()
    Q = int(input().strip())
    return N, S, Q


class SegmentTree():
    
    def __init__(self, size, op=min, init_value=10**8):
        """初期化"""
        self.size = size
        self.op = op
        self.init_value = init_value
        n = 2 ** ((size-1).bit_length())
        treesize = n * 2
        st = [init_value for i in range(treesize)]
        self.st = st

    @classmethod
    def from_array(cls, a, op=min, init_value=10**8):
        st = cls(len(a), op=op, init_value=init_value)
        for i, x in enumerate(a):
            st.update(i, x)
        return st

    def update(self, key, value):
        """値の更新"""
        offset = len(self.st) // 2
        k = offset + key
        self.st[k] = value
        k >>= 1
        while k > 0:
            self.st[k] = self.op(self.st[k * 2], self.st[k * 2 + 1])
            k >>= 1

    def _query_bottomup(self, a, b):
        """区間[a, b) に対する累積操作
        """
        offset = len(self.st) // 2
        a += offset
        b += offset - 1
        s = self.init_value
        while a < b:
            if a & 1 == 1:
                s = self.op(s, self.st[a])
                a += 1
            a >>= 1
            if b & 1 == 0:
                s = self.op(s, self.st[b])
                b -= 1
            b >>= 1
        if a == b:
            s = self.op(s, self.st[a])
        return s

    def _query_topdown(self, a, b, k, l, r):
        """区間[a, b) に対する累積操作
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        if r <= a or b <= l:
            return self.init_value
        if a <= l and r <= b:
            return self.st[k]
        mid = (l + r) // 2
        lv = self._query_topdown(a, b, k * 2, l, mid)
        rv = self._query_topdown(a, b, k * 2 + 1, mid, r)
        return self.op(lv, rv)

    def query(self, a, b):
        """区間[a, b) に対する累積操作"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        # return self._query_topdown(a, b, k=1, l=0, r=len(self.st)//2)
        return self._query_bottomup(a, b)


def solve_online(N, S, Q):
    trees = [SegmentTree(N, op=or_, init_value=0) for i in range(26)]
    C = [ord(s) - ord("a") for s in S]
    for i in range(N):
        c = ord(S[i]) - ord("a")
        trees[c].update(i, 1)

    for _ in range(Q):
        op, a, b = input().strip().split()
        if op == "1":
            i, c1 = int(a)-1, ord(b) - ord("a")
            c0 = C[i]
            trees[c0].update(i, 0)
            C[i] = c1
            trees[c1].update(i, 1)
        elif op == "2":
            l, r = int(a)-1, int(b)-1
            s = sum([trees[i].query(l, r+1) for i in range(26)])
            print(s)


if __name__ == '__main__':
    inputs = read()
    outputs = solve_online(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))