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 = list(input())
# N: 処理する区間の長さ
N0 = 2**(N-1).bit_length()
id_ele = [0,set()]
data = [id_ele]*(2*N0)
# a_k の値を x に更新
def segfunc(x,y):
    return (len(x[1]|y[1]),x[1]|y[1])

def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = segfunc(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = id_ele
    while L < R:
        if R & 1:
            R -= 1
            s = segfunc(s, data[R-1])

        if L & 1:
            s = segfunc(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(N):
  update(i,(1,set(s[i])))
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:
N = int(input())
S = input()
Q = int(input())

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n = int(input())
s = list(input())
q = int(input())
ql = [input().split() for _ in range(q)]

w = 800
sl = []
dl = []
for i in range((n+w-1)//w):
    ss = s[i*w:min((i+1)*w,n)]
    dl.append(set(ss))
    sl.append(ss)

for i in range(q):
    if ql[i][0]=="1":
        idx = int(ql[i][1])-1
        c = ql[i][2]

        ss = sl[idx//w]
        ss[idx%w] = c
        s[idx] = c
        sl[idx//w] = ss
        dl[idx//w] = set(ss)
    else:
        l = int(ql[i][1])-1
        r = int(ql[i][2])-1

        li = l//w
        ri = r//w
        if abs(li-ri)<2:
            print(len(set(s[l:r+1])))
        else:
            u = set()
            u = u | set(sl[li][l%w:])
            for j in range(li+1,ri):
                u = u | dl[j]
            u = u | set(sl[ri][:r%w+1])
            print(len(u))

Submission status: Time Limit Exceeded

Solution code:
import string

class BIT:

    def __init__(self, N):
        self.bit = [0 for _ in range(N + 1)]
        self.N = N

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

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

def solve(N, S, Q, query):
    bits = {}
    for c in string.ascii_lowercase:
        bits[c] = BIT(N)

    for i, c in enumerate(S):
        bits[c].add(i + 1, 1)

    ans = []
    for q, i, cr in query:
        if q == "1":
            i = int(i)
            bits[S[i-1]].add(i, -1)
            bits[cr].add(i, 1)
            S[i-1] = cr
        else:
            l = int(i)
            r = int(cr)
            kinds = 0
            for c in string.ascii_lowercase:
                k = bits[c].sum(r) - bits[c].sum(l)
                if S[l-1] == c:
                    k += 1
                if k > 0:
                    kinds += 1
            ans.append(str(kinds))
    return "\n".join(ans)



if __name__ == "__main__":
    N = int(input())
    S = list(input())
    Q = int(input())

    query = []
    for _ in range(Q):
        query.append(tuple(input().split(" ")))
    print(solve(N, S, Q, query))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

for _ in range(Q):
  t, a, b = input().split()
  if t == '1':
    S = list(S)
    S[int(a)-1] = b
    "".join(S)
  else:
    print(len(set(S[int(a)-1:int(b)])))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

def get(i):
    return np.identity(26)[al[i]]


bit = [np.zeros(26) for _ in range(n+1)]


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


def su(i):
    s = np.zeros(26)
    while i != 0:
        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, get(j)-a[i-1])
        a[i-1] = get(j)
    else:
        j = int(j)
        b = 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:
N = int(input())
S = input()
Q = int(input())

for i in range(Q):
	typ , a, b = input().split()
	if(typ == '1'):
		i = int(a)
		if(i == 0):
			S = b + S[1:]
		else:
			S = S[:i-1] + b + S[i:]
	if(typ == '2'):
		print(len(set(S[int(a)-1:int(b)])))

Submission status: Time Limit Exceeded

Solution code:
# 間に合わなさそう
n=int(input())
s=input()

q=int(input())

for _ in range(q):
    num,l,r=map(str,input().split())
    
    if num=="1":
        i=int(l);c=r;
        s=s[:i-1]+c+s[i:]
        # print(s)
    elif num=="2":
        l=int(l);r=int(r)
        hoge=s[l-1:r]
        # print(hoge)
        print(len(set(list(hoge))))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q = int(input())
while True:
    try:
        query = tuple(input().split())
        if int(query[0]) == 1:
            i, c = int(query[1]), query[2]
            s[i - 1] = c
        else:  # quert[0] == 2
            l, r = int(query[1]), int(query[2])
            print(len(set(s[l - 1:r])))
    except EOFError:
        break

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":
		f=list(s)
		f[int(b)-1]=c
		s="".join(f)
	if a=="2":
		print(len(set(s[int(b)-1:int(c)])))

Submission status: Time Limit Exceeded

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

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

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:
            self.tree[i][x] += 1
            self.tree[i][y] -= 1
            if self.tree[i][y] == 0:
                del self.tree[i][y]
            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 numpy as np
n = int(input())
s = input()
q = int(input())
al = "abcdefghijklmnopqrstuvwxyz"


def get(i):
    return np.identity(26)[al.index(i)]


bit = [np.zeros(26) for _ in range(n+1)]


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


def su(i):
    s = np.zeros(26)
    while i != 0:
        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, get(j)-a[i-1])
        a[i-1] = get(j)
    else:
        j = int(j)
        b = 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:
import sys

input = sys.stdin.readline

# N, M = map(int, input().split())
# nums = list(map(int, input().split()))
# nums_2d = [list(map(int, input().split())) for _ in range(N)]


def main():
    solve()


def solve():
    N = int(input())
    S = input()[:N]
    Q = int(input())

    for p in range(Q):
        n, i, c = input().split()
        # print(p, n, i, c)

        n = int(n)
        i = int(i) - 1

        if n == 1:
            S = S[:i] + c + S[i+1:]

        else:
            l = len(set(S[i:int(c)]))
            print(l)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    n=INT()
    s=STR()
    q=INT()
    for i in range(q):
        qs=LISTS()
        if qs[0]=='1':
            s=''.join([s[:int(qs[1])-1],qs[2],s[int(qs[1]):]])
            #print(s)
        else:
            temp=s[int(qs[1])-1:int(qs[2])]
            print(len(set(temp)))
if __name__ == '__main__':
    do()

Submission status: Time Limit Exceeded

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

for i in range(q):
    t, l, r = input().split()
    l = int(l)
    if t == "1":
        s[l-1] = r
    else:
        r = int(r)
        d = {}
        for i in range(l-1, r):
            d[s[i]] = 1
        print(len(d))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input().rstrip())
q = int(input())
for i in range(q):
    qr = input().rstrip().split()
    if qr[0] == '1':
        p = int(qr[1])
        s[p - 1] = qr[2]
    else:
        l = int(qr[1])
        r = int(qr[2])
        print(len(set(s[l-1:r])))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import math
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#############
# Main Code #
#############

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

for i in range(Q):
  query = list(map(str,input().split()))
  if query[0] == "1":
    S[int(query[1])-1] = query[2]
  if query[0] == "2":
    print(len(set(S[int(query[1])-1:int(query[2])])))

Submission status: Time Limit Exceeded

Solution code:
N = [int(i) for i in input().split()][0]
string = list(input())
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":
    string[int(pos)-1] = st
  else:
    lq = int(pos) - 1
    rq = int(st)
    print(len(set(string[lq:rq])))

Submission status: Time Limit Exceeded

Solution code:
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:
N = int(input())
S = [s for s in input()]
Q = int(input())
ans = []
for i in range(Q):
    t,a,b = input().split(" ")
    t = int(t)
    if t == 1:
        a = int(a)
        S[a-1] = b
    else:
        a,b = int(a),int(b)
        tmp = set(S[a-1:b])
        ans.append(len(tmp))
if ans != []:
    for a in ans:
        print(a)

Submission status: Time Limit Exceeded

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

for i in range(q):
  a, b, c = input().split()
  if int(a)==1:
    b = int(b)
    s[b-1] = c
  elif int(a)==2:
    b = int(b)
    c = int(c)
    tmp_s = s[b-1:c]
    print(len(set(tmp_s)))

Submission status: Time Limit Exceeded

Solution code:
class segmentTreeCharCount():
    dat = []
    lenTreeList = -1
    targetChar = None
    depthTreeList = 0
    lenPaddingEntry = 0
    unitDefault = [None, 0, 0, 0, 0, 1]

    def __init__(self):
        pass

    def load(self, l, tc):
        self.targetChar = tc
        # len(l)個よりも大きい2の二乗を得る
        self.lenTreeList = 2 ** (len(l) - 1).bit_length()  # len 5 なら 2^3 = 8
        self.depthTreeList = (len(l) - 1).bit_length()  # 木の段数(0 origin)
        # lenPaddingEntryは[1,2,3,4,5]を与えたなら[1,2,3,4,5,None,None,None]として扱ったので3を返す
        self.lenPaddingEntry = 2 ** (len(l) - 1).bit_length() - len(l)  # 何エントリを補完したか

        self.dat = [self.unitDefault] * (self.lenTreeList * 2)
        # 値のロード
        for i in range(len(l)):
            if l[i] == self.targetChar:
                self.dat[self.lenTreeList - 1 + i] = [l[i], 1, 1, 1, 1, 0]
            else:
                self.dat[self.lenTreeList - 1 + i] = [l[i], 0, 0, 0, 0, 0]
        self.build()

    def funcSegmentValueById(self, nodeId):
        l = self.dat[nodeId * 2 + 1]
        r = self.dat[nodeId * 2 + 2]
        return self.funcSegmentValue(l, r, nodeId)

    # 書く計算をおこなう。
    # この際にはこの計算で境界とするl,r位置であるa,bをいれることで、右端と左端のパディングを行う
    def funcSegmentValue(self, lNode, rNode, parentNodeId):
        # print("funcSegmentValue parentNode={0}".format(parentNodeId))
        # print("L:")
        lchar, lcnt, lconsLeft, lconsRight, lconsLen, lNoneNum = lNode
        # print(lNode)
        # print("R:")
        rchar, rcnt, rconsLeft, rconsRight, rconsLen, rNoneNum = rNode
        # print(rNode)

        # ここは便宜上の名前変更(あまり深い意味はない)
        if lchar is None or rchar is None:
            nchar = None
        elif rchar is not None:
            nchar = rchar
        elif lchar is not None:
            nchar = lchar

        # l, rに含まれる文字の総量
        ncnt = lcnt + rcnt

        # 連結した後の右の長さは原則的に左と一致する
        nconsLeft = lconsLeft
        nconsRight = rconsRight

        """
        #print("searchdepth = {0}".format(self.depthTreeList - ((parentNodeId + 1).bit_length() - 1)))
        if lcnt == 2 ** (self.depthTreeList - ((parentNodeId + 1).bit_length())):
            #print("child!L!")
            nconsLeft += rconsLeft
        if rcnt == 2 ** (self.depthTreeList - ((parentNodeId + 1).bit_length())):
            #print("child!R!")
            nconsRight += lconsRight
        """

        # ルートの場合、右のノードを合算するときに右のノードの左端の連続文字列数が足りなくても
        # パディング分と会うなら、左のノードの右端の連続文字列数と合算する
        # print("magic = {0}".format(2 ** (self.depthTreeList - ((parentNodeId + 1).bit_length()))))

        if lconsLeft == (2 ** (self.depthTreeList - ((parentNodeId + 1).bit_length())) - lNoneNum):
            # print(" parentnodeid {2} l root special cur={0} add={1}".format(nconsRight, rconsLeft, parentNodeId))
            nconsLeft += rconsLeft
        if rconsRight == (2 ** (self.depthTreeList - ((parentNodeId + 1).bit_length())) - rNoneNum):
            # print(" parentnodeid {2} r root special cur={0} add={1}".format(nconsRight, rconsLeft, parentNodeId))
            # print(" nconsRight{0} += lconsLeft{1}".format(nconsRight, lconsLeft))
            nconsRight += lconsRight

        # print("update n={0}, max({1},{2},{3},{4},{5}".format(parentNodeId, nconsLeft, nconsRight, lconsLen, rconsLen, lconsRight + rconsLeft))

        nconsLen = max(nconsLeft, nconsRight, lconsLen, rconsLen, lconsRight + rconsLeft)

        nNoneNum = lNoneNum + rNoneNum
        res = [nchar, ncnt, nconsLeft, nconsRight, nconsLen, nNoneNum]
        # print("Return{0}".format(res))
        return res

    # char=入っているデータ, cnt, consLeft, consRight, consLen
    def build(self):
        for nodeId in range(self.lenTreeList - 2, -1, -1):
            # 重要：このコードはリストを生成しなおすので代入に直すこと！
            self.dat[nodeId] = self.funcSegmentValueById(nodeId)

    def setValue(self, i, a):
        """
        set a to list[i]
        """
        # print("setValue: {0}, {1}".format(i, a))
        nodeId = (self.lenTreeList - 1) + i
        # print(" first nodeId: {0}".format(nodeId))
        """
        self.dat[nodeId] = a
        if a == self.targetChar:
            self.dat[self.lenTreeList - 1 + i] = [a, 1, 1, 1, 1, 0]
        else:
            self.dat[self.lenTreeList - 1 + i] = [a, 0, 0, 0, 0, 0]
        """
        # print("before")
        # print(self.dat[nodeId])
        self.dat[nodeId] = a
        if a == self.targetChar:
            self.dat[nodeId] = [a, 1, 1, 1, 1, 0]
        else:
            self.dat[nodeId] = [a, 0, 0, 0, 0, 0]
        # print("after")
        # print(self.dat[nodeId])

        while nodeId != 0:
            nodeId = (nodeId - 1) // 2
            # print(" next nodeId: {0}".format(nodeId))
            # sum : self.dat[nodeId] = self.dat[nodeId * 2 + 1] + self.dat[nodeId * 2 + 2]
            self.dat[nodeId] = self.funcSegmentValueById(nodeId)

    def querySub(self, a, b, nodeId, l, r):
        """
        [a,b) 区間の親クエリに対するノードnodeへ[l, r)の探索をデリゲート
        区間については、dataの添え字は0,1,2,3,4としたときに、
        [0,3)なら0,1,2の結果を返す
        Noneとなる条件: r <= a or b <= l
        """
        # print("querySub: a={0}, b={1}, nodeId={2}, l={3}, r={4}".format(a, b, nodeId, l, r))

        if (r <= a or b <= l):
            cannotAnswer = (r - l)
            # print(" > None") # これは答えられない数を返すべき
            return [None, 0, 0, 0, 0, cannotAnswer]
        if a <= l and r <= b:
            # print(" > have: {0} [node = {1}]".format(self.dat[nodeId], nodeId))
            # print(" >     : a={0} <= l={1} and r{2} <= b{3}".format(a,l,r,b))
            res = self.dat[nodeId]
            return res

        # print("querySubcalc: a={0}, b={1}, nodeId={2}, l={3}, r={4}".format(a, b, nodeId, l, r))
        resLeft = self.querySub(a, b, 2 * nodeId + 1, l, (l + r) // 2)
        resRight = self.querySub(a, b, 2 * nodeId + 2, (l + r) // 2, r)
        # print("querySubend: a={0}, b={1}, nodeId={2}, l={3}, r={4}".format(a, b, nodeId, l, r))
        # print(" > L")
        # print("  node{0}: {1}".format(2 * nodeId + 1, resLeft))
        # print(" > R")
        # print("  node{0}: {1}".format(2 * nodeId + 2, resRight))
        # print(resRight)
        res = self.funcSegmentValue(resLeft, resRight, nodeId)
        # print(" > res")
        # print(res)
        return res

    def query(self, a, b):
        return self.querySub(a, b, 0, 0, self.lenTreeList)

    def debugGetSliceStr(self, a, b):
        """
        元の文字列リストの[a:b]を返す: str
        """
        return "".join(list(map(lambda x: x[0], self.dat[self.lenTreeList - 1 + a:self.lenTreeList - 1 + b])))

n = int(input())
s = input()
sl = list(s)
st = []
for i in range(26):
    elem = segmentTreeCharCount()
    c = chr(ord("a") + i)
    elem.load(sl, c)
    st.append(elem)
    #print(elem.query(0, n))
# 0個目が数
#print(st[0].query(0, n)[0])
q = int(input())
for _ in range(q):
    ty, x, y = input().split()
    x = int(x)
    if ty == "1":
        cnum = ord(y[0]) - ord("a") # indexを得る
        for i in range(26):
            st[i].setValue(x - 1, y)
    elif ty == "2":
        x = int(x) - 1
        y = int(y)
        res = 0
        #print("x", x, "y", y)
        for i in range(26):
            cnt = st[i].query(x , y)[1]
            #print(st[i].debugGetSliceStr(x, y))
            #print(i, "cnt", cnt)
            if cnt != 0:
                res += 1
        print(res)
    else:
        print("error")

Submission status: Time Limit Exceeded

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

for i in range(Q):
	typ , a, b = input().split()
	if(typ == '1'):
		i = int(a)
		c = b
		if(i == 0):
			S = c + S[1:]
		else:
			S = S[:i-1] + c + S[i:]

	
	if(typ == '2'):
		l = int(a)
		r = int(b)
		S_part = S[l-1:r]

		print(len(set(S_part)))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
ho=input()
hoge=[]
for i in range(n):
  hoge.append(ho[i])
q=int(input())

for i in range(q):
  a,b,c=map(str,input().split())
  if(a=="1"):
    b=int(b)
    hoge[b-1]=c
  else:
    b,c=int(b),int(c)
    huga=hoge[b-1:c]
    print(len(list(set(huga))))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
w = list(input())
n = int(input())
for i in range(n):
    q = list(input().split())
    if q[0]=='1':
        w[int(q[1])-1] = q[2]
    elif q[0]=='2':
        print(len(set(w[int(q[1])-1:int(q[2])])))

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i)
        if cmd == "1":
            S[i-1] = j
        elif cmd == "2":
            s1 = set()
            for ii in range(i-1, int(j)):
                s1.add(S[ii])
            ans.append(len(s1))

    print(*ans,sep="\n")

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=list(input())
Q=int(input())
ans=[]
for _ in range(Q):
  x, y, z=input().split()
  x=int(x)
  y=int(y)
  if x==1:
    S[y-1]=z
  else:
    z=int(z)
    if z==N:
      ans.append(len(set(S[y-1:])))
    else:
      ans.append(len(set(S[y-1:z])))
ans=[str(ans[i]) for i in range(len(ans))]
print('\n'.join(ans))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = [_ for _ in input()]
qn = int(input())

for i in range(qn):
  q, a, b = [_ for _ in input().split()] 
  if q == '1':
    s[int(a)-1] = b
  else:
    print(len(set(s[int(a)-1:int(b)])))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import collections
n = int(input())
s = input()
q = int(input())
for i in range(0, q):
    t, x, y = input().split()
    if t == "1":
        s = s[:int(x) - 1] + y + s[int(x):]
    else:
        start = int(x) - 1
        end = int(y)
        print(len(collections.Counter(s[start:end])))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
s = [s[i] for i in range(n)]
q = int(input())

for i in range(q):
    qtype, a, b = input().split()
    if qtype == '1':
        s[int(a)-1] = b
    else:
        a = int(a) - 1
        b = int(b)
        print(len(set(s[a:b])))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=[i for i in input()]
Q=int(input())

for _ in range(Q):
    f, a, b =(i for i in input().split())
    if int(f)==1:
        S[int(a)-1]=b
    else:
        print(len(set(S[int(a)-1:int(b)])))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q_num = int(input())
query = []
for _ in range(q_num):
    query.append(input().split())


for q, i, j in query: 
    if q == "1":
        i = int(i)
        s[i-1] = j
    else:
        i = int(i)
        j = int(j)
        print(len(set(s[i-1:j])))

Submission status: Time Limit Exceeded

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

for i in range(q):
    t, l, r = input().split()
    l = int(l)
    if t == "1":
        s[l-1] = r
    else:
        r = int(r)
        print(len(set(s[l-1:r])))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
inputs = sys.stdin.readline
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    n=INT()
    s=STR()
    q=INT()
    for i in range(q):
        qs=LISTS()
        if qs[0]=='1':
            s=s[:int(qs[1])-1]+qs[2]+s[int(qs[1]):]
            #print(s)
        else:
            temp=s[int(qs[1])-1:int(qs[2])]
            print(len(set(temp)))
if __name__ == '__main__':
    do()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q = int(input())
for i in range(q):
    x,y,z = input().split()
    if x == "1":
        s[int(y)-1] = z
    else:
        
        print(len(set(s[int(y)-1:int(z)])))

Submission status: Time Limit Exceeded

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

for _ in range(q):
    q = input().split()
    #print(q)

    if q[0] == "1":
        t = int(q[1]) - 1
        s = s[:t] + q[2] + s[t+1:]
        #print(s)

    elif q[0] == "2":
        l, r = int(q[1]), int(q[2])
        #print(l,r)
        print(len(set(s[l-1:r])))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
q = int(input())
for _ in range(q):
    type, first, second = input().split()
    type = int(type)
    first = int(first)
    if type == 1:
        s = list(s)
        s[first-1] = second
        s = "".join(s)
    else:
        print(len(set(s[first-1:int(second)])))

Submission status: Time Limit Exceeded

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

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

LEN=N

BIT=[[0]*(LEN+1) for i in range(26)]

def update(v,w,i): # index vにwを加える
    while v<=LEN:
        BIT[i][v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v,i): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[i][v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

for i in range(N):
    update(i+1,1,ord(S[i])-97)

for i in range(Q):
    qf,x,y=input().split()
    qf=int(qf)

    if int(qf)==1:
        x=int(x)
        update(x,-1,ord(S[x-1])-97)
        update(x,1,ord(y)-97)
        S[x-1]=y

    else:
        x=int(x)
        y=int(y)
        ANS=0
        for i in range(26):
            if getvalue(y,i)-getvalue(x-1,i)>0:
                ANS+=1

        print(ANS)

Submission status: Time Limit Exceeded

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


for _ in range(q):
    cmd, x, y = input().split()
    if cmd == '1':
        s[int(x)-1] = y
    else:
        print(len(set(s[int(x)-1:int(y)])))