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:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)


class SegmentTree:
    """
    引数：
        N: 処理する区間の長さ
        operator: モノイド演算 (max, min, __add__,ラムダ式,関数定義など)
        UNIT: 単位元
        a: 長さNの配列 a で初期化（a を与えない場合、単位元で初期化）
    注意: 内部的には 1-indexed
    """

    def __init__(self, N, operator, unit, a=None):
        self.op = operator
        self.UNIT = unit

        self.N0 = 2**(N-1).bit_length()
        self.tree = [self.UNIT]*(2*self.N0)
        if a != None:
            self.tree[self.N0:self.N0+N] = a[:]
            for k in range(self.N0-1, 0, -1):
                self.tree[k] = self.op(self.tree[2*k], self.tree[2*k+1])

    # a_k の値を x に更新
    def update(self, k, x):
        k += self.N0
        self.tree[k] = x
        k //= 2
        while k:
            self.tree[k] = self.op(self.tree[2*k], self.tree[2*k+1])
            k //= 2

    # 区間[l,r)をopでまとめる
    def query(self, l, r):
        L = l + self.N0
        R = r + self.N0
        s = self.UNIT
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(self.tree[R], s)
            if L & 1:
                s = self.op(s, self.tree[L])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def get(self, k):  # k番目の値を取得。query[k,k]と同じ
        return self.tree[k + self.N0]

    def all(self):
        return self.tree[1]


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


def ope(x, y):
    r = []
    if type(x) is str and type(y) is str:
        r = [x, y]
    elif type(x) is str:
        r = [x] + y
    elif type(y) is str:
        r = x + [y]
    else:
        r = x + y

    return list(set(r))


seg = SegmentTree(N, ope, '-', S)

Q = int(input())

ans = []
for _ in range(Q):
    q, a, b = input().split()

    if q == '1':
        seg.update(int(a) - 1, b)
    else:
        r = seg.query(int(a) - 1, int(b))
        ans.append(str(len(r)-1))


print("\n".join(ans))

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  n=int(input())
  s=list(input())
  q=int(input())
  for i in range(q):
    v,c,x=input().split()
    v=int(v)
    c=int(c)
    if v==1:
      s[c-1]=x
    else:
      x=int(x)
      print(len(set(s[c-1:x])))
if __name__ == '__main__':
    main()

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:
import bisect
import sys

input = sys.stdin.readline
num2alpha = lambda c: chr(c + 97)
alpha2num = lambda c: ord(c) - ord("a")


class SegTreeMax:
    def __init__(self, l):
        self.N = 1
        while self.N < len(l):
            self.N *= 2
        self.L = [0 for _ in range(self.N * 2 - 1)]

    def update(self, k, v):
        k += self.N - 1
        self.L[k] = v
        while k > 0:
            k = (k - 1) // 2
            self.L[k] = max(self.L[k * 2 + 1], self.L[k * 2 + 2])

    def query(self, a, b):
        return self.inquiry(0, self.N, 0, a, b)

    def inquiry(self, l, r, k, a, b):
        if r <= a or l >= b:
            return 0
        if a <= l and b >= r:
            return self.L[k]
        vl = self.inquiry(l, (l + r) // 2, k * 2 + 1, a, b)
        if vl == 1:
            return 1
        vr = self.inquiry((l + r) // 2, r, k * 2 + 2, a, b)
        if vr == 1:
            return 1
        return 0


def main():
    N = int(input())
    Stri = input()
    L = []
    for c in Stri:
        L.append(c)
    Q = int(input())
    l0 = [0 for _ in range(N)]
    S = [SegTreeMax(l0) for _ in range(26)]
    for i in range(N):
        S[alpha2num(L[i])].update(i, 1)

    for _ in range(Q):
        a, b, c = input().split()
        if a == "1":
            i = int(b) - 1
            S[alpha2num(L[i])].update(i, 0)
            L[i] = c
            S[alpha2num(c)].update(i, 1)

        else:
            l = int(b) - 1
            r = int(c)
            res = 0
            for i in range(26):
                if S[i].query(l, r):
                    res += 1
            print(res)


main()

Submission status: Time Limit Exceeded

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

for i in range(q):
    tmp = input().split()
        
    if int(tmp[0]) != 1:
        a,b,c = map(int, tmp)
        
        print(len(set(s[b-1:c])))
        
    else:
        a,b,c = map(str, tmp)
        b = int(b)
        s[b-1] = c

Submission status: Time Limit Exceeded

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

for _ in range(Q):
    qtype, arg1, arg2 = input().split()
    if qtype == "1":
        arg1 = int(arg1)
        S = S[:arg1-1] + arg2 + S[arg1:]
    else:
        ps = S[int(arg1)-1:int(arg2)]
        print(len(set([x for x in ps])))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
Q = int(input())
count = [[0 for _ in range(N+1)] for i in range(26)]

for i, c in enumerate(S):
    for j in range(26):
        if ord(c)-97 == j:
            count[j][i+1] = count[j][i]+1
        else:
            count[j][i+1] = count[j][i]
event = []
query = [input().split() for i in range(Q)]
for q in query:
    qtype, l, r = q
    if int(qtype) == 1:
        qtype = int(qtype)
        l = int(l)
        if r != S[l-1]:
            event.append([1, l, r])
            event.append([-1, l, S[l-1]])
    else:
        qtype, l, r = map(int, [qtype, l, r])
        tmp = []
        for i in range(26):
            tmp.append(count[i][r]-count[i][l-1])

        for e in event:
            etype, el, val = e
            if l <= el <= r:
                tmp[ord(val)-97] += etype

        ans = 0
        for t in tmp:
            if t >= 1:
                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):
    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:
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)
if len(dl)%2==1:
    dl.append(set())
dl2 = []
for i in range(len(dl)//2):
    dl2.append(dl[2*i] | dl[2*i+1])
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)
        if (idx//w)%2==0:
            dl2[idx//w//2] = dl[idx//w] | dl[idx//w+1]
        else:
            dl2[idx//w//2] = dl[idx//w-1] | dl[idx//w]
    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(sl[li][l%w:])
            u |= set(sl[ri][:r%w+1])
            if (li+1)%2==1:
                u |= dl[li+1]
                li += 1
            if (ri-1)%2==0:
                u |= dl[ri-1]
                ri -= 1
            for j in range(li+1,ri,2):
                u |= dl2[j//2]
            print(len(u))

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
n = int(input())
s = list(input())
alpha = "abcdefghijklmnopqrstuvwxyz"
dict = {i:[] for i in alpha}
for i, _s in enumerate(s):
    dict[_s].append(i)
q = int(input())
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 sys
input = sys.stdin.readline

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

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

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]=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] = 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 = res | seg[p]
        if q&1 == 1:
            res = res | seg[q]
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = res | seg[p]
    else:
        res = (res | seg[p]) | seg[q]
    return res

#####単位元######
ide_ele = set()

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

init(s)
#print(seg)

for i in range(q):
    t, x, y = map(str, sys.stdin.readline().split())
    if t == '2':
        l = int(x)-1
        r = int(y)-1
        print(len(query(l, r+1)))
    else:
        i = int(x)-1
        c = {y}
        update(i, c)

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();
  aa = int(a);
  bb = int(b);
  if aa == 1:
    s[bb-1] = c;
    # print(s)
  else:
    d = int(c);
    print(len(set(s[bb-1:d])))

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 = [set() 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:
class Binary_Indexed_Tree:
    def __init__(self, n):
        self.size = n
        self.tree = [0 for _ in range(n+1)]

    # a[i]にxを加算(1 <= i <= n) 1-indexed
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & (-i)

    # a[1] から a[t] までの合計を得る (1 <= t <= n)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)

        return s




class RangeUpdate:
    def __init__(self, n):
        self.p = Binary_Indexed_Tree(n + 1)
        self.q = Binary_Indexed_Tree(n + 1)

    # a[s] から a[t] まで一律xを加算 (1 <= s <= t <= n)
    def add(self, s, t, x):
        t += 1
        self.p.add(s, -x * s)
        self.p.add(t, x * t)
        self.q.add(s, x)
        self.q.add(t, -x)

    # a[s] から a[t] までの合計を得る (1 <= s <= t <= n)
    def sum(self, s, t):
        t += 1
        return self.p.sum(t) + self.q.sum(t) * t - self.p.sum(s) - self.q.sum(s) * s

alpha_small_dict = {chr(i):i-97 for i in range(97, 97+26)} #辞書ver
n = int(input())
S = input()
data = [[0 for i in range(n)] for j in range(26)]

bit = [RangeUpdate(n) for i in range(26)]
for i,x in enumerate(S):
    bit[alpha_small_dict[x]].add(i+1,i+1,1)
    data[alpha_small_dict[x]][i] = 1
q = int(input())
for i in range(q):
    x,y,z = input().split()
    x,y = int(x),int(y)
    #print(x,y,z)
    if x == 1:
        num = alpha_small_dict[z]
        for j in range(26):
            if data[j][y-1] == 1:
                data[j][y-1] = 0
                bit[j].add(y,y,-1)
                break
        data[num][y-1] = 1
        bit[num].add(y,y,1)
    else:
        z = int(z)
        ans = 0
        for j in range(26):
            if bit[j].sum(y,z) >= 1:
                ans += 1
        print(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,s,t=input().split()
    if a=='1':
        s=int(s)
        update(s-1,t)
    if a=='2':
        s=int(s)
        t=int(t)
        print(len(query(s-1,t)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
Q = int(input())
for i in range(Q):
    l = input().split()
    if l[0] == '1':
        l[0] = int(l[0])
        l[1] = int(l[1])
        S[l[1] - 1] = l[2]
    else:
        l = list(map(int, l))
        string_list = list(S[(l[1] - 1):(l[2])])
        ans = len(set(string_list))
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
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(set(s for s in S[b:c])))

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:
def f7(seq):
    seen = set()
    seen_add = seen.add
    return [ x for x in seq if x not in seen and not seen_add(x)]
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(f7(S[i:int(c)])))
    else:S[i]=c

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 e in s[3:]:
    a,b,c = map(str, e.split())
    if a == "1":
        update(int(b)-1, c)
    else:
        print(query(int(b)-1, int(c)))

Submission status: Time Limit Exceeded

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

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 _ in range(Q):
    a,b,c = map(str, input().split())
    if a == "1":
        update(int(b)-1, c)
    else:
        print(query(int(b)-1, int(c)))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

class Bit:
    def __init__(self, n,ls):
        self.size=n
        self.tree=[Counter() for _ in range(n+1)]
        self.ls=['']*(n+1)

    def sum(self, i, j):
        i-=1
        res=Counter()
        while j>0:
            res += self.tree[j]
            j -= j&-j
        while i>0:
            res -= self.tree[i]
            i -= i&-i
        return len(res)
    
    def add(self, i, x):
        self.ls[i] = x
        while i <= self.size:
            self.tree[i][x]+=1
            i += i & -i

    def change(self, i, x):
        original = self.ls[i]
        self.ls[i]=x
        while i <= self.size:
            self.tree[i][original] -=1
            self.tree[i][x] +=1
            i += i & -i
        

n = int(input())
s = list(input())
bit=Bit(n,s)

for i in range(n):
    bit.add(i+1, s[i])

q = int(input())
for _ in range(q):
    query, a, b = input().split()
    if query=='1':
        bit.change(int(a),b)
    else:
        ans=bit.sum(int(a), int(b))
        print(ans)

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:
def q1(i, c):
  s[i-1] = c
  return
  
def q2(l, r):
  if (r-l):
    substr = s[(l-1):r]
  else:
    return 1
  return len(set(substr))

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

q = []
t = []
for _ in range(nq):
  l = list(input().split())
  if l[0]=='1':
    q1(int(l[1]), l[2])
  else:
    print(q2(int(l[1]), int(l[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
  elif a=='2':
    temp = set(S[int(b)-1:int(c)])
    print(len(temp))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    S = input()
    q = int(input())
    for _ in range(q):
        t, i, c = input().split()
        if t == '1':
            S = S[:int(i)-1] + c + S[int(i):] 
        else:
            print(len(set(S[int(i)-1:int(c)])))
        
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections

N = int(input())
S = input()
Q = int(input())
query = []
for _ in range(Q):
    query.append(list(input().split()))

#print(len(collections.Counter(S[2:6]).most_common()))

#print(query)
for q in query:
    if q[0] == "1":
        S = S[:(int(q[1])-1)]+q[2]+S[int(q[1]):]
    else:
        print(len(collections.Counter(S[int(q[1])-1:int(q[2])]).most_common()))
#print(S)

Submission status: Time Limit Exceeded

Solution code:
import sys
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
s = list(S())
Q = I()
que = [SL() for i in range(Q)]
for a,b,c in que:
  if a == "1":
    s[int(b)-1] = c
  else:
    #print(s[int(b)-1:int(c)])
    print(len(set(s[int(b)-1:int(c)])))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
S = [''] + list(input())
Q = int(input())
Query = []
for _ in range(Q):
    Query.append(list(input().split()))
res = []
for q in Query:
#    print(S,q)
    if q[0]=='1':
        S[int(q[1])] = q[2]
    else:
        res.append(str(len(set(S[int(q[1]):int(q[2])+1]))))
print('\n'.join(res))

Submission status: Time Limit Exceeded

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

    for q in range(Q):
        query = input().split()
        for idx in range(3):
            try:
                query[idx]=int(query[idx])
            except:
                pass

        if query[0] == 1:
            S[query[1]-1] = query[2]
        else:
            l = S[query[1]-1: query[2]]
            l.sort()
            cnt = 1
            for i in range(1,len(l)):
                if l[i-1]!=l[i]: cnt += 1
            print(cnt)


    return

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q = int(input())
for i in range(q):
    a1,a2,a3 = map(str, input().split())
    if a1 == '2':
        print(len(set(s[int(a2)-1:int(a3)])))
    else:
        s[int(a2)-1] = a3

Submission status: Time Limit Exceeded

Solution code:
def case1(li, x, c):
    li[x-1] = c
    return li


def case2(li, start, end):
    s = set(li[start-1:end])
    print(len(s))


i = int(input())  # skip this
char_list = [x for x in input()]
Q = int(input())

for i in range(Q):
    tokens = [int(x) if x.isdigit() else x for x in input().split()]
    if tokens[0] == 1:
        char_list = case1(char_list, tokens[1], tokens[2])
    elif tokens[0] == 2:
        case2(char_list, tokens[1], tokens[2])

Submission status: Time Limit Exceeded

Solution code:
# from math import sqrt
# from heapq import heappush, heappop
# from collections import deque
from functools import reduce


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

    for i in range(Q):
        query = input().split()
        if query[0] == '1':
            i = int(query[1]) - 1
            c = query[2]
            S[i] = c
        else:
            l = int(query[1]) - 1
            r = int(query[2])
            s = set()
            for c in S[l:r]:
                s.add(c)
            print(len(s))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, a):      
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        l = []
        for _a in a:
            l.append({'dic':{_a:1}, 'set':set(_a)})
        self.data = [{'dic':{}, 'set':set()} for i in range(self.N-1)] + l + [{'dic':{}, 'set':set()} for i in range(self.N-self.n)]
        for i in range(2*self.N-2, 0, -2):
            self.data[(i-1)//2] = self.init_func(self.data[i], self.data[i-1])
    
    def init_func(self, data1, data2):
        s = data1['set'].copy()
        d = data1['dic'].copy()
        for k in data2['dic']:
            if k in d:
                d[k] += data2['dic'][k]
            else:
                d[k] = data2['dic'][k]
                s.add(k)
        return {'dic':d, 'set':s}
    
    def func(self, idx, x1, x2):
        self.data[idx]['dic'][x1] -= 1
        self.data[idx]['set'].add(x2)
        if self.data[idx]['dic'][x1] == 0:
            self.data[idx]['set'].remove(x1)
        if x2 in self.data[idx]['dic']:
            self.data[idx]['dic'][x2] += 1
        else:
            self.data[idx]['dic'][x2] = 1
    
    def update(self, i, x):
        idx = self.N - 1 + i
        pre = list(self.data[idx]['dic'].keys())[0]
        self.data[idx] = {'dic':{x:1}, 'set':set(x)}
        while idx:
            idx = (idx-1) // 2
            self.func(idx, pre, x)
    
    def query(self, i, j):
        # [i, j)
        if i == j:
            return len(self.data[self.N - 1 + i]['set'])
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = set()
            while idx1 + 1 < idx2:
                if idx1&1 == 0: # idx1が偶数
                    result = result | self.data[idx1]['set']
                if idx2&1 == 1: # idx2が奇数
                    result = result | self.data[idx2]['set']
                    idx2 -= 1
                
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            
            if idx1 == idx2:
                result = result | self.data[idx1]['set']
            else: # idx1 + 1 == idx2
                result = result | self.data[idx1]['set'] | self.data[idx2]['set']
            
            return len(result)

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

Q = int(input())
for i in range(Q):
  t, a, b = input().split()
  if t == '1':
    a = int(a)
    if S[a-1] == b:
      continue
    st.update(a-1, b)
    S[a-1] = b
  else:
    a, b = int(a), int(b)
    print(st.query(a-1, b))