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:
N = int(input())
S = input()
Q = int(input())

def type1(S,i,w):
    S_list = list(S)
    S_list[i-1] = w
    S = ''.join(S_list)
    return S
    
def type2(S,l,r):
    S_list = list(S)
    print(len(set(S_list[l-1:r])))
    

for i in range(Q):
    a,b,c = input().split()
    if a == '1':
        S = type1(S,int(b),c)
    else:
        type2(S,int(b),int(c))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
s = []
A = [[] for i in range(26)]
for i in range(N):
    x = S[i]
    s.append(x)
    n = ord(x) - 97
    A[n].append(i)
Q = int(input())
for i in range(Q):
    q,a,b = map(str,input().split())
    q = int(q)
    a = int(a)
    a -= 1
    if q == 1:
        x = s[a]
        s[a] = b
        A[ord(x)-97].remove(a)
        A[ord(b)-97].append(a)
        A[ord(b)-97].sort()
    if q == 2:
        ans = 0
        b = int(b)
        b -= 1
        for i in range(26):
            B = A[i]
            import bisect
            p = bisect.bisect_left(B,a)
            q = bisect.bisect_right(B,b)
            if q - p > 0:
                ans += 1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
Q = int(input())
for i in range(Q):
  L_i = input().rstrip().split(' ')
  if L_i[0] == "1":
    S[int(L_i[1])-1] = L_i[2]
  elif L_i[0] == "2":
    A = set(S[int(L_i[1])-1:int(L_i[2])])
    print(len(A))

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np


class SegTree:
    def __init__(self, n, s):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [np.zeros(26, dtype=np.int32) for _ in range(n2 << 1)]

        for i, c in enumerate(s):
            x = ord(c) - 97
            i += self.offset
            self.tree[i][x] = 1
        for i in range(self.offset - 1, 0, -1):
            self.tree[i] = self.tree[i << 1] + self.tree[(i << 1) + 1]

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        y = self.tree[i].argmax()
        if x == y:
            return
        upd = np.zeros(26, dtype=np.int32)
        upd[x] = 1
        upd[y] = -1
        while i > 1:
            self.tree[i] += upd
            i >>= 1

    def get_types(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = np.zeros(26, dtype=np.int32)

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result += self.tree[r - 1]
            if l & 1:
                result += self.tree[l]
                l += 1
            l >>= 1
            r >>= 1

        return (result > 0).sum()


n = int(input())
s = input()
st = SegTree(n, s)
q = int(input())
ans = []
for line in sys.stdin:
    i, j, k = line.rstrip().split()
    if i == '1':
        j = int(j) - 1
        k = ord(k) - 97
        st.update(j, k)
    else:
        l = int(j) - 1
        r = int(k)
        ans.append(st.get_types(l, r))
print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()

Q = int(input())

for i in range(Q):
  order = list(map(str, input().split()))

  if int(order[0]) == 1:
    iq, cq = int(order[1])-1, order[2]
    s = s[:iq] + cq + s[iq+1:]
  else:
    lq, rq = int(order[1])-1, int(order[2])-1
    substr = s[lq:rq+1]
    print(len(set(substr)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
Q = int(input())

for i in range(Q):
  hoge = input().split()
  if hoge[0] == "1":
    S[int(hoge[1]) - 1] = hoge[2]
  else:
    print(len(set(S[int(hoge[1]) - 1:int(hoge[2])])))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q = int(input())
que = list()
for i in range(q):
    que.append(list(input().split()))
for i in que:
    if i[0] == "1":
        s[int(i[1])-1] = i[2]
    else:
        print(len(set(s[int(i[1])-1:int(i[2])])))

Submission status: Time Limit Exceeded

Solution code:
import collections

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

for i in range(Q):
  q = list(input().split())
  if q[0] == '1':
    S[int(q[1])-1] = q[2]
  else:
    s = S[(int(q[1])-1):(int(q[2]))]
    c = collections.Counter(s)
    print(len(c))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
Q=int(input())
for i in range(Q):
  t,q1,q2=input().split()
  if t=='2':
    print(len(set(S[int(q1)-1:int(q2)])))
  else:
    q1=int(q1)
    S=S[:q1-1]+q2+S[q1:]

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = [s for s in input()]
Q = int(input())
for i in range(Q):
    a, b, c = input().split()
    if a == '1':
        S[int(b)-1] = c
    else:
        print(len(set(S[int(b)-1:int(c)])))

Submission status: Time Limit Exceeded

Solution code:
#E

n = int(input())
s = input()
q = int(input())
a = [input().split() for _ in range(q)]
for i in range(q):
    
    if a[i][0] == "1":
        j = int(a[i][1])
        s = s[:j-1] + a[i][2] + s[j:]
    else:
        print(len(set(s[int(a[i][1])-1:int(a[i][2])])))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

for i in range(q):
    select, v1, v2 = input().split()
    if select == "1":
        s[int(v1)-1] = v2
    if select == "2":
        print(len(set(s[int(v1)-1:int(v2)])))

Submission status: Time Limit Exceeded

Solution code:
def type2(s):
    set_s = set(s)
    return len(set_s)

n = int(input())
S = input()
Q = int(input())
for _ in range(Q):
    a,b,c = input().split()
    a,b = int(a),int(b)
    if a==2:
        c = int(c)
        print(type2(S[b-1:c]))
    else:
        S  = S[:b-1] + c + S[b:]

Submission status: Time Limit Exceeded

Solution code:
import collections
n=int(input())
s=list(input())
q=int(input())
l=[list(input().split()) for i in range(q)]


for i in range(q):
    if l[i][0]=="1":
        s[(int(l[i][1])-1)]=l[i][2]
    else:
        c =set(s[int(l[i][1])-1:int(l[i][2])])
        print(len(c))

Submission status: Time Limit Exceeded

Solution code:
N = int(input()) # 数字を変数に格納
S = input() # 文字列を変数に格納
Q = int(input()) # 数字を変数に格納
List = [list(map(str,input().split())) for i in range(Q)] # [[1,2],[3,4],[5,6]]

result = S

for i in range(Q):
    if List[i][0] == '1':
        n = int(List[i][1])
        result = result[:n-1] + List[i][2] + result[n:]
    elif List[i][0] == '2':
        first = int(List[i][1])
        last = int(List[i][2])
        l = result[first-1:last]
        l = ''.join(set(l))
        print(len(l))

Submission status: Time Limit Exceeded

Solution code:
import itertools as it
import collections as col
n=int(input())
s=str(input())
List=list(s)
# print(List)
q=int(input())
for i in range(q):
    a,b,c=map(str, input().split())
    A=int(a)
    B=int(b)
    if(A==1):
        List[B-1]=c
    else:
        C=int(c)
        L=col.Counter((List[B-1:C]))
        print(len(L))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = str(input())
Q = int(input())
ans = []
ans_append = ans.append
for i in range(Q):
    t,a,b = input().split(" ")
    t = int(t)
    if t == 1:
        a = int(a)
        S = S[:a-1] + str(b) + S[a:]
    else:
        a,b = int(a),int(b)
        tmp = set(S[a-1:b])
        ans_append(len(tmp))

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import copy
n = int(input())
s = str(input())
sli = list(s)
q = int(input())
for i in range(q):
    q1, q2, q3 = map(str, input().split())
    q1 = int(q1)
    if q1 == 1:
        q2 = int(q2)
        sli[q2 - 1] = q3
    else:
        q2 = int(q2)
        q3 = int(q3)
        scopy = copy.copy(sli[(q2 - 1):q3])
        print(len(list(set(scopy))))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree():
    _data = []
    _offset = 0
    _size = 0

    def __init__(self, size):
        _size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [set() for _ in range(t * 2 - 1)]

    def update_all(self, iterable):
        self._data[self._offset:self._offset+self._size] = [set(c) for c in iterable]
        for i in range(self._offset - 1, -1, -1):
            self._data[i] = self._data[i * 2 + 1] | self._data[i * 2 + 2]

    def update(self, index, value):
        i = self._offset + index
        self._data[i] = set(value)
        while i >= 1:
            i = (i - 1) // 2
            self._data[i] = self._data[i * 2 + 1] | self._data[i * 2 + 2]

    def query(self, start, stop):
        result = set()
        l = start + self._offset
        r = stop + self._offset
        while l < r:
            if l & 1 == 0:
                result = result | self._data[l]
            if r & 1 == 0:
                result = result | self._data[r - 1]
            l = l // 2
            r = (r - 1) // 2
        return result


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

st = SegmentTree(N)
st.update_all(S)

Q = int(input())
for _ in range(Q):
    q = input().split()
    if q[0] == '1':
        i, c = q[1:]
        i = int(i) - 1
        st.update(i, c)
    elif q[0] == '2':
        l, r = map(int, q[1:])
        print(len(st.query(l - 1, r)))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q = int(input())
for _ in range(q):
    c = list(map(str, input().split()))
    if int(c[0]) == 1:
        s[int(c[1]) - 1] = c[2]
    else:
        d = []
        for i in range(int(c[1]) - 1, int(c[2])):
            if not s[i] in d:
                d.append(s[i])
        print(len(d))

Submission status: Time Limit Exceeded

Solution code:
import sys

class RMQ(): #range minimum query
    def __init__(self, N, V): #create segment tree with initial value V
        d, k = 1, 0
        while d < N:
            d <<= 1
            k += 1
        self.tree = [V for _ in range(2 * d - 1)]
        self.size = d 
    
    def update(self, i, a): #update cell i by value a
        now = self.size - 1 + i
        if self.tree[now] != {a}:
            self.tree[now] = {a}
            while now > 0:
                now = (now - 1) // 2
                self.tree[now] = self.tree[2 * now + 1] | self.tree[2 * now + 2]

    def search(self, lower, higher, lbound, hbound, pos): #search minimum value of [lower, higher) init: lbound = 0, hbound = self.size, pos = 0
        if higher <= lbound or hbound <= lower: return set()
        if lower <= lbound and hbound <= higher: return self.tree[pos]
        else:
            left = self.search(lower, higher, lbound, (lbound + hbound) // 2, 2 * pos + 1)
            right = self.search(lower, higher, (lbound + hbound) // 2, hbound, 2 * pos + 2)
            return left | right


def solve():
    input = sys.stdin.readline
    N = int(input())
    S = list(input().strip("\n"))
    SegTree = RMQ(N, set())
    for i, s in enumerate(S): SegTree.update(i, s)
    Q = int(input())
    for _ in range(Q):
        t, l, r = input().strip("\n").split()
        if t == "1": SegTree.update(int(l) - 1, r)
        elif t == "2": print(len(SegTree.search(int(l) - 1, int(r), 0, SegTree.size, 0)))
    return 0

if __name__ =="__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
s2 = list(s)
q = int(input())
for i in range(q):
    temp = list(input().split())
    if temp[0] == "1":
        s2[int(temp[1]) - 1] = temp[2]
    else:
        l, r = map(int, (temp[1], temp[2]))
        check = s2[l -1:r]
        print(len(set(check)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import bisect_left, bisect_right
from collections import defaultdict
INF = float("inf")

# Range Add Query, Range Sum Query
class SegmentTree:

    def __init__(self, N):
        self.N = 1
        while self.N < N:
            self.N *= 2
        self.data1 = [0] * (2*self.N)
        self.data2 = [0] * (2*self.N)

    # [a, b) に x を加算する
    def add(self, a, b, x, k = 0, l = 0, r = -1):
        if r == -1: r = self.N
        if r <= a or b <= l: return
        if a <= l and r <= b:
            self.data1[k] += x
        else:
            self.add(a, b, x, k*2+1, l, (l+r)//2)
            self.add(a, b, x, k*2+2, (l+r)//2, r)
            self.data2[k] = max(self.data1[k*2+1]+self.data2[k*2+1], self.data1[k*2+2]+self.data2[k*2+2])

    # [a, b) の和を計算する
    def sum(self, a, b, k = 0, l = 0, r = -1):
        if r == -1: r = self.N
        if r <= a or b <= l: return 0
        if a <= l and r <= b: return self.data1[k]+self.data2[k]
        vl = self.sum(a, b, k*2+1, l, (l+r)//2)
        vr = self.sum(a, b, k*2+2, (l+r)//2, r)
        return max(vl, vr) + self.data1[k]

N = int(input())
S = list(input())
Q = int(input())
Seg = [SegmentTree(N) for i in range(26)]
for i in range(N):
    Seg[ord(S[i])-97].add(i, i+1, 1)
for i in range(Q):
    q, x, y = input().split()
    if q == '1':
        i = int(x)-1
        Seg[ord(S[i])-97].add(i, i+1, -1)
        S[i] = y
        Seg[ord(y)-97].add(i, i+1, 1)
    else:
        l, r, ans = int(x), int(y), 0
        for i in range(26):
            ans += Seg[i].sum(l-1, r) > 0
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
Q = int(input())
for i in range(Q):
  q = input().split()
  if q[0] == "1":
    i = int(q[1]) - 1
    c = q[2]
    S[i] = c
    #print(S)
  else:
    i = int(q[1]) - 1
    c = int(q[2])
    num = len(set(S[i:c]))
    #print(S[i:c])
    print(num)

Submission status: Time Limit Exceeded

Solution code:
N=int(raw_input())
S=list(raw_input())
#print S
Q = int(raw_input())

for i in range(Q):
    [s,a,b] = raw_input().split()
    s = int(s)
    a = int(a)
    if s == 1:
        S[a-1] = b
    else:
        b = int(b)
        set = [0 for i in range(26)]
        for i in range(a-1,b):
            set[ord(S[i])-ord("a")] = 1
        c = 0
        for i in range(26):
            c += set[i]
        print c

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
S = list(readline().decode().rstrip())

Q = int(readline())

for q in range(Q):
    que = list(readline().decode().split())
    que[0] = int(que[0])
    que[1] = int(que[1]) - 1
    if que[0] == 1:
        S[que[1]] = que[2]
    else:
        l = que[1]
        r = int(que[2])
        acc = S[l:r]
        print(len(set(acc)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


N = [int(i) for i in input().split()][0]
array = np.zeros([N, 26])
string = list(input())
strs = []
a0 = ord("a")
for n, s in enumerate(string):
  i = ord(s) - a0
  array[n, i] = 1
  strs.append(i)

Q = [int(i) for i in input().split()][0]
queries =[[i for i in input().split()] for _ in range(Q)]


for que in queries:
  type_, pos, st = que
  if type_ == "1":
    p = int(pos) - 1
    s1 = strs[p]
    array[p, s1] = 0
    s2 = ord(st) - a0
    strs[p] = s2
    array[p, s2] = 1
  else:
    lq = int(pos) - 1
    rq = int(st)
    print(np.sum(np.sum(array[lq:rq, :], axis=0)>0))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
Q = int(input())

for _ in range(Q):
    n, l, r = input().split()
    if n == "1":
        S[int(l) - 1] = r
    else:
        s = set(S[int(l) - 1 : int(r)])
        print(len(s))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q = int(input())

ql = []

for _ in range(q):
  ql += [input().split()]

for a, b, c in ql:
  if a == '1':
    i = int(b)
    s[i-1] = c
  else:
    l = int(b)
    r = int(c)
    print(len(set(s[l-1:r])))

Submission status: Time Limit Exceeded

Solution code:
def type2(s):
    set_s = {s[i] for i in range(len(s))}
    return len(set_s)

n = int(input())
S = input()
Q = int(input())
for _ in range(Q):
    a,b,c = input().split()
    a,b = int(a),int(b)
    if a==2:
        c = int(c)
        print(type2(S[b-1:c]))
    else:
        str_list = list(S)
        str_list[b-1]=c
        S = "".join(str_list)

Submission status: Time Limit Exceeded

Solution code:
import math

class SegmentTree:
	def update(self, i, x):
		i += self.num_leaves-1
		self.nodes[i] = x
		while i > 0:
			i = (i-1) // 2
			self.nodes[i] = self.monoid(self.nodes[i*2+1],self.nodes[i*2+2])
			
	def query(self,a,b,k=0,l=0,r=None):
		if r is None:
			r = self.num_leaves
		if r <= a or b <= l:
			return None
		if a <= l and r <= b:
			return self.nodes[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.monoid(vl,vr)
		
	def __init__(self, monoid, values):
		self.monoid = lambda x, y : monoid(x, y) if x is not None and y is not None else x or y
		self.num_leaves = 2**math.ceil(math.log2(len(values)))
		self.nodes = [None for i in range(self.num_leaves*2-1)]
		for i in range(len(values)):
			self.update(i,values[i])

def func(a,b):
    return [a[i] or b[i] for i in range(26)]

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

values = [[(ord(s[i])-ord('a')) == j for j in range(26)] for i in range(n)]

sgt = SegmentTree(func, values)

for i in range(q):
    a,b,c = Q[i]
    b = int(b)
    if a == "1":
        sgt.update(b-1,[(ord(c)-ord('a')) == j for j in range(26)])
    else:
        c = int(c)
        val = sgt.query(b-1,c)
        cnt = 0
        for i in range(26):
            if val[i]:
                cnt += 1
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q = int(input())
out = []
for i in range(q):
	c,x,y = list(map(str,input().split()))
	if int(c)==1:
		s[int(x)-1]= y
	else:
		arr = set(s[int(x)-1:int(y)])
		out.append((len(arr)))
for i in out:
	print(i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
q = int(input())
al = "abcdefghijklmnopqrstuvwxyz"
al = {al[i]: i for i in range(26)}


def get(i):
    a = [0] * 26
    a[al[i]] = 1
    return a


def add(i, j):
    k = []
    for l, m in zip(i, j):
        k.append(l + m)
    return k


def sub(i, j):
    k = []
    for l, m in zip(i, j):
        k.append(l - m)
    return k


bit = [[0]*26 for _ in range(n+1)]


def ko(i, j):
    global bit
    while i <= n:
        bit[i] = add(bit[i], j)
        i += i & (-i)


def su(i):
    s = [0]*26
    while i != 0:
        s = add(s, bit[i])
        i -= i & (-i)
    return s


a = []
for i in range(n):
    ko(i + 1, get(s[i]))
    a.append(get(s[i]))
for _ in range(q):
    kind, i, j = [k for k in input().split()]
    i = int(i)
    if int(kind) == 1:
        ko(i, sub(get(j),a[i-1]))
        a[i-1] = get(j)
    else:
        j = int(j)
        b = sub(su(j), su(i-1))
        k = 0
        for i in b:
            if i != 0:
                k += 1
        print(k)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


def main():
    mod=10**9+7
    N=I()
    S=input()
    Q=I()
    
    #####segfunc######

    #評価関数（という言い方であっている？）
    def segfunc(x,y):
        return x|y


    #初期化
    def init(init_val):
        #init_valは操作する数列
        for i in range(N):
            seg[i+num-1]=set([init_val[i]])    
        #built
        for i in range(num-2,-1,-1) :
            seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
            

    #k番目の値をxに更新
    def update(k,x):
        k += num-1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

            
    #[p,q)の区間に対するクエリへの応答
    def query(p,q):
        if q<=p:
            return ide_ele
        p += num-1
        q += num-2
        res=ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res,seg[p])
            if q&1 == 1:
                res = segfunc(res,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res,seg[p])
        else:
            res = segfunc(segfunc(res,seg[p]),seg[q])
        return len(res)


    #####単位元######
    ide_ele = set([])
    """
    ex)
    最小値のセグ木 → +inf
    　　和のセグ木 → 0
    　　積のセグ木 → 1
    　　gcdのセグ木 → 0
"""
     #num:n以上の最小の2のべき乗
    num =2**(N-1).bit_length()
    seg=[ide_ele]*2*num
    init(S)



    
    for i in range(Q):
        q,a,b=input().split()
        if q=="1":
            update(int(a)-1,set([b]))
        else:
            print(query(int(a)-1,int(b)))
            
    
    

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict


class SegTree:
    def __init__(self, n, s):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [defaultdict(lambda: 0) for _ in range(n2 << 1)]

        for i, c in enumerate(s):
            x = ord(c) - 97
            i += self.offset
            self.tree[i][x] = 1
        for i in range(self.offset - 1, 0, -1):
            for x, c in self.tree[i << 1].items():
                self.tree[i][x] += c
            for x, c in self.tree[(i << 1) + 1].items():
                self.tree[i][x] += c
        # print(*(dict(t) for t in self.tree), sep='\n')

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        if x in self.tree[i]:
            return
        y, _ = self.tree[i].popitem()
        self.tree[i][x] = 1
        i >>= 1
        while i > 1:
            sti = self.tree[i]
            sti[x] += 1
            if sti[y] == 1:
                del sti[y]
            else:
                sti[y] -= 1
            i >>= 1

    def get_types(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = set()

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result.update(self.tree[r - 1].keys())
            if l & 1:
                result.update(self.tree[l].keys())
                l += 1
            l >>= 1
            r >>= 1

        return len(result)


n = int(input())
s = input()
st = SegTree(n, s)
q = int(input())
ans = []
for line in sys.stdin:
    i, j, k = line.rstrip().split()
    if i == '1':
        j = int(j) - 1
        k = ord(k) - 97
        st.update(j, k)
    else:
        l = int(j) - 1
        r = int(k)
        ans.append(st.get_types(l, r))
print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
S=input()
nagasa=len(list(S))
num=2**(nagasa-1).bit_length()
SEG=[set([])]*2*num
def init(S):
    for i in range(n):
        SEG[i+num-1]=set([S[i]])
    for i in range(num-2,-1,-1) :
        SEG[i]=SEG[2*i+1]|SEG[2*i+2]
    
def update(k,x):
    k += num-1
    SEG[k] = set(x)
    while k:
        k = (k-1)//2
        SEG[k] = SEG[k*2+1] | SEG[k*2+2]
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    ans=set([])
    while q-p>1:
        if p&1 == 0:
            ans|= SEG[p]
        if q&1 == 1:
            ans|= SEG[q]
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        ans |=SEG[p]
    else:
        ans |= SEG[p]
        ans |= SEG[q]
    return ans
init(S)
q=int(input())
for i in range(q):
    a=input()
    if a[0]=='1':
        s,t=a[1:].split()
        s=int(s)
        update(s-1,t)
    if a[0]=='2':
        s,t=map(int, a[1:].split())
        print(len(query(s-1,t)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
s = list(input())

def segfunc(x,y):
    return (len(x[1]|y[1]),x[1]|y[1])

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = [0,set()]

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

A = []
for i in range(n):
  A.append((1,set(s[i])))
init(A)
q = int(input())
for _ in range(q):
  p,a,b = input().split()
  if p == "1":
    update(int(a)-1,(1,set(b)))
  if p == "2":
    print(query(int(a)-1,int(b))[0])

Submission status: Time Limit Exceeded

Solution code:
input()
S=list(input())
for i in range(int(input())):
    q,i,c=input().split()
    q=int(q)-1
    i=int(i)-1
    if q:print(len(set(S[i:int(c)])))
    else:S[i]=c

Submission status: Time Limit Exceeded

Solution code:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key


yn = 'YNeos'
ynflg = False
cnt = 0
ans = None

def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas



N = intinput()
S = input()
ss = []
for s in S:
    ss.append(s)
Q = intinput()
query = []
for i in range(Q):
    query.append(list(input().split()))

for q in query:
    if q[0] == '1':
        ss[int(q[1])-1] = q[2]
    if q[0] == '2':
        s = int(q[1])-1
        e = int(q[2])
        print(len(set(ss[s:e])))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
s = list(str(input()))
s.pop()
q = int(input())
for _ in range(q):
    query, i, c = map(str,input().split())
    if query == "1":
        s[int(i)-1] = c
    else:
        tmp = [False] * 26
        for j in s[int(i)-1:int(c)]:
            tmp[ord(j)-97] = True
        print(sum(tmp))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
Q = int(input())

for i in range(Q):
    q = input().split()
    q0 = int(q[0])
    if q0 == 1:
        S[int(q[1]) - 1] = q[2]
    elif q0 == 2:
        print(len(set(S[int(q[1]) - 1 : int(q[2])])))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(input())
k=int(input())

result=[]

for _ in range(k):
    a,b,c=map(str,input().split())
    if a=="1":
        s[int(b)-1]=c
        #print(s)
    else:
        temp=set(s[int(b)-1:int(c)])
        result.append(len(temp))

for item in result:
    print(item)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
Q = int(input())

for q in range(Q):
  _, i, c = input().split()
  if _ == '1':
    S = S[:int(i)-1] + c + S[int(i):]
  else:
    ans = len(set(S[int(i)-1:int(c)]))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
q = int(input())
for i in range(q):
	a,b,c=map(str, input().split())
	if a=="1":
		s=s[:int(b)-1]+c+s[int(b):]
	if a=="2":
		print(len(set(s[int(b)-1:int(c)])))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N=int(input())
S=input()
Q=int(input())

def change(num,mozi):
    global S
    SL=list(S)
    SL[num-1]=mozi
    S="".join(SL)

def count(l,r):
    return len(set(list(S)[l-1:r]))

for i in range(Q):
    q,a,b=input().split()
    if int(q)==1:
        change(int(a),b)
    if int(q)==2:
        print(count(int(a),int(b)))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

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


if __name__ == '__main__':
    main()