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(str(input()))

def ordN(x):
  return ord(x) - ord('a')

li = [[] for _ in range(26)]
for i,s in enumerate(S):
  li[ordN(s)].append(i)

for i in range(int(input())):
  Q1, Q2, Q3 = input().split()
  if Q1 == "1":
    Q2 = int(Q2) - 1
    if S[Q2] != Q3:
      li[ordN(S[Q2])] = [n for n in li[ordN(S[Q2])] if n != Q2]
      li[ordN(Q3)].append(Q2)
      S[Q2] = Q3
  else:
    Q2, Q3 = int(Q2)-1, int(Q3)-1
    count = 0
    for j in range(26):
      if [True for n in li[j] if Q2 <= n and n <= Q3]:
        count += 1
    print(count)

Submission status: Time Limit Exceeded

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

ans = []
for i in range(Q):
    que = list(input().split())
    if que[0] == '1':
        s[int(que[1])-1] = que[2]
    if que[0] == '2':
        ans.append(len(set(s[int(que[1])-1:int(que[2])])))

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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

ques = []
for i in range(Q):
    ques.append(list(input().split()))

for que in ques:
    if que[0] == '1':
        s[int(que[1])-1] = que[2]
    if que[0] == '2':
        print(len(set(s[int(que[1])-1:int(que[2])])))

Submission status: Time Limit Exceeded

Solution code:
from bisect import insort_left, bisect_left
n = int(input())
s = list(input())
Q = int(input())
query = [input() for _ in range(Q)]
dic = {chr(i+ord('a')):[] for i in range(26)}
for ind, c in enumerate(s):
    dic[c].append(ind)

for q in query:
    t, a, b = q.split()
    a = int(a)-1
    if t=='1':
        if s[a]==b:
            continue
        dic[s[a]].remove(a)
        insort_left(dic[b], a)
        s[a] = b
    else:
        b = int(b)-1
        tmp = 0
        for li in dic.values():
            if li and a<=li[-1] and li[bisect_left(li, a)] <= b:
                tmp += 1
        print(tmp)

Submission status: Time Limit Exceeded

Solution code:
from bisect import insort_left, bisect_left
n = int(input())
s = list(input())
q = int(input())
dic = {chr(i+ord('a')):[] for i in range(26)}
for ind, c in enumerate(s):
    dic[c].append(ind)

for _ in range(q):
    t, a, b = input().split()
    a = int(a)-1
    if t=='1':
        if s[a]==b:
            continue
        dic[s[a]].remove(a)
        insort_left(dic[b], a)
        s[a] = b
    else:
        b = int(b)-1
        tmp = 0
        for li in dic.values():
            if li and a<=li[-1] and li[bisect_left(li, a)] <= b:
                tmp += 1
        print(tmp)

Submission status: Time Limit Exceeded

Solution code:
from bisect import insort_left, bisect_left
n = int(input())
s = input()
q = int(input())
dic = {chr(i+ord('a')):[] for i in range(26)}
for ind, c in enumerate(s):
    dic[c].append(ind+1)

for _ in range(q):
    t, a, b = input().split()
    a = int(a)
    if t=='1':
        for li in dic.values():
            if a in li:
                li.remove(a)
                break
        insort_left(dic[b], a)
    else:
        b = int(b)
        tmp = 0
        for li in dic.values():
            if li and a<=li[-1] and li[bisect_left(li, a)] <= b:
                tmp += 1
        print(tmp)

Submission status: Time Limit Exceeded

Solution code:
from bisect import insort_left, bisect_left
n = int(input())
s = input()
q = int(input())
dic = {chr(i+ord('a')):[] for i in range(26)}
for ind, c in enumerate(s):
    dic[c].append(ind)

for _ in range(q):
    t, a, b = input().split()
    a = int(a)-1
    if t=='1':
        for c, li in dic.items():
            if a in li:
                li.remove(a)
            if c==b:
                insort_left(li, a)
    else:
        b = int(b)-1
        tmp = 0
        for li in dic.values():
            if li and a<=li[-1] and li[bisect_left(li, a)] <= b:
                tmp += 1
        print(tmp)

Submission status: Time Limit Exceeded

Solution code:
from bisect import insort_left, bisect_left, bisect_right
n = int(input())
s = input()
q = int(input())
dic = {chr(i+ord('a')):[] for i in range(26)}
for ind, c in enumerate(s):
    dic[c].append(ind)

for _ in range(q):
    t, a, b = input().split()
    a = int(a)-1
    if t=='1':
        for c, li in dic.items():
            if a in li:
                li.remove(a)
            if c==b:
                insort_left(li, a)
    else:
        b = int(b)-1
        tmp = 0
        for li in dic.values():
            if bisect_left(li, a) < bisect_right(li, b):
                tmp += 1
        print(tmp)

Submission status: Time Limit Exceeded

Solution code:
from bisect import insort_left, bisect_left, bisect_right
n = int(input())
s = input()
q = int(input())
dic = {}
for ind, c in enumerate(s):
    if c in dic:
        dic[c].append(ind)
    else:
        dic[c] = [ind]

for _ in range(q):
    t, a, b = input().split()
    a = int(a)-1
    if t=='1':
        find_c = False
        for c, li in dic.items():
            if a in li:
                li.remove(a)
            if c==b:
                insort_left(li, a)
                find_c = True
        if not find_c:
            dic[b] = [a]
        dic = {c:li for c, li in dic.items() if len(li)>0}
    else:
        b = int(b)-1
        tmp = 0
        for li in dic.values():
            if bisect_left(li, a) < bisect_right(li, b):
                tmp += 1
        print(tmp)

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    def __init__(self, n):
        self.node = [ 0 for _ in range(n+1) ]

    def add(self, idx, w):
        i = idx
        while i < len(self.node) - 1:
            self.node[i] += w
            i |= (i + 1)

    def sum_(self, idx):
        ret, i = 0, idx-1
        while i >= 0:
            ret += self.node[i]
            i = (i & (i + 1)) - 1
        return ret

    def sum(self, l, r):
        return self.sum_(r) - self.sum_(l)


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

tree = [ BIT(n) for _ in range(26) ]
for i in range(n):
    tree_id = ord(s[i]) - ord("a")
    tree[tree_id].add(i, 1)

for _ in range(q):
    query = input().split()
    com = int(query[0])
    if com == 1:
        idx, new_char = int(query[1]), query[2]
        idx -= 1
        old_char = s[idx]
        new_id = ord(new_char) - ord("a")
        old_id = ord(old_char) - ord("a")

        tree[old_id].add(idx, -1)
        tree[new_id].add(idx, 1)
        s[idx] = new_char

    if com == 2:
        l, r = int(query[1]), int(query[2])
        ret = 0
        for c in range(26):
            if tree[c].sum(l-1, r) > 0:
                ret += 1
        print(ret)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
Q=int(input())
d={}
AA=ord('a')
alp=[[] for i in range(26)]
for i in range(N):
    d[i]=S[i]
    x=ord(S[i])-AA
    alp[x].append(i)
import bisect
#print(alp)
for _ in range(Q):
    Query=list(input().split())
    if Query[0]=='1':
        x=ord(Query[2])-AA
        b=int(Query[1])-1
        bisect.insort(alp[x],b)

        e=ord(d[b])-AA
        d[b]=Query[2]
        alp[e].pop(bisect.bisect_left(alp[e],b))
        #print(alp, d)
    else:
        tmp=0
        for a in alp:
            if bisect.bisect_right(a,int(Query[2])-1)>bisect.bisect_left(a,int(Query[1])-1):
                tmp+=1
                #print("{} exists".format(alp.index(a)))
        print(tmp)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
Q=int(input())
d={}
alp=[[] for i in range(26)]
for i in range(N):
    d[i]=S[i]
    x=ord(S[i])-ord('a')
    alp[x].append(i)
import bisect
#print(alp)
for _ in range(Q):
    Query=list(input().split())
    if Query[0]=='1':
        x=ord(Query[2])-ord('a')
        b=int(Query[1])-1
        bisect.insort(alp[x],b)

        e=ord(d[b])-ord('a')
        d[b]=Query[2]
        f=bisect.bisect_left(alp[e],b)
        alp[e].pop(f)
        #print(alp, d)
    else:
        tmp=0
        x=int(Query[1])-1
        y=int(Query[2])-1
        for a in alp:
            xx=bisect.bisect_left(a,x)
            yy=bisect.bisect_right(a,y)
            if yy>xx:
                tmp+=1
                #print("{} exists".format(alp.index(a)))
        print(tmp)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
Q=int(input())
d={}
alp=[[] for i in range(26)]
for i in range(N):
    d[i]=S[i]
    x=ord(S[i])-ord('a')
    alp[x].append(i)
import bisect
#print(alp)
for _ in range(Q):
    Query=list(input().split())
    if Query[0]=='1':
        x=ord(Query[2])-ord('a')
        b=int(Query[1])-1
        bisect.insort(alp[x],b)

        e=ord(d[b])-ord('a')
        d[b]=Query[2]
        f=bisect.bisect_left(alp[e],b)
        del alp[e][f]
        #print(alp, d)
    else:
        tmp=0
        x=int(Query[1])-1
        y=int(Query[2])-1
        for a in alp:
            xx=bisect.bisect_left(a,x)
            yy=bisect.bisect_right(a,y)
            if yy>xx:
                tmp+=1
                #print("{} exists".format(alp.index(a)))
        print(tmp)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import collections

def intOrStr(a):
    try:
        return int(a)
    except:
        return str(a)

N = int(input())
S = list(input())
Q = int(input())
for _ in range(Q):
    Q1, Q2, Q3 = map(intOrStr, input().split())
    if Q1 == 1:
        S[Q2-1] = Q3
    else:
        print(len(collections.Counter(S[Q2-1: Q3])))

Submission status: Time Limit Exceeded

Solution code:
import collections

N = int(input())
S = list(input())
Q = int(input())
for _ in range(Q):
    Q1, Q2, Q3 = map(str, input().split())
    if Q1 == '1':
        S[int(Q2)-1] = Q3
    else:
        print(len(collections.Counter(S[int(Q2)-1: int(Q3)])))

Submission status: Time Limit Exceeded

Solution code:
class BinaryIndexedTree():
    def __init__(self, num):
        self.bit = [0]*(num+1) # 1-indexed
        self.num = num

    def sum(self, i):
        i += 1
        res = 0
        while (i > 0):
            res += self.bit[i]
            i -= i & -i
        return res
    
    def add(self, i, target):
        i += 1
        while i <= self.num:
            self.bit[i] += target
            i += i & -i
    
    # [l, r) 
    def query(self, l, r):
        return self.sum(r-1) - self.sum(l-1)

def main():
    N = int(input())
    S = list(input())
    Q = int(input())
    anss = []
    bits = [BinaryIndexedTree(N) for i in range(26)]

    for index, c in enumerate(S):
        bits[ord(c) - ord('a')].add(index, 1)
    
    for _ in range(Q):
        query = input().split()
        if query[0] == "1":
            index = int(query[1]) - 1
            target = query[2]
            if S[index] == target:
                continue
            else:
                bits[ord(S[index])-ord('a')].add(index, -1)
                S[index] = target
                bits[ord(target)-ord('a')].add(index, 1)
        else:
            l, r = map(int, query[1:])
            l-= 1; r-= 1
            ans = 0
            for i in range(26):
                if bits[i].query(l, r+1) > 0:
                    ans += 1
            anss.append(ans)
    print(*anss, sep="\n")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

#bottom-up query
class SegmentTree():
    def __init__(self, num, segfunc, ide_ele):
        length = 2 ** (num-1).bit_length()
        self.n = num
        self.func = segfunc
        self.seg = [ide_ele] * 2 * length
        self.ide_ele = ide_ele
    
    def update(self, index, target):
        index += self.n - 1
        self.seg[index] = target
        while (index > 0):
            index = (index - 1) // 2
            self.seg[index] = self.func(self.seg[index*2 + 1], self.seg[index*2 + 2])
    
    # [l, r)
    def quary(self, l, r):
        l += self.n - 1
        r += self.n - 1
        res = self.ide_ele
        while l < r :
            if l & 1 == 0:
                res = self.func(res, self.seg[l])
            if r & 1 == 0:
                res = self.func(res, self.seg[r-1])
            l = l // 2
            r = (r-1) // 2
        return res

def main():
    N = int(input())
    S = list(input())
    Q = int(input())
    anss = []
    ide_ele = 10 ** 9
    segs = [SegmentTree(N, min, ide_ele) for i in range(26)]
    for index, c in enumerate(S):
        segs[ord(c) - ord('a')].update(index, index)
    
    for _ in range(Q):
        query = input().split()
        if query[0] == "1":
            index = int(query[1]) - 1
            target = query[2]
            if S[index] == target:
                continue
            else:
                segs[ord(S[index])-ord('a')].update(index, ide_ele)
                S[index] = target
                segs[ord(target)-ord('a')].update(index, index)
        else:
            l, r = map(int, query[1:])
            l-= 1; r-= 1
            ans = 0
            for i in range(26):
                if segs[i].quary(l, r+1) <= r:
                    ans += 1
            anss.append(ans)
    print(*anss, sep="\n")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import time
from collections import deque
from collections import defaultdict
from copy import deepcopy
import heapq
import random
import string

mod = 10 ** 9 + 7
t = time.time()

def randomname(n):
   randlst = [random.choice(string.ascii_letters) for i in range(n)]
   return ''.join(randlst).lower()


def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret


def conbination(n, r, mod):
    if n < r:
        return 0

    if r == 0 or n == 0:
        return 1

    ret = 1
    for i in range(n-r+1, n+1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r+1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    #print(f"conbination {n}, {r} = {ret}")
    return ret

def inv(n, mod):
    return power(n, mod-2)

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p//2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod


def main():
    N = iip()
    S = input()
    Q = iip()
    #S = randomname(10**5)
    #N = len(S)
    #Q = 10000
    rw = ruisekiwa(S, N)
    query_list = []
    #print(ruisekiwa(S, N))

    for i in range(Q):
        query_list.append(input().split())
        #query_list.append(("1", random.randint(0,10**5), randomname(1)))
        #query_list.append(("2", random.randint(0, 10**4), random.randint(10**4+1, 10**5)))

    changelist = []
    outlist = []
    for k, query in enumerate(query_list):
        #if k % 1000 == 0:
        #    print(k)
        if query[0] == "1":
            for i, change in enumerate(changelist):
                if change[0] == int(query[1])-1:
                    changelist.pop(i)
                    break
            changelist.append((int(query[1])-1, query[2]))

        if query[0] == "2":
            left = int(query[1])-1
            right = int(query[2])-1

            if left == 0:
                leftitem = defaultdict(int)
            else:
                leftitem = deepcopy(rw[left-1])

            item = defaultdict(int)
            for char, value in  rw[right].items():
                item[char] = value - leftitem[char]

            for position, value in changelist:
                if left <= position and position <= right:
                    item[value] += 1
                    item[S[position]] -=1

            result = 0
            for value in item.values():
                if value>=1:
                    result += 1
            outlist.append(str(result))
    print("\n".join(outlist))

            #print(item)


def ruisekiwa(S, N):
    ret = []
    inner = defaultdict(int)
    for i in range(N):
        inner[S[i]] += 1
        ret.append(deepcopy(inner))
    return ret


main()

Submission status: Time Limit Exceeded

Solution code:
import math
import time
from collections import deque
from collections import defaultdict
from copy import deepcopy
import heapq

mod = 10 ** 9 + 7
t = time.time()



def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret


def conbination(n, r, mod):
    if n < r:
        return 0

    if r == 0 or n == 0:
        return 1

    ret = 1
    for i in range(n-r+1, n+1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r+1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    #print(f"conbination {n}, {r} = {ret}")
    return ret

def inv(n, mod):
    return power(n, mod-2)

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p//2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod

def main():
    N = iip()
    S = input()
    rw = ruisekiwa(S, N)
    Q = iip()
    query_list = []
    #print(ruisekiwa(S, N))

    for i in range(Q):
        query_list.append(input().split())

    changelist = []
    for query in query_list:
        if query[0] == "1":
            for i, change in enumerate(changelist):
                if change[0] == int(query[1])-1:
                    changelist.pop(i)
                    break
            changelist.append((int(query[1])-1, query[2]))

        if query[0] == "2":
            left = int(query[1])-1
            right = int(query[2])-1

            if left == 0:
                leftitem = defaultdict(int)
            else:
                leftitem = deepcopy(rw[left-1])

            item = defaultdict(int)
            for char, value in  rw[right].items():
                item[char] = value - leftitem[char]

            for position, value in changelist:
                if left <= position and position <= right:
                    item[value] += 1
                    item[S[position]] -=1

            result = 0
            for value in item.values():
                if value>=1:
                    result += 1
            print(result)

            #print(item)







def ruisekiwa(S, N):
    ret = []
    inner = defaultdict(int)
    for i in range(N):
        inner[S[i]] += 1
        ret.append(deepcopy(inner))
    return ret


main()

Submission status: Time Limit Exceeded

Solution code:
class SegTree:

    def __init__(self, N, S):
        self.N = 1
        while self.N < N:
            self.N *= 2
        self.tree = [set() for i in range(2 * self.N - 1)]
        for i in range(len(S)):
            self.tree[self.N - 1 + i] = set(S[i])
        for i in range(self.N - 2, -1, -1):
            self.tree[i] = self.tree[i * 2 + 1] | self.tree[i * 2 + 2]

    def update(self, index, char):
        i = self.N - 1 + index
        self.tree[i] = set(char)

        while i > 0:
            i = (i - 1) // 2
            self.tree[i] = self.tree[i * 2 + 1] | self.tree[i * 2 + 2]

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

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return set()

        if a <= l and r <= b:
            return self.tree[k]

        left = self.query(a, b, 2 * k + 1, l, (l + r) // 2)
        right = self.query(a, b, 2 * k + 2, (l + r) // 2, r)
        return left | right


def solve():

    N = int(input())
    S = list(input())
    tree = SegTree(N, S)

    Q = int(input())
    for _ in range(Q):
        t_q, in_1, in_2 = input().split()
        if t_q == '1':
            i_q = int(in_1)
            c_q = in_2
            tree.update(i_q-1, c_q)
        elif t_q == '2':
            l_q = int(in_1)
            r_q = int(in_2)
            print(len(tree.get(l_q-1, r_q)))


solve()

Submission status: Time Limit Exceeded

Solution code:
class SegTree:

    def __init__(self, N):
        self.N = 1
        while self.N < N:
            self.N *= 2
        self.tree = [set() for i in range(2 * self.N - 1)]

    def update(self, index, char):
        i = self.N - 1 + index
        self.tree[i] = set(char)

        while i > 0:
            i = (i - 1) // 2
            left = self.tree[i * 2 + 1]
            right = self.tree[i * 2 + 2]
            self.tree[i] = left | right

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

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return set()

        if a <= l and r <= b:
            return self.tree[k]

        left = self.query(a, b, 2 * k + 1, l, (l + r) // 2)
        right = self.query(a, b, 2 * k + 2, (l + r) // 2, r)
        return left | right


def solve():

    N = int(input())
    tree = SegTree(N)

    S = list(input())
    for i in range(N):
        tree.update(i, S[i])

    Q = int(input())
    for _ in range(Q):
        t_q, in_1, in_2 = input().split()
        if t_q == '1':
            i_q = int(in_1)
            c_q = in_2
            tree.update(i_q-1, c_q)
        elif t_q == '2':
            l_q = int(in_1)
            r_q = int(in_2)
            print(len(tree.get(l_q-1, r_q)))


solve()

Submission status: Time Limit Exceeded

Solution code:
class SegTree:

    def __init__(self, N):
        self.N = 1
        while self.N < N:
            self.N *= 2
        self.tree = [{} for i in range(2 * self.N - 1)]

    def update(self, index, char):
        i = self.N - 1 + index
        assert len(self.tree[i]) <= 1

        if len(self.tree[i]) == 1:
            old_char, _ = self.tree[i].popitem()
            new_char = char
            self.tree[i][new_char] = 1

            while i > 0:
                i = (i - 1) // 2
                assert old_char in self.tree[i] and self.tree[i][old_char] > 0
                self.tree[i][old_char] -= 1
                self.tree[i][new_char] = self.tree[i].get(new_char, 0) + 1

        else:
            self.tree[i][char] = 1

            while i > 0:
                i = (i - 1) // 2
                self.tree[i][char] = self.tree[i].get(char, 0) + 1
    
    def get(self, a, b):
        return self.query(a, b, 0, 0, self.N)

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return {}

        if a <= l and r <= b:
            return self.tree[k].copy()

        left = self.query(a, b, 2 * k + 1, l, (l + r) // 2)
        right = self.query(a, b, 2 * k + 2, (l + r) // 2, r)
        res = left
        for char in right.keys():
            res[char] = res.get(char, 0) + right[char]
        return res


def solve():

    N = int(input())
    tree = SegTree(N)

    S = list(input())
    for i in range(N):
        tree.update(i, S[i])

    Q = int(input())
    for _ in range(Q):
        t_q, in_1, in_2 = input().split()
        if t_q == '1':
            i_q = int(in_1)
            c_q = in_2
            tree.update(i_q-1, c_q)
        elif t_q == '2':
            l_q = int(in_1)
            r_q = int(in_2)
            dic = tree.get(l_q-1, r_q)
            res = 0
            for char in dic.keys():
                if dic[char] > 0:
                    res += 1
            print(res)


solve()

Submission status: Time Limit Exceeded

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

def ci(c):
  return "abcdefghijklmnopqrstuvwxyz".find(c)

N=int(input())
S=[ci(c) for c in str(input())]+[0]
Q=int(input())

C=[[0]*26 for _ in range(N+1)]
for i in range(N):
  for j in range(26):
    C[i][j]=C[i-1][j]
  C[i][S[i]]+=1

L=list()

for i in range(Q):
  t,x,y=input().split()
  if t=='1':
    L.append([int(x)-1,ci(y)])
  else:
    t,l,r=0,int(x)-1,int(y)-1
    c=[0]*26
    for x,j in L:
      if l<=x and x<=r:
        c[j]+=1
        c[S[x]]-=1
    for j in range(26):
      if C[r][j]-C[l-1][j]+c[j]>0:
        t+=1
    print(t)

Submission status: Time Limit Exceeded

Solution code:
#https://tjkendev.github.io/procon-library/python/range_query/rmq_segment_tree.html
# N: 処理する区間の長さ

# 中身は追えてない
#bit管理,26個作るより速いだろう
#演算はor

N = int(input())
s = input()


N0 = 2**(N-1).bit_length()
INF = 0
data = [0]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = 1<<x
    while k >= 0:
        k = (k - 1) // 2
        data[k] =data[2*k+1]|data[2*k+2]
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = s|data[R-1]

        if L & 1:
            s = s|data[L-1]
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(N):
    update(i,ord(s[i])-ord("a"))
q = int(input())
for j in range(q):
    t,l,r = input().split( )
    if t=="1":
        update(int(l)-1,ord(r)-ord("a"))
        
    else:
        bit = bin(query(int(l)-1,int(r)))[2:]
        ans = 0
        for i in bit:
            ans += int(i)
        print(ans)

Submission status: Time Limit Exceeded

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

A=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]

n=1
while n<N:
    n*=2

seg=[set() for i in range(n*2)]
#print(seg)

for i in range(N):
    seg[n-1+i]=set(S[i])
    k=n-1+i
    while k>0:
        k=(k-1)//2
        seg[k]=(seg[k*2+1]|seg[k*2+2])
#print(seg)

#0indexでa番目の値をbに変更
def update(a,b):
    a+=n-1
    seg[a]=set(b)
    while a>0:
        a=(a-1)//2
        seg[a]=(seg[a*2+1]|seg[a*2+2])

#print(seg)

#A～B-1(0-index)までの累積和を求める
#1～2までの累積和なら(1,3,0,0,n)
#Kは接点番号？L,Rはその接点が[L,R)に対応づいていることを表す？
#外部からはquery(A,B,0,0,n)として呼び出す
def query(A,B,K,L,R):
    if K>=len(seg):
        return set()
    if R<=A or B<=L:
        return set()
    elif A<=L and R<=B:
        return seg[K]
    else:
        vl=query(A,B,K*2+1,L,(L+R)//2)
        vr=query(A,B,K*2+2,(L+R)//2,R)
        #print(vl,vr)
        return vl|vr
#print(n,len(seg))
#print("P",query(2,4,0,0,n),len(query(2,4,0,0,n)))
#update(3,"a")
#print(seg)
#print(query(2,4,0,0,n))
for i in range(Q):
    x,y,z=list(input().split())
    if x=="1":
        update(int(y)-1,z)
    else:
        print(len(query(int(y)-1,int(z),0,0,n)))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

for i in range(Q):
    a, b, c = input().split()
    if a == "1":
        S[int(b)-1] = c
    else:
        count = Counter([S[i] for i in range(int(b)-1, int(c))])
        print(len(count))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

for i in range(Q):
    a, b, c = input().split()
    if a == "1":
        S[int(b)-1] = c
    else:
        count = Counter(S[int(b)-1:int(c)])
        print(len(count))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys

DEBUG = False


class SegmentTree:

    # Use 1-based index internally
    def __init__(self, n, merge_func, fillval=sys.maxsize):
        self.n = 1
        while self.n < n:
            self.n *= 2
        self.nodes = [fillval] * (self.n * 2 - 1 + 1)  # +1 for 1-based index
        self.merge_func = merge_func
        self.fillval = fillval
    
    def update(self, idx, val):
        idx += 1  # for 1-based index

        nodes = self.nodes
        mergef = self.merge_func

        idx += self.n - 1
        nodes[idx] = val
        while idx > 1: # > 1 for 1-based index
            idx >>= 1  # parent(idx) = idx >> 1 for 1-based index segment tree
            nodes[idx] = mergef(nodes[idx << 1], nodes[(idx << 1) + 1]) # child(idx) = idx << 1 and idx << 1 + 1
    
    def query(self, l, r):
        l += 1; r += 1  # for 1-based index

        l += self.n - 1
        r += self.n - 1
        acc = self.fillval
        while l < r:
            if l & 1:
                acc = self.merge_func(acc, self.nodes[l])
                l += 1
            if r & 1:
                acc = self.merge_func(acc, self.nodes[r - 1])
                r -= 1
            l >>= 1
            r >>= 1
        return acc

def read(t = str):
    return t(sys.stdin.readline().rstrip())

def read_list(t = str, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return


def main():
    read()
    s = read()

    a_ord = ord("a")
    bit_offsets = {chr(c_ord): c_ord - a_ord for c_ord in range(ord("a"), ord("z") + 1)}

    apps = SegmentTree(len(s), lambda x, y: x | y, 0)
    i = 0
    for c in s:
        apps.update(i, 1 << bit_offsets[c])
        i += 1

    nr_q = read(int)
    for i in range(0, nr_q):
        q = read_list()
        if q[0] == "1":
            _, i, c = q  # i_q in the question starts from 1, not 0
            apps.update(int(i) - 1, 1 << bit_offsets[c])
        else:
            _, l, r = q  # l_q and r_q in the question start from 1, not 0
            print(bin(apps.query(int(l) - 1, int(r) - 1 + 1)).count("1"))  # query in the question includes both edges


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
qn = int(input())
for i in range(qn):
    t, t1, t2 = input().split()
    t1 = int(t1) - 1
    if t == '1': s[t1] = t2
    else: print(len(set(s[t1:int(t2)])))