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:
from collections import Counter
n = int(input())
s = str(input())
q = int(input())
query = []
for _ in range(q):
    a,b,c = map(str, input().split())
    if a == '2':
        query.append([int(a),int(b),int(c)])
    else:
        query.append([int(a),int(b),c])
for x in query:
    if x[0] == 2:
        print(len(Counter(s[x[1]-1:x[2]]).most_common()))
    else:
        s = s[:x[1]-1] + x[2] + s[x[1]:]

Submission status: Time Limit Exceeded

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()
    S_list = []
    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)
        S_list.append(S_[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_list[i_q]
            if s_q != c_q:
                S_list[i_q] = c_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)
                if len(value) <= l_i:
                    continue
                if value[l_i] <= r_q:
                    cnt += 1
            print(cnt)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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()
    S_list = []
    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)
        S_list.append(S_[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_list[i_q]
            if s_q != c_q:
                S_list[i_q] = c_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: Time Limit Exceeded

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()
    S_list = []
    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)
        S_list.append(S_[i])
    for i in range(Q):
        query = LS()
        if query[0] == '1':
            i_q = int(query[1])
            c_q = query[2]
            s_q = S_list[i_q - 1]
            if s_q != c_q:
                S_list[i_q - 1] = c_q
                D[c_q].append(i_q - 1)
                D[c_q].sort()
                D[s_q].remove(i_q - 1)
        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: Time Limit Exceeded

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])
            c_q = query[2]
            s_q = S_[i_q - 1]
            if s_q != c_q:
                S_ = S_[:i_q - 1] + c_q + S_[i_q:]
                D[c_q].append(i_q - 1)
                D[c_q].sort()
                D[s_q].remove(i_q - 1)
        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: Time Limit Exceeded

Solution code:
class SegTree:
    """ segment tree with point modification and range product. """
    # # https://yukicoder.me/submissions/452850
    def __init__(self, N, data_f = min, data_unit=1<<30):
        self.N = N
        self.data_f = data_f
        self.data_unit = data_unit
        self.data = [self.data_unit] * (N + N)

    def build(self, raw_data):
        data = self.data
        f = self.data_f
        N = self.N
        data[N:] = raw_data[:]
        for i in range(N - 1, 0, -1):
            data[i] = f(data[i << 1], data[i << 1 | 1])

    def set_val(self, i, x):
        data = self.data
        f = self.data_f
        i += self.N
        data[i] = x
        while i > 1:
            data[i >> 1] = f(data[i], data[i ^ 1])
            i >>= 1

    def fold(self, L, R):
        """ compute for [L, R) """
        vL = vR = self.data_unit
        data = self.data
        f = self.data_f
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                vL = f(vL, data[L])
                L += 1
            if R & 1:
                R -= 1
                vR = f(data[R], vR)
            L >>= 1
            R >>= 1
        return f(vL, vR)
      
N=int(input())
S=input()
seg = SegTree(N,set.union,set())
S = [set(S[i]) for i in range(N)]
seg.build(S)
Q=int(input())
for i in range(Q):
  *q, = input().split()
  if q[0] == '1':
    i, c = q[1:]
    seg.set_val(int(i)-1,set(c))
  else:
    l,r = map(int,q[1:])
    print(len(seg.fold(l-1,r)))

Submission status: Time Limit Exceeded

Solution code:
"""
セグメント木で行きたいところだけど、集合の管理が必要になるため、時間がかかりすぎてしまう。
と思いきや、文字の種類は26種類しかないので、問題ない。
"""
def main():
    import sys
    input = sys.stdin.readline
    class segTree:
        def __init__(self,n):
            if bin(n).count("1") == 1:
                self.leaves = 2**(n.bit_length()-1)
            else:
                self.leaves = 2**n.bit_length()
            self.identity = set()
            self.tree = [set() for _ in range(self.leaves*2)]

        def update(self,i,x):
            i = i+self.leaves
            self.tree[i] = set([x])
            i >>= 1
            while i > 0:
                self.tree[i] = self.tree[i*2]|self.tree[i*2+1]
                i >>= 1

        def query(self,l,r):
            #[l:r)のクエリ結果を返す
            l = l + self.leaves
            r = r + self.leaves
            res = self.identity
            while l < r:
                if l&1:
                    res = res|self.tree[l]
                    l += 1
                if r&1:
                    r -= 1
                    res = res|self.tree[r]
                l >>= 1
                r >>= 1
            return len(res)


    N = int(input())
    S = list(input())
    Q = int(input())
    seg = segTree(N)
    for i in range(N):
        x = ord(S[i])-ord("a")
        seg.update(i,x)

    for _ in range(Q):
        q,a,b = input().split()
        if q == "1":
            a = int(a)
            b = ord(b)-ord("a")
            seg.update(a-1,b)
        else:
            a = int(a)
            b = int(b)
            print(seg.query(a-1,b))
main()

Submission status: Time Limit Exceeded

Solution code:
"""
セグメント木で行きたいところだけど、集合の管理が必要になるため、時間がかかりすぎてしまう。
と思いきや、文字の種類は26種類しかないので、問題ない。
"""
def main():
    import sys
    input = sys.stdin.readline
    class segTree:
        def __init__(self,n):
            if bin(n).count("1") == 1:
                self.leaves = 2**(n.bit_length()-1)
            else:
                self.leaves = 2**n.bit_length()
            self.identity = set()
            self.tree = [set()]*(self.leaves*2)

        def update(self,i,x):
            i = i+self.leaves
            self.tree[i] = set([x])
            i >>= 1
            while i > 0:
                self.tree[i] = self.tree[i*2]|self.tree[i*2+1]
                i >>= 1

        def query(self,l,r):
            #[l:r)のクエリ結果を返す
            l = l + self.leaves
            r = r + self.leaves
            res = self.identity
            while l < r:
                if l&1:
                    res = res|self.tree[l]
                    l += 1
                if r&1:
                    r -= 1
                    res = res|self.tree[r]
                l >>= 1
                r >>= 1
            return len(res)


    N = int(input())
    S = list(input())
    Q = int(input())
    seg = segTree(N)
    for i in range(N):
        x = ord(S[i])-ord("a")
        seg.update(i,x)

    for _ in range(Q):
        q,a,b = input().split()
        if q == "1":
            a = int(a)
            b = ord(b)-ord("a")
            seg.update(a-1,b)
        else:
            a = int(a)
            b = int(b)
            print(seg.query(a-1,b))
main()

Submission status: Time Limit Exceeded

Solution code:
"""
セグメント木で行きたいところだけど、集合の管理が必要になるため、時間がかかりすぎてしまう。
と思いきや、文字の種類は26種類しかないので、問題ない。
"""
def main():
    import sys
    input = sys.stdin.readline
    class segTree:
        def __init__(self,n):
            if bin(n).count("1") == 1:
                self.leaves = 2**(n.bit_length()-1)
            else:
                self.leaves = 2**n.bit_length()
            self.identity = set()
            self.tree = [set()]*(self.leaves*2)

        def update(self,i,x):
            i = i+self.leaves
            self.tree[i] = set(x)
            i >>= 1
            while i > 0:
                self.tree[i] = self.tree[i*2]|self.tree[i*2+1]
                i >>= 1

        def query(self,l,r):
            #[l:r)のクエリ結果を返す
            l = l + self.leaves
            r = r + self.leaves
            res = self.identity
            while l < r:
                if l&1:
                    res = res|self.tree[l]
                    l += 1
                if r&1:
                    r -= 1
                    res = res|self.tree[r]
                l >>= 1
                r >>= 1
            return len(res)


    N = int(input())
    S = list(input())
    Q = int(input())
    seg = segTree(N)
    for i in range(N):
        seg.update(i,S[i])

    for _ in range(Q):
        q,a,b = input().split()
        if q == "1":
            a = int(a)
            seg.update(a-1,b)
        else:
            a = int(a)
            b = int(b)
            print(seg.query(a-1,b))
main()

Submission status: Time Limit Exceeded

Solution code:
"""
セグメント木で行きたいところだけど、集合の管理が必要になるため、時間がかかりすぎてしまう。
と思いきや、文字の種類は26種類しかないので、問題ない。
"""
def main():
    import sys
    input = sys.stdin.readline
    class segTree:
        def __init__(self,n):
            if bin(n).count("1") == 1:
                self.leaves = 2**(n.bit_length()-1)
            else:
                self.leaves = 2**n.bit_length()
            self.identity = set()
            self.tree = [set()]*(self.leaves*2)

        def merge(self,x,y):
            #ここにマージ処理を書く
            return set(list(x)+list(y))

        def update(self,i,x):
            i = i+self.leaves
            self.tree[i] = set(x)
            i >>= 1
            while i > 0:
                self.tree[i] = self.merge(self.tree[i*2],self.tree[i*2+1])
                i >>= 1

        def query(self,l,r):
            #[l:r)のクエリ結果を返す
            l = l + self.leaves
            r = r + self.leaves
            res = self.identity
            while l < r:
                if l&1:
                    res = self.merge(res,self.tree[l])
                    l += 1
                if r&1:
                    r -= 1
                    res = self.merge(res,self.tree[r])
                l >>= 1
                r >>= 1
            return len(res)


    N = int(input())
    S = list(input())
    Q = int(input())
    seg = segTree(N)
    for i in range(N):
        seg.update(i,S[i])

    for _ in range(Q):
        q,a,b = input().split()
        if q == "1":
            a = int(a)
            seg.update(a-1,b)
        else:
            a = int(a)
            b = int(b)
            print(seg.query(a-1,b))
main()

Submission status: Time Limit Exceeded

Solution code:
"""
セグメント木で行きたいところだけど、集合の管理が必要になるため、時間がかかりすぎてしまう。
と思いきや、文字の種類は26種類しかないので、問題ない。
"""
def main():
    import sys
    input = sys.stdin.readline
    class segTree:
        def __init__(self,n):
            if bin(n).count("1") == 1:
                self.leaves = 2**(n.bit_length()-1)
            else:
                self.leaves = 2**n.bit_length()
            self.identity = set()
            self.tree = [set()]*(self.leaves*2)

        def merge(self,x,y):
            #ここにマージ処理を書く
            return x|y

        def update(self,i,x):
            i = i+self.leaves
            self.tree[i] = set(x)
            i >>= 1
            while i > 0:
                self.tree[i] = self.merge(self.tree[i*2],self.tree[i*2+1])
                i >>= 1

        def query(self,l,r):
            #[l:r)のクエリ結果を返す
            l = l + self.leaves
            r = r + self.leaves
            res = self.identity
            while l < r:
                if l&1:
                    res = self.merge(res,self.tree[l])
                    l += 1
                if r&1:
                    r -= 1
                    res = self.merge(res,self.tree[r])
                l >>= 1
                r >>= 1
            return len(res)


    N = int(input())
    S = list(input())
    Q = int(input())
    seg = segTree(N)
    for i in range(N):
        seg.update(i,S[i])

    for _ in range(Q):
        q,a,b = input().split()
        if q == "1":
            a = int(a)
            seg.update(a-1,b)
        else:
            a = int(a)
            b = int(b)
            print(seg.query(a-1,b))
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())
def NIJIGEN(H): return [list(input()) for i in range(H)]
input=sys.stdin.readline
N=INT()
S=input()
L=list(S)
Q=INT()
for i in range(Q):
  a,b,c=input().split()
  a=int(a)
  b=int(b)
  if a==1:
    L[b-1]=c
  else:
    c=int(c)
    print(len(set(L[b-1:c])))

Submission status: Time Limit Exceeded

Solution code:
# 本当はBITやセグメントツリーを用いた解法を使いたいところ...(理解不足)

import bisect
from collections import defaultdict

N = int(input())
# 書き換える時に文字列だと不便なのでリスト化しておく
S = list(input())
Q = int(input())

# setは順序を保証しない、setで管理するとクエリ2で（リスト化した後に）ソートする必要がある
# 最初からlistで管理して、クエリ1ではソート済になるように挿入する
dict = defaultdict(list)
for i in range(N):
    dict[S[i]].append(i)

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:
            # クエリ2が飛んできた時に毎回ソートしていては間に合わない
            # クエリ1の時点でソート済にしておく
            # 二分探索の際、同じ数字が既にあることはないので、leftでもrightでも良い
            dict[S[b]].remove(b)
            idx = bisect.bisect(dict[c], b)
            dict[c].insert(idx, b)
            # 文字列の書き換え
            S[b] = c

    elif a == 2:
        b = int(b) - 1
        c = int(c) - 1
        # 文字が何種類あるか
        char_cnt = 0
        for key, value in dict.items():
            # left,rightを指定する必要がある
            x1 = bisect.bisect_left(value, b)
            x2 = bisect.bisect_right(value, c)
            if x2 - x1 > 0:
                char_cnt += 1
        ans.append(char_cnt)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import defaultdict

N = int(input())
# 書き換える時に文字列だと不便なのでリスト化しておく
S = list(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.bisect_left(dict[c], b)
            dict[c].insert(idx, b)
            S[b] = c

    elif a == 2:
        b = int(b) - 1
        c = int(c) - 1
        char_n = 0
        for key, value in dict.items():
            value.sort()
            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: Time Limit Exceeded

Solution code:
# test!!!!!!!!!!!

from bisect import bisect_left, bisect_right

N = int(input())

S = list(input())

Q = int(input())

# {"a":[], "b":[], ..., "z":[]}
dict = {chr(ord('a') + i): [] for i in range(26)}

for i in range(N):
    dict[S[i]].append(i)

ans = []

for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1])-1, query[2]
        now = S[i]
        # if now == x:
        #     continue
        dict[now].remove(i)
        next_i = bisect_left(dict[x], i)
        dict[x].insert(next_i, i)
        S[i] = x
    else:
        start, end = int(query[1])-1, int(query[2])-1
        tmp_cout = 0
        for alf_array in dict.values():
            if len(alf_array) == 0:
                continue
            ss = bisect_left(alf_array, start)
            gg = bisect_right(alf_array, end)
            if gg- ss > 0:
                tmp_cout += 1
        ans.append(tmp_cout)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
# test!!!!!!!!!!

from bisect import bisect_left, bisect_right

N = int(input())

S = list(input())

Q = int(input())

memo = {chr(ord('a') + i): [] for i in range(26)}

for key,val in enumerate(S):
    memo[val].append(key)

for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1])-1, query[2]
        now = S[i]
        if now == x:
            continue
        memo[now].remove(i)
        next_i = bisect_left(memo[x], i)
        memo[x].insert(next_i, i)
        S[i] = x
    else:
        start, end = int(query[1])-1, int(query[2])-1
        tmp_cout = 0
        for alf_array in memo.values():
            if len(alf_array) == 0:
                continue
            ss = bisect_left(alf_array, start)
            gg = bisect_right(alf_array, end)
            if gg- ss > 0:
                tmp_cout += 1
        print(tmp_cout)

Submission status: Time Limit Exceeded

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

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

ans = []

for _ in range(Q):
    a, b, c = input().split()
    a = int(a)
    if a == 1:
        b = int(b) - 1
        for key in dict.keys():
            if b in dict[key]:
                dict[key].discard(b)
                dict[c].add(b)
                break
    elif a == 2:
        b = int(b) - 1
        c = int(c) - 1
        char_n = 0
        for key, value in dict.items():
            value = list(value)
            value.sort()
            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: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

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

    def get_sum(self, i):
        i += 1
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i & -i
        return x

    # Return sum for [l, r)
    def get_sum_range(self, l, r):
        return self.get_sum(r - 1) - self.get_sum(l - 1)


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

    S = list(S)
    base = ord('a')

    tree = [BIT(N) for _ in range(26)]
    for i, c in enumerate(S):
        tree[ord(c) - base].add(i)

    ans = []
    for _ in range(Q):
        n, a, b = readline().split()
        if n == '1':
            i = int(a) - 1
            if S[i] != b:
                tree[ord(S[i]) - base].add(i, -1)
                tree[ord(b) - base].add(i, 1)
                S[i] = b
        else:
            l, r = int(a) - 1, int(b)
            tmp = 0
            for i in range(26):
                if tree[i].get_sum_range(l, r) > 0:
                    tmp += 1
            ans.append(tmp)

    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT():
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

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

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

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

n = int(input())
S = input()
q = int(input())
Query = [input().split() for _ in range(q)]

bits = [BIT(n) for i in range(26)]
s = []
for i,c in enumerate(S):
    bits[ord(c) - ord("a")].add(i,1)
    s.append(c)

for q_type,fr,to in Query:
    if q_type == "1":
        i = int(fr)-1
        bits[ord(s[i]) - ord("a")].add(i,-1)
        bits[ord(to) - ord("a")].add(i,1)
        s[i] = to
    else:
        l,r = int(fr)-1,int(to)
        tmp = 0
        for i in range(26):
            if bits[i].sum(l,r):
                tmp += 1
        print(tmp)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

N = int(input())
S = list(input().strip())
Q = int(input())

# アルファベットごとの累積和
acum = [[0 for _ in range(N+1)] for _ in range(26)]
for i in range(N):
    for j in range(26):
        acum[j][i+1] = acum[j][i]
    # print(S[i])
    n = ord(S[i]) - ord("a")
    # print(n)
    acum[n][i+1] += 1

for _ in range(Q):
    query = input()
    if query[0] == "1":
        _, i, c = query.strip().split()
        i = int(i) - 1
        n = ord(c) - ord("a")
        # 同じ文字の場合は何もしない
        if S[i] == c:
            continue

        n_org = ord(S[i]) - ord("a")
        # print("query", c, "i", i, "n", n)
        for k in range(i+1, N+1):
            acum[n][k] += 1
            acum[n_org][k] -= 1
        # print(acum[n])
        S[i] = c
    else:
        _, l, r = map(int, query.split())
        ans = 0
        for i in range(26):
            if acum[i][r] - acum[i][l-1] > 0:
                ans += 1
        print(ans)
# print(acum)

Submission status: Time Limit Exceeded

Solution code:
def update(i,a,x):
    T[i][2**n+a-1] = x
    k = 2**n+a-1
    k = k//2
    while k>0:
        T[i][k] += 2*x-1
        k = k//2
def find(i,l,r,k):
    x = C[k][0]
    y = C[k][1]
    if y<=l or x>=r:
        return 0
    if x>=l and y<=r:
        return T[i][k]
    return find(i,l,r,2*k)+find(i,l,r,2*k+1)
    
N = int(input())
S = list(input().strip())
S.insert(0,0)
n = 0
while 2**n<N:
    n += 1
T = {i:[0 for _ in range(2**(n+1))] for i in range(97,123)}
C = [0 for _ in range(2**(n+1))]
C[1] = (1,2**n+1)
for j in range(2,2**(n+1)):
    d = C[j//2][1]-C[j//2][0]
    if j%2==0:
        C[j] = (C[j//2][0],C[j//2][0]+d//2)
    else:
        C[j] = (C[j//2][0]+d//2,C[j//2][1])
for i in range(97,123):
    for j in range(1,N+1):
        if S[j]==chr(i):
            update(i,j,1)
Q = int(input())
for _ in range(Q):
    q,x,y = list(input().split())
    if q=="1":
        x = int(x)
        y = ord(y)
        z = ord(S[x])
        if S[x]!=chr(y):
            S[x] = chr(y)
            update(z,x,0)
            update(y,x,1)
    else:
        x = int(x)
        y = int(y)
        cnt = 0
        for i in range(97,123):
            if find(i,x,y+1,1)>0:
                cnt += 1
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def update(i,a,x):
    T[i][2**n+a-1] = x
    k = 2**n+a-1
    k = k//2
    while k>0:
        T[i][k] += 2*x-1
        k = k//2
def find(i,l,r,k):
    x = C[k][0]
    y = C[k][1]
    if y<=l or x>=r:
        return 0
    if x>=l and y<=r:
        return T[i][k]
    return find(i,l,r,2*k)+find(i,l,r,2*k+1)
    
N = int(input())
S = list(input().strip())
S.insert(0,0)
n = 0
while 2**n<N:
    n += 1
T = {i:[0 for _ in range(2**(n+1))] for i in range(97,123)}
C = [0 for _ in range(2**(n+1))]
C[1] = (1,2**n+1)
for j in range(2,2**(n+1)):
    d = C[j//2][1]-C[j//2][0]
    if j%2==0:
        C[j] = (C[j//2][0],C[j//2][0]+d//2)
    else:
        C[j] = (C[j//2][0]+d//2,C[j//2][1])
for i in range(97,123):
    A = []
    for j in range(1,N+1):
        if S[j]==chr(i):
            A.append(j)
    for a in A:
        update(i,a,1)
Q = int(input())
for _ in range(Q):
    q,x,y = list(input().split())
    if q=="1":
        x = int(x)
        y = ord(y)
        z = ord(S[x])
        if S[x]!=chr(y):
            S[x] = chr(y)
            update(z,x,0)
            update(y,x,1)
    else:
        x = int(x)
        y = int(y)
        cnt = 0
        for i in range(97,123):
            if find(i,x,y+1,1)>0:
                cnt += 1
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)

# Segment Tree
class SegmentTree:
    def __init__(self, N):
        self.size = 2 ** (N-1).bit_length()# 要素数を超える最小の2べき
        self.dat = [0] * (2*self.size)
    
    def update(self,i,x):# i番目の文字がxになる
        i += self.size
        self.dat[i] = 1 << ord(x)-ord('a')
        while i > 0:# 上まで更新していく
            i >>= 1
            self.dat[i] = self.dat[i*2] | self.dat[i*2+1]

    def fold(self, l, r):
        l += self.size
        r += self.size
        vl = 0
        vr = 0
        while l < r:
            if l & 1:
                vl |= self.dat[l]
                l += 1
            if r & 1:
                r -= 1
                vr |= self.dat[r]
            l >>= 1
            r >>= 1
        # print(bin(vl | vr))
        return bin(vl | vr).count('1')

def main():
    N = int(input())
    S = list(input())
    sg = SegmentTree(N)
    for i in range(N):
        sg.update(i,S[i])
    # print(sg.dat)
    
    Q = int(input())
    for _ in range(Q):
        Query = input().split()
        if Query[0] == '1':
            sg.update(int(Query[1])-1, Query[2])
            # print(sg.dat)
        else:
            res = sg.fold(int(Query[1])-1, int(Query[2]))
            print(res)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

N = int(input())

S = list(input())

Q = int(input())

memo = [[]*N for _ in range(26)]

for key,val in enumerate(S):
    ch = ord(val)-97
    memo[ch].append(key)

for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1])-1, query[2]
        now = S[i]
        now_cn = ord(now)-97
        nex_ch = ord(x)-97
        if nex_ch == x:
            continue
        memo[now_cn].remove(i)
        next_i = bisect_left(memo[nex_ch], i)
        memo[nex_ch].insert(next_i, i)
        S[i] = x
    else:
        start, end = int(query[1])-1, int(query[2])-1
        tmp_cout = 0
        for alf_array in memo:
            if len(alf_array) == 0:
                continue
            ss = bisect_left(alf_array, start)
            gg = bisect_right(alf_array, end)
            if gg- ss > 0:
                tmp_cout += 1
        print(tmp_cout)