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:
import sys
import bisect
import math
import itertools
import heapq
import collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


class SegmentTree():
    def __init__(self, init_val, N):
        """
        Parameters
        ----------
        init_val:int
            identity element
        N:int
            the number of nodes
        """
        self.init_val = init_val
        # Range Minimum Query
        self.N0 = 2**(N-1).bit_length()
        # 0-indexedで管理
        self.data = [self.init_val] * (2 * self.N0)

    def _segfunc(self, left, right):
        res = left | right
        return res

    def update(self, k, x):
        """
        Parameters
        ----------
        k:int
            target index(0-index)
        x:any
            target value
        """
        k += self.N0-1
        self.data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.data[k] = self._segfunc(self.data[2*k+1], self.data[2*k+2])

    def query(self, l, r):
        """
        Parameters
        ----------
        l,r:int
            target range [l,r)

        Return
        ----------
        res:any
            val
        """
        L = l + self.N0
        R = r + self.N0
        s = self.init_val
        while L < R:
            if R & 1:
                R -= 1
                s = self._segfunc(s, self.data[R-1])

            if L & 1:
                s = self._segfunc(s, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return s


def main():
    n = inp()
    s = [set(i) for i in list(input()) if i != "\n"]
    st = SegmentTree(set(), n)
    for i in range(n):
        st.update(i, s[i])
    q = inp()
    ans = []
    for i in range(q):
        mode, first, second = input().split()
        if mode == "1":
            st.update(int(first) - 1, set(second))
        else:
            ans.append(len(st.query(int(first) - 1, int(second))))
    for i in ans:
        print(i)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

class SegmentTree():
    def __init__(self, init_val, N):
        """
        Parameters
        ----------
        init_val:int
            identity element
        N:int
            the number of nodes
        """
        self.init_val=init_val
        # Range Minimum Query
        self.N0 = 2**(N-1).bit_length()
        # 0-indexedで管理
        self.data = [self.init_val] * (2 * self.N0)

    def _segfunc(self, left, right):
        res= left | right
        return res

    def update(self,k, x):
        """
        Parameters
        ----------
        k:int
            target index(0-index)
        x:any
            target value
        """
        k += self.N0-1
        self.data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.data[k] = self._segfunc(self.data[2*k+1], self.data[2*k+2])

    def query(self, l, r):
        """
        Parameters
        ----------
        l,r:int
            target range [l,r)

        Return
        ----------
        res:any
            val
        """
        L = l + self.N0
        R = r + self.N0
        s = self.init_val
        while L < R:
            if R & 1:
                R -= 1
                s = self._segfunc(s, self.data[R-1])
    
            if L & 1:
                s = self._segfunc(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
def main():
    n=inp()
    s=[set(i) for i in list(input()) if i!="\n"]
    st = SegmentTree(set(), n)
    for i in range(n):
        st.update(i,s[i])
    q = inp()
    ans = []
    for i in range(q):
        mode, first, second = input().split()
        if mode == "1":
            st.update(int(first) - 1, set(second))
        else:
            ans.append(len(st.query(int(first) - 1, int(second))))
    for i in ans:
        print(i)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

class SegmentTree():
    def __init__(self, init_val, N):
        """
        Parameters
        ----------
        init_val:int
            identity element
        N:int
            the number of nodes
        """
        self.init_val=init_val
        # Range Minimum Query
        self.N0 = 2**(N-1).bit_length()
        # 0-indexedで管理
        self.data = [self.init_val] * (2 * self.N0)

    def _segfunc(self, left, right):
        res= left | right
        return res

    def update(self,k, x):
        """
        Parameters
        ----------
        k:int
            target index(0-index)
        x:any
            target value
        """
        k += self.N0-1
        self.data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.data[k] = self._segfunc(self.data[2*k+1], self.data[2*k+2])

    def query(self, l, r):
        """
        Parameters
        ----------
        l,r:int
            target range [l,r)

        Return
        ----------
        res:any
            val
        """
        L = l + self.N0
        R = r + self.N0
        s = self.init_val
        while L < R:
            if R & 1:
                R -= 1
                s = self._segfunc(s, self.data[R-1])
    
            if L & 1:
                s = self._segfunc(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

n=inp()
s=[set(i) for i in list(input()) if i!="\n"]
st = SegmentTree(set(), n)
for i in range(n):
    st.update(i,s[i])
q = inp()
ans = []
for i in range(q):
    mode, first, second = input().split()
    if mode == "1":
        st.update(int(first) - 1, set(second))
    else:
        ans.append(len(st.query(int(first) - 1, int(second))))
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

class segment_tree:
    '''
    init_val(int): 初期化値
    Input(array):  入力
    '''
    def __init__(self, init_val, Input):
        #self.num:n以上の最小の2のべき乗(一番下のNodeの数)
        n=len(Input)
        self.init_val = init_val
        self.num = 2 ** (n - 1).bit_length()
        self.seg = [init_val] * 2 * self.num
        for i in range(n):
            self.seg[i + self.num - 1] = Input[i]
        for i in range(self.num - 2, -1, -1):
            self.seg[i]=self._segfunc(self.seg[2*i+1],self.seg[2*i+2])
    def _segfunc(self, left, right):
        '''
        ここに求めたい関数を入れる
        ex)最小値問題→min, 
        left:左の子
        right:右の子
        '''
        res= left | right
        return res
    def update(self, k, x):
        '''
        k番目の値をxに書き換える(0-index)
        '''
        k += self.num - 1
        self.seg[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.seg[k] = self._segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])
    def query(self, p, q):
        '''
        区間[p,q)の目的の値を取り出す
        '''
        if q <= p:
            return self.init_val
        p += self.num - 1
        q += self.num - 2
        res = self.init_val
        while q - p > 1:
            if p % 2 == 0: #始点が偶数or終点が奇数だと端っこが余る
                res = self._segfunc(res, self.seg[p])
            if q % 2 == 1:
                res = self._segfunc(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        res = self._segfunc(res, self.seg[p])
        res = self._segfunc(res, self.seg[q])
        return res
n=inp()
s=[set(i) for i in list(input()) if i!="\n"]
st = segment_tree(set(), s)
q = inp()
ans = []
for i in range(q):
    mode, first, second = input().split()
    if mode == "1":
        st.update(int(first) - 1, set(second))
    else:
        ans.append(len(st.query(int(first)-1, int(second))))
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import bisect

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    S = list(input())
    Q = int(input())

    L = [[] for x in range(26)] # i番目のリストは、アルファベットが現れるインデックスのリストを持つ。

    for idx, s in enumerate(S):
        L[ord(s)-ord("a")].append(idx)

    for _ in range(Q):
        row = input().split()
        if row[0] == '1':
            y, z = int(row[1])-1, row[2]
            idx_target = ord(S[y]) - ord("a")
            idx_del = bisect.bisect_left(L[idx_target], y)
            if idx_del < len(L[idx_target]):
                L[idx_target].pop(idx_del)
            bisect.insort(L[ord(z) - ord("a")], y)
            S[y] = z

        elif row[0] == '2':
            y, z = int(row[1]) - 1, int(row[2]) - 1
            answer = 0
            for idx_alphabet in range(26):
                left = bisect.bisect_left(L[idx_alphabet], y)
                if left < len(L[idx_alphabet]) and y <= L[idx_alphabet][left] <= z:
                    answer += 1
            print(answer)

    # Failed to predict input format
    pass

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import bisect

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    S = list(input())
    Q = int(input())

    alphabets = [chr(i) for i in range(ord("a"), ord("a")+26)]
    L = [[] for x in alphabets] # i番目のリストは、アルファベットが現れるインデックスのリストを持つ。

    for idx, s in enumerate(S):
        L[ord(s)-ord("a")].append(idx)

    for _ in range(Q):
        row = input().split()
        if row[0] == '1':
            y, z = int(row[1])-1, row[2]
            target = S[y]
            idx_del = bisect.bisect_left(L[ord(target)-ord("a")], y)
            if idx_del < len(L[ord(target)-ord("a")]):
                L[ord(target)-ord("a")].pop(idx_del)
            bisect.insort(L[ord(z)-ord("a")], y)
            S[y] = z

        elif row[0] == '2':
            y, z = int(row[1]) - 1, int(row[2]) - 1
            answer = 0
            for alphabet in alphabets:
                left = bisect.bisect_left(L[ord(alphabet)-ord("a")], y)
                if left < len(L[ord(alphabet)-ord("a")]) and y <= L[ord(alphabet)-ord("a")][left] <= z:
                    answer += 1
            print(answer)

    # Failed to predict input format
    pass

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import bisect

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    S = list(input())
    Q = int(input())

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

    L = {x:[] for x in alphabets} # i番目のリストは、アルファベットが現れるインデックスのリストを持つ。
    for idx, s in enumerate(S):
        L[s].append(idx)

    for _ in range(Q):
        row = input().split()
        if row[0] == '1':
            x, y, z = int(row[0]), int(row[1])-1, row[2]
        elif row[0] == '2':
            x, y, z = int(row[0]), int(row[1]) - 1, int(row[2]) - 1

        if x == 1:
            target = S[y]
            idx_del = bisect.bisect_left(L[target], y)
            if idx_del < len(L[target]):
                L[target].pop(idx_del)
            bisect.insort(L[z], y)
            S[y] = z
        elif x == 2:
            answer = 0
            for alphabet in alphabets:
                left = bisect.bisect_left(L[alphabet], y)
                if left < len(L[alphabet]) and y <= L[alphabet][left] <= z:
                    answer += 1
            print(answer)

    # Failed to predict input format
    pass

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import bisect

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    S = list(input())
    Q = int(input())

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

    L = {x:[] for x in alphabets} # i番目のリストは、アルファベットが現れるインデックスのリストを持つ。
    for idx, s in enumerate(S):
        L[s].append(idx)

    for _ in range(Q):
        row = input().split()
        if row[0] == '1':
            x, y, z = int(row[0]), int(row[1])-1, row[2]
        elif row[0] == '2':
            x, y, z = int(row[0]), int(row[1]) - 1, int(row[2]) - 1

        if x == 1:
            target = S[y]
            idx_del = bisect.bisect_left(L[target], y)
            if idx_del < len(L[target]):
                del L[target][idx_del]
            bisect.insort(L[z], y)
            S[y] = z
        elif x == 2:
            answer = 0
            for alphabet in alphabets:
                left = bisect.bisect_left(L[alphabet], y)
                if left < len(L[alphabet]) and y <= L[alphabet][left] <= z:
                    answer += 1
            print(answer)

    # Failed to predict input format
    pass

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import bisect

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    S = list(input())
    Q = int(input())

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

    L = {x:[] for x in alphabets} # i番目のリストは、アルファベットが現れるインデックスのリストを持つ。
    for idx, s in enumerate(S):
        L[s].append(idx)

    queries = []
    for _ in range(Q):
        row = input().split()
        if row[0] == '1':
            queries.append([int(row[0]), int(row[1])-1, row[2]])
        elif row[0] == '2':
            queries.append([int(row[0]), int(row[1])-1, int(row[2])-1])

    for query in queries:
        if query[0] == 1:
            target = S[query[1]]
            idx_del = bisect.bisect_left(L[target], query[1])
            if idx_del < len(L[target]):
                del L[target][idx_del]
            bisect.insort(L[query[2]], query[1])
            S[query[1]] = query[2]
        elif query[0] == 2:
            answer = 0
            for i in range(26):
                alphabet = chr(ord("a") + i)
                left = bisect.bisect_left(L[alphabet], query[1])
                if left < len(L[alphabet]) and query[1] <= L[alphabet][left] <= query[2]:
                    answer += 1
            print(answer)

    # Failed to predict input format
    pass

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import log2, ceil


class SegTree:
    #####単位元######
    ide_ele = 0

    def __init__(self, init_val):
        n = len(init_val)
        self.num = 2**ceil(log2(n))
        self.seg = [self.ide_ele] * (2 * self.num - 1)

        for i in range(n):
            self.seg[i + self.num - 1] = init_val[i]

        # built
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

    #####segfunc######
    def segfunc(self, x, y):
        return x+y

    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.ide_ele
        if a <= l and r <= b:
            return self.seg[k]
        else:
            vl = self.query(a, b, k*2+1, l, (l+r)//2)
            vr = self.query(a, b, k*2+2, (l+r)//2, r)
            return self.segfunc(vl, vr)


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

seg_trees = []
ts = [chr(ord('a')+i) for i in range(26)]
for t in ts:
    init_val = [int(s == t) for s in S]
    seg_tree = SegTree(init_val)
    seg_trees.append(seg_tree)

ans = []
for _ in range(Q):
    i, l, r = input().split()
    i = int(i)
    l = int(l)
    if i == 1:
        for i,t in enumerate(ts):
            seg_trees[i].update(l-1, int(r == t))
    else:
        r = int(r)
        num = [seg_trees[i].query(l-1, r, 0, 0, seg_trees[i].num) > 0 for i, t in enumerate(ts)]
        ans.append(sum(num))

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from math import log2, ceil


class SegTree:
    #####単位元######
    ide_ele = []

    def __init__(self, init_val):
        n = len(init_val)
        self.num = 2**ceil(log2(n))
        self.seg = [self.ide_ele] * (2 * self.num - 1)

        for i in range(n):
            self.seg[i + self.num - 1] = init_val[i]

        # built
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

    #####segfunc######
    def segfunc(self, x, y):
        _x = x[:]
        _y = y[:]
        _x.extend(_y)
        ans = list(set(_x))

        return ans

    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.ide_ele
        if a <= l and r <= b:
            return self.seg[k]
        else:
            vl = self.query(a, b, k*2+1, l, (l+r)//2)
            vr = self.query(a, b, k*2+2, (l+r)//2, r)
            return self.segfunc(vl, vr)


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

init_val = [[s] for s in S]
seg_tree = SegTree(init_val)


ans = []
for _ in range(Q):
    i, l, r = input().split()
    i = int(i)
    l = int(l)
    if i == 1:
        seg_tree.update(l-1, [r])
    else:
        r = int(r)
        ans.append(len(seg_tree.query(l-1, r, 0, 0, seg_tree.num)))

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:

import copy
import itertools
import sys
sys.setrecursionlimit(10**5)

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

si = []
for i in range(len(s)):
    si.append(int(ord(s[i])-int(ord("a"))))

si1000 = [[0] * 26 for i in range((len(si)//10000)+1)]
for i in range(len(si)):
    si1000[i//10000][si[i]] = 1

for i in range(q):
    if(int(qa[i][0])==1):
        si[int(qa[i][1])-1] = ord(qa[i][2])-int(ord("a"))
        si1000[(int(qa[i][1])-1)//10000] = [0] * 26
        if ((int(qa[i][1])-1)//10000)*10000+10000-1 < len(si):
            for j in range(10000):
                si1000[(int(qa[i][1])-1)//10000][si[((int(qa[i][1])-1)//10000)*10000+j]] = 1
    else:
        chex = [0] * 26
        #for j in range(int(qa[i][1])-1, int(qa[i][2])-1+1):
        #    chex[si[j]] = 1
        #print(sum(chex))
        j = int(qa[i][1])-1
        while j < int(qa[i][2])-1+1:
            if j % 10000 == 0 and j + 10000 < int(qa[i][2])-1+1:
                for k in range(26):
                    if si1000[j//10000][k] == 1:
                        chex[k] = 1
                j += 10000
            else:
                chex[si[j]] = 1
                j += 1
        print(sum(chex))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
table = {x: 2**i for i, x in enumerate(map(chr, range(97, 123)))}

SEG_LEN = n
SEG = [0]*(SEG_LEN*2)


def update(i, x):
    i += SEG_LEN
    SEG[i] = table[x]
    while i > 0:
        i //= 2
        SEG[i] = SEG[i*2] | SEG[i*2+1]


def find(left, right):
    left += SEG_LEN
    right += SEG_LEN
    ans = 0
    while left < right:
        if left % 2 == 1:
            ans = SEG[left] | ans
            left += 1
        left //= 2
        if right % 2 == 1:
            ans = SEG[right-1] | ans
            right -= 1
        right //= 2
    return format(ans, 'b').count('1')


for i, c in enumerate(s):
    update(i, c)

q = int(input())
for _ in range(q):
    com, *query = input().split()
    if com == '1':
        idx, x = query
        update(int(idx)-1, x)
    else:
        L, R = map(int, query)
        print(find(L-1, R))

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left as b
def main():
	input=sys.stdin.readline
	n=int(input())
	s=list(input().rstrip())
	q=int(input())
	word=[[]for _ in range(26)]
	for i,j in enumerate(s):
		ch=ord(j)-97
		word[ch].append(i)
	for _ in range(q):
		query=input().split()
		if query[0]=="1":
			i,x=int(query[1])-1,ord(query[2])-97
			old=ord(s[i])-97
			if s==x:
				continue
			word[old].remove(i)
			new=b(word[x],i)
			word[x].insert(new,i)
			s[i]=chr(x+97)
		else:
			l,r=int(query[1])-1,int(query[2])-1
			kind=0
			for i in range(26):
				ll=b(word[i],l)
				if ll==len(word[i]):
					continue
				if word[i][ll]<=r:
					kind+=1
			print(kind)
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
def main():
	import bisect,sys
	input=sys.stdin.readline
	n=int(input())
	s=list(input().rstrip())
	q=int(input())
	word=[[]for _ in range(26)]
	for i,j in enumerate(s):
		ch=ord(j)-ord("a")
		word[ch].append(i)
	for _ in range(q):
		query=input().split()
		if query[0]=="1":
			i,x=int(query[1])-1,ord(query[2])-ord("a")
			old=ord(s[i])-ord("a")
			if s==x:
				continue
			word[old].remove(i)
			new=bisect.bisect_left(word[x],i)
			word[x].insert(new,i)
			s[i]=chr(x+ord("a"))
		else:
			l,r=int(query[1])-1,int(query[2])-1
			kind=0
			for i in range(26):
				ll=bisect.bisect_left(word[i],l)
				if ll==len(word[i]):
					continue
				if word[i][ll]<=r:
					kind+=1
			print(kind)
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(300000)

class BinaryIndexedTree(object):

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

    def add(self, i, v):
        while i <= self.n:
            self.vals[i] += v
            i += i & -i

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

    def sum_range(self, l, r):
        # l and r are 1-based index and inclusive
        return self.sum(r) - self.sum(l - 1)


def update(i, val, n, bi_tree, sign=1):
    i += 1
    while i < n:
        bi_tree[i][val] += (1 * sign)
        i += i & -i


def get_sum(i, bi_tree):
    ans = [0] * 26
    while i > 0:
        tmp = bi_tree[i]
        for j in range(26):
            ans[j] += tmp[j]
        i -= i & -i
    return ans


def get_range_sum(left, right, bi_tree):
    r_sum = get_sum(right, bi_tree)
    l_sum = get_sum(left - 1, bi_tree)
    for i in range(26):
        r_sum[i] -= l_sum[i]
    return r_sum


from pprint import pprint

def solve(N, S, Q, queries):
    #arr.insert(0, 0)   # insert dummy node for 1-based indexing
    #bit = [0 for i in range(n+1)]
    trees = []
    for i in range(26):
        trees.append(BinaryIndexedTree(N))

    s = []
    for i, c in enumerate(S):
        c_idx = ord(c) - ord('a')
        if 'a' <= c <= 'z':
            trees[c_idx].add(i + 1, 1)
        s.append(c)

    for q in queries:
        if q[0] == '1':
            i, c = int(q[1]), q[2]
            p = s[i - 1]
            s[i - 1] = c
            trees[ord(p) - ord('a')].add(i, -1)
            trees[ord(c) - ord('a')].add(i, 1)
        if q[0] == '2':
            l, r = int(q[1]), int(q[2])
            ret = 0
            for tree in trees:
                cnt = tree.sum_range(l, r)
                if cnt:
                    ret += 1
            print(ret)
        #pprint(get_range_sum(1, 5, bit))
        #print(s)
        #print()

    return

def _solve(N, S, Q, queries):
    #arr.insert(0, 0)   # insert dummy node for 1-based indexing
    #bit = [0 for i in range(n+1)]
    bit = [[0] * 26 for i in range(N + 1)]
    s = []
    for i, c in enumerate(S):
        if 'a' <= c <= 'z':
            update(i, ord(c) - ord('a'), N + 1, bit)
        s.append(c)

    for q in queries:
        if q[0] == '1':
            i, c = int(q[1]) - 1, q[2]
            p = s[i]
            update(i, ord(p) - ord('a'), N + 1, bit, -1)
            update(i, ord(c) - ord('a'), N + 1, bit, 1)
            s[i] = c
        if q[0] == '2':
            l, r = int(q[1]), int(q[2])
            counts = get_range_sum(l, r, bit)
            ret = 0
            for x in counts:
                if x > 0:
                    ret += 1
            print(ret)
        #pprint(get_range_sum(1, 5, bit))
        #print(s)
        #print()

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))
    S = str(next(tokens))
    Q = int(next(tokens))
    q = []
    for i in range(Q):
        q.append(list(map(str, input().split())))
    solve(N, S, Q, q)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self,siz,v = 0):
        self.n = 1
        self.v = v
        while self.n < siz: self.n *= 2
        self.node = [self.v]*(2*self.n-1)

    def merge(self,x,y): return x | y

    def update(self,i,x):
        i += self.n-1
        self.node[i] = x
        while i > 0:
            i = (i-1)//2
            self.node[i] = self.merge(self.node[i*2+1],self.node[i*2+2])
    
    def query(self,a,b):
        vl = vr = self.v
        a += self.n-1
        b += self.n-1
        while a < b:
            if a & 1 == 0: vl = self.merge(vl,self.node[a])
            if b & 1 == 0: vr = self.merge(vr,self.node[b-1])
            a //= 2
            b = (b-1)//2
        return self.merge(vl,vr)
    
n = int(input())
st = SegmentTree(n)
s = list(input())
def f(c): return 1<<(ord(c) - ord("a"))
for i in range(n): st.update(i,f(s[i]))
q = int(input())
for _ in range(q):
    typ,x,y = input().split()
    if typ == "1":
        i,c = int(x)-1,y
        if s[i] == c: continue
        st.update(i,f(c))
        s[i] = c
    else:
        l,r = int(x)-1,int(y)
        print(bin(st.query(l,r)).count("1"))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self,n):
        self.siz = 1
        while self.siz < n: self.siz *= 2
        self.node = [0]*(2*self.siz-1)

    def update(self,i,x):
        i += self.siz-1
        self.node[i] = x
        while i > 0:
            i = (i-1)//2
            self.node[i] = self.node[i*2+1] | self.node[i*2+2]
    
    def query(self,a,b,k=0,l=0,r=-1):
        if r < 0: r = self.siz
        if r <= a or b <= l: return 0
        if a <= l and r <= b: return self.node[k]
        vl = self.query(a,b,k*2+1,l,(l+r)//2)
        vr = self.query(a,b,k*2+2,(l+r)//2,r)
        return vl | vr
    
n = int(input())
st = SegmentTree(n)
s = list(input())
def f(c): return 1<<(ord(c) - ord("a"))
for i in range(n): st.update(i,f(s[i]))
q = int(input())
for _ in range(q):
    typ,x,y = input().split()
    if typ == "1":
        i,c = int(x)-1,y
        if s[i] == c: continue
        st.update(i,f(c))
        s[i] = c
    else:
        l,r = int(x)-1,int(y)
        print(bin(st.query(l,r)).count("1"))

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
input = lambda: sys.stdin.readline().rstrip()

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

# アルファベットごとに出現位置を記録
x=[[] for i in range(26)]
for i,j in enumerate(s):
    x[ord(j)-97].append(i)

# 終点対策
for i in range(26):
    x[i].append(float('inf'))


for i,j,k in q:
    if int(i)==1:
        if s[int(j)-1]!=k:
            v=s[int(j)-1]
            s[int(j)-1]=k
            # 変更前の要素を削除
            index=bisect.bisect_right(x[ord(v)-97], int(j)-1) - 1
            x[ord(v)-97].pop(index)
            # 変更後の要素を加える
            bisect.insort_right(x[ord(k)-97],int(j)-1)
    else:
        cnt=0
        j=int(j)-1
        k=int(k)-1
        for l in range(26):
            index=bisect.bisect_left(x[l],j)
            if x[l][index]<=k:
                cnt+=1


        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
f=input; n=int(f()); s=list(f())
d={chr(97+i):[0]*(n+1) for i in range(26)}
def bsum(k,i):
  s=0
  while i: s+=d[k][i]; i-=i&-i
  return s
def badd(k,i,x):
  while i<=n: d[k][i]+=x; i+=i&-i
for i in range(n): badd(s[i],i+1,1)
for i in range(int(f())):
  a,b,c=f().split(); b=int(b)-1
  if a>'1': print(sum(1 for k in d.keys() if bsum(k,int(c))-bsum(k,b)))
  else: badd(s[b],b+1,-1); s[b]=c; badd(c,b+1,1)