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:

class segtree:

    def __init__(self, n,operator,identity):
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2**(len(nb)-1)
        else:
            self.num_end_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity
        self.operator =operator

    def update(self,x,val):
        actual_x = x+self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0 :
            actual_x = actual_x//2
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        width_of_floor = self.num_end_leaves//(2**depth)
        leaf_right = leaf_left+width_of_floor-1

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
            return self.operator(val_l,val_r)


import sys
from fractions import gcd
input = sys.stdin.readline
N=int(input())
S=[i for i in input()]
Q=int(input())

s_tree = segtree(N,(lambda x,y:set(list(x)+list(y))),set([])) 
for i in range(N):
    s_tree.update(i, set([S[i]]))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
s = sys.stdin.readlines()
N = int(s[0])
S = s[1]
Q = int(s[2])

seg = [set([]) for _ in range(2*N-1)]
def update(k, x):
    k += N-1
    seg[k] = set([x])
    while k:
        k = (k-1)//2
        seg[k] = seg[2*k+1] | seg[2*k+2]
        
def query(p, q):
    p += N-1
    q += N-2
    res = set([])
    while q-p > 1:
        if p&1 == 0:
            res = res | seg[p]
        if q&1 == 1:
            res = res | seg[q]
            q -= 1
        p //= 2
        q = (q-1)//2
    if p == q:
        res |= seg[q]
    else:
        res |= seg[p] | seg[q]
    return len(res)

for i in range(N):
    update(i, S[i])
    
for i in range(3, Q+3):
    a,b,c = map(str, s[i].split())
    if a == "1":
        update(int(b)-1, c)
    else:
        print(query(int(b)-1, int(c)))

Submission status: Time Limit Exceeded

Solution code:
import collections

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

answer = []


def type_1(i_mojime, c):
    i_mojime -= 1
    S[i_mojime] = c

def type_2(l, r):
    string = S[l - 1 : r]
    
    CTR = collections.Counter(string).most_common()
    ans = len(CTR)
    
    answer.append(ans)
    


for i in range(Q):
    
    q, i, x = input().split()
    
    if (q == '1'):
        type_1(int(i), x)
        
    
    else:
        i = int(i)
        x = int(x)
        type_2(i, x)


for i in answer:
    print(i)

Submission status: Time Limit Exceeded

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

    def __init__(self, size):
        _size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [None for _ in range(t * 2 - 1)]
        self._dirty = [False 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]
            self._dirty[i] = True

    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]
            self._dirty[i] = True

    def refresh(self, i):
        if not self._dirty[i]:
            return
        self.refresh(i * 2 + 1)
        self.refresh(i * 2 + 2)
        self._data[i] = self._data[i * 2 + 1] | self._data[i * 2 + 2]
        self._dirty[i] = False

    def query(self, start, stop):
        result = set()
        l = start + self._offset
        r = stop + self._offset
        while l < r:
            if l & 1 == 0:
                self.refresh(l)
                result = result | self._data[l]
            if r & 1 == 0:
                self.refresh(r - 1)
                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 = input()
s = []
A = [[] for i in range(26)]
DE = [[] 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())
import bisect
for i in range(Q):
    q,a,b = map(str,input().split())
    a = int(a)
    a -= 1
    if q == '1':
        x = s[a]
        s[a] = b
        B = A[ord(x)-97]
        A[ord(b)-97].append(a)
        DE[ord(x)-97].append(a)
    else:
        ans = 0
        b = int(b)
        b -= 1
        for i in range(26):
            B = A[i]
            B.sort()
            C = DE[i]
            C.sort()
            p = bisect.bisect_left(B,a)
            q = bisect.bisect_right(B,b)
            r = bisect.bisect_right(C,b) - bisect.bisect_left(C,a)
            if q - p - r > 0:
                ans += 1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

def main():
    N = int(input())
    S = input()
    Q = int(input())

    res = []
    def str_to_list(s):
        return [x for x in s]

    S = str_to_list(S)
    for i in range(Q):
        qtype, a, b = input().split()
        if qtype == '1':
            a = int(a)
            S[a-1] = b

        elif qtype == '2':
            a = int(a)
            b = int(b)
            c = S[a-1:b]
            res.append(len(set(c)))

    for r in res:
        print(r)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
n = int(sys.stdin.readline().strip())
s = list(sys.stdin.readline().strip())
alpha = "abcdefghijklmnopqrstuvwxyz"
dict = {i:[] for i in alpha}
for i, _s in enumerate(s):
    dict[_s].append(i)
q = int(sys.stdin.readline().strip())
for i in range(q):
    type, first, last = [i for i in sys.stdin.readline().split()]
    if type == "2":
        first = int(first)
        last = int(last)
        first -= 1
        last -= 1
        cnt = 0
        for a in alpha:
            ls = dict[a]
            if bisect.bisect_left(ls, first) != bisect.bisect_right(ls, last):
                cnt += 1
        print(cnt)
    else:
        first = int(first)
        first -= 1
        dict[s[first]].pop(bisect.bisect_left(dict[s[first]], first))
        s[first] = last
        bisect.insort_left(dict[last], first)

Submission status: Time Limit Exceeded

Solution code:
import collections
n=int(input())
s=list(input())
q=int(input())
for i in range(q):
    query=list(input().split())
    if query[0]=='1':
        s[int(query[1])-1]=query[2]
    else:
        cut=s[int(query[1])-1:int(query[2])]
        ans=collections.Counter(cut)
        print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
from collections import deque
def main():
    n = int(input())
    s = np.array(list(input()))
    q = int(input())

    result = []
    for _ in range(q):
        query = input().split()
        ty,t1,t2 = query[0],query[1],query[2]
        if ty =='1':
            s[int(t1)-1] = t2
        else:
            t1,t2 = int(t1)-1, int(t2)
            result.append(len(set(s[t1:t2])))

    for r in result:
        print(r)
        
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)



def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, N, operator, identity_element):
        """ operator and identity_element has to be a monoid.
        """
        self.__N = 2**int(math.ceil(math.log(N, 2)))
        self.__table = [identity_element] * (self.__N * 2 - 1)
        self.__op = operator
        self.__ie = identity_element

    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        t = self.__table
        o = self.__op

        t[i] = x
        while i != 0:
            pi = (i - 1) // 2  # parent
            li = 2*pi + 1
            ri = 2*pi + 2
            v = o(t[li], t[ri])
            if t[pi] != v:
                t[pi] = v
            else:
                break
            i = pi

    def query(self, a, b):
        stack = [(0, 0, self.__N)]
        t = self.__table
        o = self.__op

        ans = self.__ie
        c = 0
        while stack:
            c += 1
            k, l, r = stack.pop()
            cnd = t[k]
            if a <= l and r <= b:
                ans = o(ans, cnd)
            else:
                if (l + r) // 2 > a and b > l:
                    stack.append((2 * k + 1, l, (l + r) // 2))

                if r > a and b > (l + r) // 2:
                    stack.append((2 * k + 2, (l + r) // 2, r))
        return ans

    def print(self):
        print(self.__table)



@mt
def slv(N, S, Q):
    S = [c for c in S]
    st = [SegmentTree(N, add, 0) for _ in range(26)]
    for i, c in enumerate(S):
        st[ord(c)-ord('a')].update(i, 1)

    for q in Q:
        if q[0] == '1':
            i = int(q[1]) - 1
            d = q[2]
            c = S[i]
            S[i] = d
            st[ord(c)-ord('a')].update(i, 0)
            st[ord(d)-ord('a')].update(i, 1)
        if q[0] == '2':
            i = int(q[1]) - 1
            j = int(q[2]) - 1
            ans = 0
            for k in range(26):
                if st[k].query(i, j+1) > 0:
                    ans += 1
            print(ans)
    # return ans


def main():
    N = read_int()
    S = read_str()
    Q = [read_str_n() for _ in range(read_int())]
    (slv(N, S, Q))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
s=list(input().strip())
q=int(input())
for _ in range(q):
    a,x,y=input().split()
    if a=="1":
        i=int(x)-1
        c=y
        s[i]=c
    if a=="2":
        l=int(x)-1
        r=int(y)
        ans=len(set(s[l:r]))
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
INF = float("inf")

# Binary Indexed Tree
class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N+1)
    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x
    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

for i in range(q):
    type,iq,q=map(str,input().split())
    if type == "1":
        s = "".join([s[:int(iq)-1],q,s[int(iq):]])
    else:
        print(len(set(s[int(iq)-1:int(q)])))

Submission status: Time Limit Exceeded

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

"""考え方
対応が必要そうなところだけSを修正する。
そうでないと、Sを修正するところの計算量が大きくなりすぎてしまいそう
"""
import re

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	S = input()
	S = S[:-1]
	Q = inputInt()

	ans = []
	for i in range(Q):
		#print(S)
		Oo = input()
		Oo = Oo[:-1]
		O = Oo.split()
		o1 = int(O[0])
		o2 = int(O[1])
		if o1 == 1:
			o3 = O[2]
			S1 = S[:o2-1]
			S2 = S[o2:]
			S = S1 + o3 + S2
		else:
			o3 = int(O[2])
			tmp = S[o2-1:o3]
			c = collections.Counter(tmp)
			ans.append(len(c))

	for i in ans:
		print(i)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

q1 = []
q2 = []
type_seq = []
for i in range(Q):
    type_, p1, p2 = input().split()
    if type_ == "2":
        q2.append((int(p1), int(p2)))
        type_seq.append(2)
    else:
        q1.append((int(p1), p2))
        type_seq.append(1)

for type_ in type_seq:
    if type_ == 1:
        query = q1.pop(0)
        S[query[0]-1] = query[1]
    else:
        start, end = q2.pop(0)
        string_set = set(S[start-1:end])
        print(len(string_set))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
S = input()
Q = int(input())
query = []
for i in range(Q):
    query.append(input().split())

for i in range(Q):
    a, b, c = query[i]
    if a == '1':
        b = int(b)-1
        if not S[b] == c:
            S = S[:b]+c+S[b+1:]
    else:
        b = int(b)-1; c = int(c)
        print(len(Counter(S[b:c]).keys()))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Mar  1 22:12:35 2020

@author: naoki
"""

# =============================================================================
# with open('C:/Users/naoki/Desktop/Atcoder/input.txt') as f:
#     N = int(f.readline())
#     S = str(f.readline())
#     Q = int(f.readline())
#     p = [list(map(str,f.readline().split())) for _ in range(Q)]
# =============================================================================

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

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

Submission status: Time Limit Exceeded

Solution code:


class segtree:

    def __init__(self, n,operator,identity):
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2**(len(nb)-1)
        else:
            self.num_end_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity
        self.operator =operator

    def update(self,x,val):
        actual_x = x+self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0 :
            actual_x = actual_x//2
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        width_of_floor = self.num_end_leaves//(2**depth)
        leaf_right = leaf_left+width_of_floor-1

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
            return self.operator(val_l,val_r)



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

s_tree = segtree(N,(lambda x,y:set(list(x)+list(y))),set([])) 
for i in range(N):
    s_tree.update(i, set([S[i]]))




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

Submission status: Time Limit Exceeded

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

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 = [None] * n2 + [{} for _ in range(n2)]

        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):
            sti = self.tree[i] = defaultdict(lambda: 0, self.tree[i << 1])
            for x, c in self.tree[(i << 1) + 1].items():
                sti[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 > 0:
            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:
N=int(input())
s = input()
a = [str(c) for c in s]
q=int(input())
b = [list(input().split()) for i in range(q)]
for i in range(q):
  m=int(b[i][1])
  if(b[i][0]=="1"):
      a[m-1]=b[i][2]
  else:
    m,n=int(b[i][1]),int(b[i][2])
    print(len(set(a[m-1:n])))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
S = input()
Q = int(input())

ide_ele = set()

def segfunc(x,y):
    return x|y

def init(init_val):
    #set_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]) 
    
def update(k,x):
    k += num-1
    if x in seg[k]: return
    seg[k] = set((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

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

init(S)

for _ in range(Q):
    t, a, b = input().split()
    if t == '1':
        a = int(a)
        update(a-1, b)
    else:
        a, b = int(a)-1, int(b)
        print(len(query(a,b)))

Submission status: Time Limit Exceeded

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

# int = int(input())
# s = input().split()
# i = list(map(int, input().split()))
# s = [input() for i in range(3)]

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

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n = int(input())
  s = list(input().strip())
  q = int(input())
  for _ in range(q):
    t, iq, cq = input().strip().split()
    if t == '1':
      iq = int(iq)
      s[iq-1] = cq
    if t == '2':
      iq, cq = int(iq), int(cq)
      print(len(set(list(s[iq-1:cq]))))

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
S = list(input())
Q = int(input())
ans = []
ans_append = ans.append
for _ in range(Q):
    query = input().split()
    if query[0] == "1":
        S[int(query[1]) - 1] = query[2]
    else:
        l, r = map(int, query[1:])
        c = set(S[l - 1:r])
        ans_append(len(c))
print("\n".join(str(c) for c in ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input().strip()
C = {chr(i):[0 for _ in range(N)] for i in range(97,123)}
for j in range(N):
    a = S[j]
    C[a][j] = 1
Q = int(input())
for _ in range(Q):
    x,y,z = input().split()
    if int(x)==1:
        y = int(y)
        for i in range(97,123):
            if C[chr(i)][y-1]==1:
                C[chr(i)][y-1] = 0
        C[z][y-1] = 1
    elif int(x)==2:
        y = int(y)
        z = int(z)
        cnt = 0
        hist = [0 for _ in range(123)]
        for j in range(y-1,z):
            for i in range(97,123):
                if C[chr(i)][j]==1 and hist[i]==0:
                    cnt += 1
                    hist[i] = 1
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

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

res = []
def str_to_list(s):
    return [x for x in s]

S = str_to_list(S)
for i in range(Q):
    qtype, a, b = input().split()
    if qtype == '1':
        a = int(a)
        S[a-1] = b

    elif qtype == '2':
        a = int(a)
        b = int(b)
        c = S[a-1:b]
        res.append(len(set(c)))

for r in res:
    print(r)

Submission status: Time Limit Exceeded

Solution code:
def q2(strg, stt, ed):
  return(len(set(strg[stt-1:ed])))
def q1(strg, nb, ch):
  #strg[nb-1] = ch
  tmp = [x for x in strg]
  tmp[nb-1] = ch
  strg_post = "".join(tmp)
  return strg_post

n = input()
n = int(n)
s = input()
q = input()
q = int(q)
for i in range(q):
  inp = input().split(" ")
  if int(inp[0]) == 1:
    s = q1(s, int(inp[1]), inp[2])
  else:
    print(q2(s, int(inp[1]), int(inp[2])))

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':
        if S[int(q[1])-1] != q[2]:
            S[int(q[1])-1] = q[2]
    else:
        q = [int(i) for i in q]
        ans = S[q[1]-1:q[2]]
        ans1 = set()
        for i in ans:
            ans1.add(i)
        print(len(ans1))