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:
#!/usr/bin/env python3

class Bit:
    # Binary Indexed Tree
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i + 1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, i) の要素の総和を返す
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        # 足し算と引き算にはaddを使うべき
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])

(n,), (s,), _, *q = map(str.split, open(0))
*s, = s
BIT = [Bit(int(n)) for _ in [0] * 26]
for e, t in enumerate(s):
    BIT[ord(t) - 97].add(e, 1)
for a, b, c in q:
    if a == "1":
        i = int(b)
        BIT[ord(s[i - 1]) - 97].add(i - 1, -1)
        s[i - 1] = c
        BIT[ord(c) - 97].add(i - 1, 1)
    else:
        l, r = int(b), int(c)
        print(sum(BIT[i].sum(r) - BIT[i].sum(l - 1) > 0 for i in range(26)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
BIT=[[0]*n for i in range(26)]
w=[ord(x)-ord("a") for x in input()]
for i in range(n):
	k=i+1
	while k<=n:
		BIT[w[i]][k-1]+=1
		k=k+(k&-k)
q=int(input())
for i in range(q):
	a,b,c=input().split()
	if a=="1":
		k=int(b)
		while k<=n:
			BIT[ord(c)-ord("a")][k-1]+=1
			k=k+(k&-k)
		k=int(b)
		while k<=n:
			BIT[w[int(b)-1]][k-1]-=1
			k=k+(k&-k)	
		w[int(b)-1]=ord(c)-ord("a")
	else:
		b=int(b);c=int(c)
		ans=0
		for i in range(26):
			cnt=0
			k=c
			while k!=0:
				cnt+=BIT[i][k-1]
				k=k-(k&-k)
			k=b-1
			while k!=0:
				cnt-=BIT[i][k-1]
				k=k-(k&-k)
			if cnt>0:
				ans+=1
		print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=[s for s in input()]
for _ in range(int(input())):
  a,b,c=input().split()
  a,b=int(a),int(b)
  if a==1:s[b-1]=c
  else:print(len(set(s[b-1:int(c)])))

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import or_

input = sys.stdin.readline


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

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

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

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

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

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

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


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

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

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

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


class SegmentTree:
    def __init__(self, N, X):
        self.N = N
        self.func = lambda x, y: x | y
        self.__build(X)

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

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

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

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

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

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


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

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

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

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

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

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

for i, s in enumerate(S):
    D[s].append(i)

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

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

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

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

            if ri - li > 0:
                ans += 1

        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
# from collections import defaultdict

N = int(sys.stdin.readline().rstrip())
S1 = sys.stdin.readline().rstrip()
Q = int(sys.stdin.readline().rstrip())

BIT = [[0 for _ in range(N + 1)] for _ in range(26)]  # 初期化（アルファベット分）
alpha = {"a": 0, "b": 1, "c": 2, "d": 3, "e": 4,
         "f": 5, "g": 6, "h": 7, "i": 8, "j": 9,
         "k": 10, "l": 11, "m": 12, "n": 13, "o": 14,
         "p": 15, "q": 16, "r": 17, "s": 18, "t": 19,
         "u": 20, "v": 21, "w": 22, "x": 23, "y": 24, "z": 25}

S = []
for i in range(N):
    S.append(alpha[S1[i]])


# 初期化
def initialize():
    global BIT, S, N
    for j in range(N):
        c = S[j]  # 文字切り出し／index に変換
        i = j + 1
        while i <= N:
            BIT[c][i] += 1
            i += (i & -i)

# 文字の交換


def change(i, before, after):

    global BIT, N
    while i <= N:
        BIT[before][i] -= 1
        BIT[after][i] += 1
        i += (i & -i)


# 文字数の取り出し
def sum(i, c):

    global BIT

    _sum = 0
    while i > 0:
        _sum += BIT[c][i]
        i -= (i & -i)

    return _sum


initialize()

for _ in range(Q):
    q, x, y = sys.stdin.readline().rstrip().split()
    if q == "1":
        i = int(x)
        bc = S[i - 1]
        ac = alpha[y]
        S[i - 1] = ac
        change(i, bc, ac)

    else:
        x = int(x)
        y = int(y)
        count = 0
        for c in range(26):
            if sum(y, c) != sum(x - 1, c):
                count += 1
        print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
# from collections import defaultdict

N = int(sys.stdin.readline().rstrip())
S = sys.stdin.readline().rstrip()
Q = int(sys.stdin.readline().rstrip())

BIT = [[0 for _ in range(N + 1)] for _ in range(26)]  # 初期化（アルファベット分）
alpha = {"a": 0, "b": 1, "c": 2, "d": 3, "e": 4,
         "f": 5, "g": 6, "h": 7, "i": 8, "j": 9,
         "k": 10, "l": 11, "m": 12, "n": 13, "o": 14,
         "p": 15, "q": 16, "r": 17, "s": 18, "t": 19,
         "u": 20, "v": 21, "w": 22, "x": 23, "y": 24, "z": 25}


# 初期化
def initialize():
    global BIT, S, N
    for j in range(N):
        c = alpha[S[j]]  # 文字切り出し／index に変換
        i = j + 1
        while i <= N:
            BIT[c][i] += 1
            i += (i & -i)


def identify(i):
    # i文字目を、変化点があった文字として探索する
    for c in range(26):
        if sum(i, c) != sum(i - 1, c):
            return c


# 文字の交換
def change(i, before, after):

    global BIT, N
    while i <= N:
        BIT[before][i] -= 1
        BIT[after][i] += 1
        i += (i & -i)


# 文字数の取り出し
def sum(i, c):

    global BIT

    _sum = 0
    while i > 0:
        _sum += BIT[c][i]
        i -= (i & -i)

    return _sum


initialize()

for _ in range(Q):
    q, x, y = sys.stdin.readline().rstrip().split()
    if q == "1":
        i = int(x)
        ac = alpha[y]
        bc = identify(i)
        change(i, bc, ac)

    else:
        x = int(x)
        y = int(y)
        count = 0
        for c in range(26):
            if sum(y, c) != sum(x - 1, c):
                count += 1
        print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

N = int(sys.stdin.readline().rstrip())
S = sys.stdin.readline().rstrip()
Q = int(sys.stdin.readline().rstrip())


for _ in range(Q):
    q, x, y = sys.stdin.readline().rstrip().split()
    if q == "1":
        x = int(x)
        if x == 1:
            S = y + S[1:]
        elif x == N:
            S = S[:-1] + y
        else:
            S = S[:x - 1] + y + S[x:]
    else:
        print(len(Counter(S[int(x) - 1:int(y)]).keys()))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, lst, op, e):
        self.n = len(lst)
        self.N = 1 << ((self.n - 1).bit_length())
        self.op = op # operation
        self.e = e # identity element
        self.v = self._build(lst) # self.v is set to be 1-indexed for simplicity
        
    def _build(self, lst):
        # construction of a tree
        # total 2 * self.N elements (tree[0] is not used)
        tree = [self.e] * (self.N) + lst + [self.e] * (self.N - self.n)
        for i in range(self.N - 1, 0, -1): tree[i] = self.op(tree[i << 1], tree[(i << 1)|1])
        return tree
    
    def __getitem__(self, i):
        return self.v[i + self.N]
    
    # update a_i to be x 
    def update(self, i, x):
        v, op = self.v, self.op
        i += self.N
        v[i] = x
        while i > 0:
            i >>= 1 # move to parent
            v[i] = op(v[i << 1], v[(i << 1)|1])
    
    # returns answer for the query interval [l, r)
    def fold(self, l, r):
        N, e, v, op = self.N, self.e, self.v, self.op
        left = l + N; right = r + N
        L = R = e
        while left < right:
            if left & 1: # self.v[left] is the right child
                L = op(L, v[left])
                left += 1
            if right & 1: # self.v[right-1] is the left child
                right -= 1
                R = op(v[right], R)
            left >>= 1; right >>= 1
        return op(L, R)

def wa(set1, set2):
    return set1 | set2

n = int(input())
s = input()
lst = []
for i in range(n):
    lst.append(set([s[i]]))

st = SegmentTree(lst, wa, set([]))

ans = []
q = int(input())
for i in range(q):
    que = input()
    if que[0] == '1':
        kind, i, c = que.split()
        i = int(i) - 1
        st.update(i, set([c]))
    else:
        kind, l, r = map(int, que.split())
        l -= 1
        ans.append(len(st.fold(l, r)))

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Jul 31 20:31:15 2020

@author: teppe
"""

import copy

def init(init_val):
    for j in range(26):
        #set_val
        for i in range(n):
            if init_val[i] == j:
                seg[j][i+num-1] = 1
        #built
        for i in range(num-2,-1,-1):
            seg[j][i] = seg[j][2*i+1] | seg[j][2*i+2]


def update(k, cs):
    ls = s[k]
    if ls == cs:
        return
    k += num-1
    seg[cs][k] = 1
    seg[ls][k] = 0
    while k:
        k = (k-1)//2
        seg[ls][k] = seg[ls][k*2+1] | seg[ls][k*2+2]
        seg[cs][k] = seg[cs][k*2+1] | seg[cs][k*2+2]


def query(pp, qq): # pからq-1までの最大値
    pp += num-1
    qq += num-2
    total = 0
    for j in range(26):
        p = copy.deepcopy(pp)
        q = copy.deepcopy(qq)
        res = 0
        while q - p > 1:
            if res == 1:
                break
            if p&1 == 0:
                res = res | seg[j][p]
            if q&1 == 1:
                res = res | seg[j][q]
                q -= 1
            p = p//2
            q = (q-1)//2
        if q - p > 1:
            total += res
            continue
        if p == q:
            res = res | seg[j][p]
        else:
            res = res | seg[j][p] | seg[j][q]
        total += res
    return total


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

for i in range(n):
    s[i] = ord(s[i]) - 97
#num:n以上の最小の2のべき乗
num = 2**(n-1).bit_length()
seg = [[0]*(2*num) for i in range(26)]
init(s)
for i in range(q):
    cq = list(input().split())
    if cq[0] == '1':
        cn, cs = int(cq[1]) - 1, ord(cq[2]) - 97
        update(cn, cs)
        s[cn] = cs
    if cq[0] == '2':
        p, q = int(cq[1]) - 1, int(cq[2])
        print(query(p, q))

Submission status: Time Limit Exceeded

Solution code:
import copy

def init(init_val):
    for j in range(26):
        #set_val
        for i in range(n):
            if init_val[i] == j:
                seg[j][i+num-1] = 1
        #built
        for i in range(num-2,-1,-1):
            seg[j][i] = max(seg[j][2*i+1], seg[j][2*i+2])


def update(k, cs):
    ls = s[k]
    if ls == cs:
        return
    k += num-1
    seg[cs][k] = 1
    seg[ls][k] = 0
    while k:
        k = (k-1)//2
        seg[ls][k] = max(seg[ls][k*2+1], seg[ls][k*2+2])
        seg[cs][k] = max(seg[cs][k*2+1], seg[cs][k*2+2])


def query(pp, qq): # pからq-1までの最大値
    pp += num-1
    qq += num-2
    total = 0
    for j in range(26):
        p = copy.deepcopy(pp)
        q = copy.deepcopy(qq)
        res = 0
        while q - p > 1:
            if res == 1:
                break
            if p&1 == 0:
                res = max(res, seg[j][p])
            if q&1 == 1:
                res = max(res, seg[j][q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if q - p > 1:
            total += res
            continue
        if p == q:
            res = max(res, seg[j][p])
        else:
            res = max(max(res,seg[j][p]),seg[j][q])
        total += res
    return total


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

for i in range(n):
    s[i] = ord(s[i]) - 97
#num:n以上の最小の2のべき乗
num = 2**(n-1).bit_length()
seg = [[0]*(2*num) for i in range(26)]
init(s)
for i in range(q):
    cq = list(input().split())
    if cq[0] == '1':
        cn, cs = int(cq[1]) - 1, ord(cq[2]) - 97
        update(cn, cs)
        s[cn] = cs
    if cq[0] == '2':
        p, q = int(cq[1]) - 1, int(cq[2])
        print(query(p, q))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left,bisect_right

TO_ACII = 97

N = int(input())
S = ["0"] + list(input())
Q = int(input())

ABC = [[]for i in range(0,26,1)]#該当文字a:0 b:1 ...z:26 が何文字目に出てきたかを保持する配列

for i in range(1,N+1,1):
    ABC[ord(S[i])-TO_ACII].append(i)

ans = []
for i in range(0,Q,1):
    q = list(input().split())
    if q[0]=="1":#文字変更
        changed = S[int(q[1])]
        ABC[ord(changed)-TO_ACII].pop(bisect_left(ABC[ord(changed)-TO_ACII],int(q[1])))
        ABC[ord(q[2])-TO_ACII].insert(bisect_left(ABC[ord(q[2])-TO_ACII],int(q[1])),int(q[1]))
        S[int(q[1])]=q[2]
    else:
        tmpans = 0
        for i in range(0,26,1):

            if bisect_right(ABC[i],int(q[1])-1)<len(ABC[i]) and int(q[2]) >= ABC[i][bisect_right(ABC[i],int(q[1])-1)]:
                tmpans+=1
        ans.append(tmpans)

for i in range(0,len(ans),1):
    print(ans[i])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
class BIT:
  from operator import add, sub, mul, floordiv
  X_unit = 0
  X_f = add
  X_f_rev = sub

  def __init__(self, seq):
    N = len(seq)
    self.N = N
    self.X = seq[:]
    for i in range(self.N):
      j = i + ((i+1) & -(i+1))
      if j < self.N:
        self.X[j] = self.X_f(self.X[i], self.X[j])
  
  def set_val(self, i, x):
    while(i < self.N):
      self.X[i] = self.X_f(self.X[i], x)
      i += (i+1) & -(i+1)

  def cum_val(self, i):
    res = self.X_unit
    while(i > -1):
      res = self.X_f(res, self.X[i])
      i -= (i+1) & -(i+1)
    return res
  
  #区間[L, R)
  def fold(self, L, R):
    return self.X_f_rev(self.cum_val(R-1), self.cum_val(L-1))
  
  def bisect_left(self, w):
    if w > self.cum_val(self.N - 1):
      return self.N
    elif self.N == 2:
      return 1
    n = 2**((self.N - 1).bit_length() - 1)
    res = 0
    while(n):
      if res + n - 1 > self.N - 1:
        n //= 2
        continue
      if w <= self.X[res + n - 1]:
        n //= 2
      else:
        w -= self.X[res + n - 1]
        res += n
        n //= 2
    return res
  
  def bisect_right(self, w):
    if w >= self.cum_val(self.N - 1):
      return self.N
    elif self.N == 2:
      return 1
    n = 2**((self.N - 1).bit_length() - 1)
    res = 0
    while(n):
      if res + n - 1 > self.N - 1:
        n //= 2
        continue
      if w < self.X[res + n - 1]:
        n //= 2
      else:
        w -= self.X[res + n - 1]
        res += n
        n //= 2
    return res
  
  def lower_bound(self, w):
    ans = self.bisect_right(self.cum_val(w))
    if ans == self.N:
      return -1
    else:
      return ans
  
  def upper_bound(self, w):
    ans = self.bisect_left(self.cum_val(w-1))
    return ans

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

L = [BIT([0]*N) for _ in range(26)]

for i in range(N):
  L[ord(S[i])-97].set_val(i, 1)

Q = int(input())

for _ in range(Q):
  q, a, b = input().split()
  if q == "1":
    a = int(a)
    L[ord(S[a-1])-97].set_val(a-1, -1)
    L[ord(b)-97].set_val(a-1, 1)
    S[a-1] = b
  else:
    a, b = int(a), int(b)
    ans = 0
    for i in range(26):
      if L[i].fold(a-1, b) >= 1:
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=[*input()]
q=int(input())
# BIT
B={chr(97+i):[0]*(n+1) for i in range(26)}
def bsum(c,i):
  s=0
  while i:
    s+=B[c][i]
    i-=i&-i
  return s
def badd(c,i,x):
  while i<=n:
    B[c][i]+=x
    i+=i&-i
for i,c in enumerate(s):
  badd(c,i+1,1)
for _ in range(q):
  x,y,z=input().split()
  y=int(y)-1
  if x=='1':
    badd(s[y],y+1,-1)
    s[y]=z
    badd(z,y+1,1)
  else:
    print(sum(bsum(c,int(z))-bsum(c,y)>0 for c in B))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q = int(input())
al=[[0 for i in range(26)]]
for i in range(n):
    al.append(al[-1][:])
    al[-1][ord(s[i]) - ord("a")] += 1
for i in range(q):
    x , y , z = input().split()
    if int(x) == 1:
        for j in range(int(y),n+1):
            al[j][ord(s[int(y)-1]) - ord("a")] -= 1
            al[j][ord(z) - ord("a")] += 1
        s[int(y)-1] = z
    elif int(x) == 2:
        cou = 0
        for j in range(26):
            if al[int(z)][j] - al[int(y)-1][j] >= 1:
                cou += 1
        print(cou)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, lst, op, e):
        self.n = len(lst)
        self.N = 1 << ((self.n - 1).bit_length())
        self.op = op # operation
        self.e = e # identity element
        self.v = self._build(lst) # self.v is set to be 1-indexed for simplicity
        
    def _build(self, lst):
        # construction of a tree
        # total 2 * self.N elements (tree[0] is not used)
        tree = [self.e] * (self.N) + lst + [self.e] * (self.N - self.n)
        for i in range(self.N - 1, 0, -1): tree[i] = self.op(tree[i << 1], tree[(i << 1)|1])
        return tree
    
    def __getitem__(self, i):
        return self.v[i + self.N]
    
    # update a_i to be x 
    def update(self, i, x):
        v, op = self.v, self.op
        i += self.N
        v[i] = x
        while i > 0:
            i >>= 1 # move to parent
            v[i] = op(v[i << 1], v[(i << 1)|1])
    
    # returns answer for the query interval [l, r)
    def fold(self, l, r):
        N, e, v, op = self.N, self.e, self.v, self.op
        left = l + N; right = r + N
        L = R = e
        while left < right:
            if left & 1: # self.v[left] is the right child
                L = op(L, v[left])
                left += 1
            if right & 1: # self.v[right-1] is the left child
                right -= 1
                R = op(v[right], R)
            left >>= 1; right >>= 1
        return op(L, R)

def lcm(x, y):
    mini, maxi = min(x, y), max(x, y)
    if maxi%mini == 0:
        return maxi
    else:
        return mini * maxi

dic = {'a':2, 'b':3, 'c':5, 'd':7, 'e':11, 'f':13, 'g':17, 'h':19, 'i':23, 'j':29, 'k':31, 'l':37, 'm':41, 'n':43, 'o':47, 'p':53, 'q':59, 'r':61, 's':67, 't':71, 'u':73, 'v':79, 'w':83, 'x':89, 'y':97, 'z':101}

n = int(input())
s = input()
lst = []
for i in range(n):
    lst.append(dic[s[i]])

st = SegmentTree(lst, lcm, 1)

ans = []
q = int(input())
for i in range(q):
    que = input()
    if que[0] == '1':
        kind, i, c = que.split()
        i = int(i) - 1
        st.update(i, dic[c])
    else:
        kind, l, r = map(int, que.split())
        l -= 1
        num = st.fold(l, r)
        temp = 0
        for prime in dic.values():
            if num%prime == 0:
                temp += 1
        ans.append(temp)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
class BIT:

    def __init__(self, N):
        # NOTE: 1-indexed
        self.N = N
        self.data = [0] * (N + 1)

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

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


def c2n(c):
    return ord(c) - ord('a')


def main():
    N = int(input())
    S = input()
    char_list = list(S)
    trees = [BIT(N) for _ in range(26)]
    for i, c in enumerate(S):
        trees[c2n(c)].update(i + 1, 1)
    Q = int(input())
    ans = list()
    for _ in range(Q):
        query = input().split()
        if query[0] == '1':
            _, i, c = query
            i = int(i) - 1
            before_c = char_list[i]
            char_list[i] = c
            trees[c2n(before_c)].update(i + 1, - 1)
            trees[c2n(c)].update(i + 1, 1)
        else:  # type '2'
            _, left, right = query
            left, right = int(left) - 1, int(right) - 1
            cnt = 0
            for i in range(26):
                n = trees[i].sum(right + 1) - trees[i].sum(left)
                if n > 0:
                    cnt += 1
            ans.append(cnt)
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
s = input()
S = []
for k in range(N):
  S.append(s[k])
Q = int(input())
a = ord('a')
alpha = [[0 for _ in range(26)] for _ in range(N)]
alpha[0][ord(S[0])-a] = 1
for k in range(1, N):
  alpha[k] = [] + alpha[k-1]
  alpha[k][ord(S[k])-a] += 1
change = set()
substitute = []
inp = []
lastapp = [-1 for _ in range(N)]
for k in range(Q):
  s,t,u = map(str, input().split())
  inp.append([s,t,u])
  if s == '2':
    l = int(t) -1
    r = int(u) -1
    change.add(max(l-1, 0))
    change.add(r)
    lastapp[r] = k
    lastapp[max(l-1, 0)] = k

change = list(change)
for k in range(len(inp)):
  if inp[k][0] == '1':
    j = 0
    while j < len(change):
      if int(inp[k][1]) -1 <= change[j]:
        alpha[change[j]][ord(inp[k][2]) -a] += 1
        alpha[change[j]][ord(S[int(inp[k][1])-1]) - a] -= 1
      if lastapp[change[j]] < k:
        del change[j]
        j -= 1
      j += 1
    S[int(inp[k][1])-1] = inp[k][2]
  
  else:
    l = int(inp[k][1]) -1
    r = int(inp[k][2]) -1
    ans = 0
    if l == 0:
      for k in range(26):
        if alpha[r][k] >0:
          ans += 1
    else:
      for k in range(26):
        if alpha[r][k] - alpha[l-1][k] > 0:
          ans += 1
    print(ans)