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 math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()


class Node:
    def __init__(self, x):
        self.data = x
        self.priority = random.random()
        self.left = None
        self.right = None


def rotate_right(node):
    l_node = node.left
    node.left = l_node.right
    l_node.right = node
    return l_node


def rotate_left(node):
    r_node = node.right
    node.right = r_node.left
    r_node.left = node
    return r_node


def search_min(node):
    while node.left is not None:
        node = node.left
    return node.data


def traverse_(node):
    if node is not None:
        for x in traverse_(node.left):
            yield x
        yield node.data
        for x in traverse_(node.right):
            yield x


class Treap:
    """
    動的ランダム二分探索木の中の一つ。構築:O(nlogn), 他の操作:期待値O(logn)
    """

    def __init__(self):
        self.root = None

    def search(self, x):
        def search_(node, x):
            while node is not None:
                if x == node.data:
                    return True
                elif x < node.data:
                    node = node.left
                else:
                    node = node.right
            return False

        return search_(self.root, x)

    def insert(self, x):
        def insert_(node, x):
            if node is None:
                return Node(x)
            elif x == node.data:
                return node
            elif x < node.data:
                node.left = insert_(node.left, x)
                if node.priority > node.left.priority:
                    node = rotate_right(node)
            else:
                node.right = insert_(node.right, x)
                if node.priority > node.right.priority:
                    node = rotate_left(node)
            return node

        self.root = insert_(self.root, x)

    def delete(self, x):
        def delete_(node, x):
            if node is not None:
                if x == node.data:
                    if node.left is None:
                        return node.right
                    elif node.right is None:
                        return node.left
                    else:
                        node.data = search_min(node.right)
                        node.right = delete_(node.right, node.data)
                elif x < node.data:
                    node.left = delete_(node.left, x)
                else:
                    node.right = delete_(node.right, x)
            return node

        self.root = delete_(self.root, x)

    def traverse(self):

        for x in traverse_(self.root):
            yield x

    def lower_bound(self, x):
        def lower_bound_(node, x):
            while node is not None:
                if node.right and node.left:
                    if node.right.data < x:
                        return lower_bound_(node.right, x)
                    elif node.data < x:
                        return min(node.right.data, lower_bound_(node.right, x))
                    else:
                        return min(node.data, lower_bound_(node.left, x))
                elif node.right:
                    if node.right.data < x:
                        return lower_bound_(node.right, x)
                    elif node.data < x:
                        return min(node.right.data, lower_bound_(node.right, x))
                    else:
                        return node.data  # 怪しい！！
                elif node.left:
                    if node.data < x:
                        return INF
                    elif node.left.data < x:
                        return min(node.data, lower_bound_(node.left, x))
                    else:
                        return lower_bound_(node.left, x)
                elif x <= node.data:
                    return node.data
                else:
                    return INF

        if self.root:
            return lower_bound_(self.root, x)
        else:
            return INF

    def upper_bound(self, x):
        def upper_bound_(node, x):
            while node is not None:
                if node.right and node.left:
                    if node.left.data > x:
                        return upper_bound_(node.left, x)
                    elif node.data > x:
                        return max(node.left.data, upper_bound_(node.left, x))
                    else:
                        return max(node.data, upper_bound_(node.right, x))
                elif node.left:
                    if node.left.data > x:
                        return upper_bound_(node.left, x)
                    elif node.data > x:
                        return max(node.left.data, upper_bound_(node.left, x))
                    else:
                        return node.data
                elif node.right:
                    if node.data > x:
                        return -INF
                    elif node.right.data > x:
                        return max(node.data, upper_bound_(node.right, x))
                    else:
                        return upper_bound_(node.right, x)
                elif x >= node.data:
                    return node.data
                else:
                    return -INF

        if self.root:
            return upper_bound_(self.root, x)
        else:
            return -INF

    def __str__(self):
        if self.root is None:
            return "Treap()"
        buff = "Treap("
        for x in traverse_(self.root):
            buff += "%s, " % x
        buff = buff.rstrip(", ")
        buff += ")"
        return buff


N = int(input())
S = input()
Q = int(input())
strings = [Treap() for _ in range(26)]
alphabets = string.ascii_lowercase
check = {}
check2 = {}
for i in range(26):
    check[alphabets[i]] = i
for i in range(N):
    strings[check[S[i]]].insert(i)
for _ in range(Q):
    Query, a, b = map(str, input().split())
    if Query == "1":
        a = int(a)
        if a-1 not in check2:
            strings[check[S[a - 1]]].delete(a - 1)
            strings[check[b]].insert(a - 1)
            check2[a-1] = b
        else:
            strings[check[check2[a-1]]].delete(a - 1)
            strings[check[b]].insert(a - 1)
            check2[a-1] = b
    else:
        a, b = map(int, (a, b))
        ans = 0
        for i in range(26):
            if strings[i].lower_bound(a - 1) <= b - 1:
                ans += 1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()


class Node:
    def __init__(self, x):
        self.data = x
        self.priority = random.random()
        self.left = None
        self.right = None


def rotate_right(node):
    l_node = node.left
    node.left = l_node.right
    l_node.right = node
    return l_node


def rotate_left(node):
    r_node = node.right
    node.right = r_node.left
    r_node.left = node
    return r_node


def search_min(node):
    while node.left is not None:
        node = node.left
    return node.data


def traverse_(node):
    if node is not None:
        for x in traverse_(node.left):
            yield x
        yield node.data
        for x in traverse_(node.right):
            yield x


class Treap:
    """
    動的ランダム二分探索木の中の一つ。構築:O(nlogn), 他の操作:期待値O(logn)
    """

    def __init__(self):
        self.root = None

    def search(self, x):
        def search_(node, x):
            while node is not None:
                if x == node.data:
                    return True
                elif x < node.data:
                    node = node.left
                else:
                    node = node.right
            return False

        return search_(self.root, x)

    def insert(self, x):
        def insert_(node, x):
            if node is None:
                return Node(x)
            elif x == node.data:
                return node
            elif x < node.data:
                node.left = insert_(node.left, x)
                if node.priority > node.left.priority:
                    node = rotate_right(node)
            else:
                node.right = insert_(node.right, x)
                if node.priority > node.right.priority:
                    node = rotate_left(node)
            return node

        self.root = insert_(self.root, x)

    def delete(self, x):
        def delete_(node, x):
            if node is not None:
                if x == node.data:
                    if node.left is None:
                        return node.right
                    elif node.right is None:
                        return node.left
                    else:
                        node.data = search_min(node.right)
                        node.right = delete_(node.right, node.data)
                elif x < node.data:
                    node.left = delete_(node.left, x)
                else:
                    node.right = delete_(node.right, x)
            return node

        self.root = delete_(self.root, x)

    def traverse(self):

        for x in traverse_(self.root):
            yield x

    def lower_bound(self, x):
        def lower_bound_(node, x):
            while node is not None:
                if node.right and node.left:
                    if node.right.data < x:
                        return lower_bound_(node.right, x)
                    elif node.data < x:
                        return min(node.right.data, lower_bound_(node.right, x))
                    else:
                        return min(node.data, lower_bound_(node.left, x))
                elif node.right:
                    if node.right.data < x:
                        return lower_bound_(node.right, x)
                    elif node.data < x:
                        return min(node.right.data, lower_bound_(node.right, x))
                    else:
                        return node.data  # 怪しい！！
                elif node.left:
                    if node.data < x:
                        return INF
                    elif node.left.data < x:
                        return min(node.data, lower_bound_(node.left, x))
                    else:
                        return lower_bound_(node.left, x)
                elif x <= node.data:
                    return node.data
                else:
                    return INF

        if self.root:
            return lower_bound_(self.root, x)
        else:
            return INF

    def upper_bound(self, x):
        def upper_bound_(node, x):
            while node is not None:
                if node.right and node.left:
                    if node.left.data > x:
                        return upper_bound_(node.left, x)
                    elif node.data > x:
                        return max(node.left.data, upper_bound_(node.left, x))
                    else:
                        return max(node.data, upper_bound_(node.right, x))
                elif node.left:
                    if node.left.data > x:
                        return upper_bound_(node.left, x)
                    elif node.data > x:
                        return max(node.left.data, upper_bound_(node.left, x))
                    else:
                        return node.data
                elif node.right:
                    if node.data > x:
                        return -INF
                    elif node.right.data > x:
                        return max(node.data, upper_bound_(node.right, x))
                    else:
                        return upper_bound_(node.right, x)
                elif x >= node.data:
                    return node.data
                else:
                    return -INF

        if self.root:
            return upper_bound_(self.root, x)
        else:
            return -INF

    def __str__(self):
        if self.root is None:
            return "Treap()"
        buff = "Treap("
        for x in traverse_(self.root):
            buff += "%s, " % x
        buff = buff.rstrip(", ")
        buff += ")"
        return buff


N = int(input())
S = input()
Q = int(input())
strings = [Treap() for _ in range(26)]
alphabets = string.ascii_lowercase
check = {}
for i in range(26):
    check[alphabets[i]] = i
for i in range(N):
    strings[check[S[i]]].insert(i)
for _ in range(Q):
    Query, a, b = map(str, input().split())
    if Query == "1":
        a = int(a)
        strings[check[S[a - 1]]].delete(a - 1)
        strings[check[b]].insert(a - 1)
        S = S[:a-1] + b + S[a:]
    else:
        a, b = map(int, (a, b))
        ans = 0
        for i in range(26):
            if strings[i].lower_bound(a - 1) <= b - 1:
                ans += 1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

def resolve():
    N = int(input())
    S = input().strip()
    Q = int(input())
    table = [[] for _ in range(26)]
    for i in range(len(S)):
        ch = S[i]
        bisect.insort(table[ord(ch)-ord('a')], i+1)

    for i in range(Q):
        query = input().strip().split()
        if query[0] == '1':
            pos = int(query[1])
            old_ch = ord(S[pos-1]) - ord('a')
            new_ch = ord(query[2]) - ord('a')
            if old_ch != new_ch:
                bisect.insort(table[new_ch], pos)
                table[old_ch].remove(pos)
                S = S[:pos-1] + query[2] + S[pos:]
        else:
            left = int(query[1])
            right = int(query[2])
            count = 0
            for j in range(26):
                k = bisect.bisect_left(table[j], left)
                if k != len(table[j]) and table[j][k] <= right:
                    count +=1
            print(count)
            
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()


class Node:
    def __init__(self, begin, end):
        self.begin = begin
        self.end = end
        self.left = self.right = self.parent = None
        self.val = set()


class SegmentTree:
    INF = 2 ** 60

    def __init__(self, size):
        self.root = Node(0, size)
        self.leaves = [None] * size

        queue = deque()
        queue.append(self.root)

        while len(queue) > 0:
            node = queue.popleft()

            if node.end - node.begin == 1:
                self.leaves[node.begin] = node
            else:
                mid = (node.begin + node.end) // 2
                node.left = Node(node.begin, mid)
                node.right = Node(mid, node.end)
                node.left.parent = node.right.parent = node
                queue.append(node.left)
                queue.append(node.right)

    def update(self, index, val):
        node = self.leaves[index]
        node.val = val
        while node.parent is not None:
            node = node.parent
            node.val = node.left.val | node.right.val

    def val(self, begin, end, node=None):
        if node is None:
            return self.val(begin, end, self.root)
        if begin <= node.begin and node.end <= end:
            return node.val
        if node.end <= begin or end <= node.begin:
            return set()
        return self.val(begin, end, node.left) | self.val(begin, end, node.right)


N = int(input())
S = list(input())
Q = int(input())
tree = SegmentTree(N)
for i, c in enumerate(S):
    tree.update(i, set([c]))
for _ in range(Q):
    query = input().split()
    if query[0] == '1':
        i, c = query[1:]
        i = int(i) - 1
        tree.update(i, set([c]))
    else:
        l, r = map(int, query[1:])
        print(len(tree.val(l - 1, r)))

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys

from bisect import bisect, insort_left

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

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

    c0 = ord('a')
    S1 = [[] for i in range(26)]
    for i, c1 in enumerate(S):
        ci = ord(c1) - c0
        S1[ci].append(i)

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            if S[i] == j:
                continue

            c1 = ord(S[i]) - c0
            s1 = S1[c1]
            s1.remove(i)
            S[i] = j
            c1 = ord(j) - c0
            insort_left(S1[c1], i)
        elif cmd == "2":
            j = int(j) - 1
            num = 0

            for s1 in S1:
                ls = len(s1)
                k = bisect(s1, i-1, 0, ls)

                if k == ls:
                    continue
                if i <= s1[k] <= j:
                    num += 1

            ans.append(num)

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

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

for _ in range(Q):
    type, x, y = input().split()
    if type == "1":
        x = int(x)
        S[x-1] = y
    else:
        x = int(x)
        y = int(y)
        print(len(set(S[x-1:y])))

Submission status: Time Limit Exceeded

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


class SegTree():
    def __init__(self, N, e=float("inf"), operator_func=min):
        self.e = e
        self.size = N
        self.node = [self.e] * (2*N)
        self.op = operator_func

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x


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

    tree = SegTree(N, e=set(), operator_func=lambda x,y:set(x)|set(y))
    tree.set_list(S)

    Q = int(input())
    for _ in range(Q):
        mode, i, v = input().split()
        if mode=="1":
            i = int(i)-1
            tree.update(i, set(v))
        else:
            i = int(i)-1
            v = int(v)
            print(len(tree.get(i, v)))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class SegTree():
    def __init__(self, N, e=float("inf"), operator_func=min):
        self.e = e
        self.size = N
        self.node = [self.e] * (2*N)
        self.op = operator_func

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x

from operator import or_

N = int(input())
S = list(input())
trees = {}

for i in range(26):
    s = chr(97+i)
    trees[s] = SegTree(N, e=False, operator_func=or_)

for i, s in enumerate(S):
    trees[s].update(i, True)

Q = int(input())
for _ in range(Q):
    mode, i, v = input().split()
    if mode=="1":
        i = int(i)-1
        trees[S[i]].update(i, False)
        trees[v].update(i, True)
        S[i] = v
    else:
        i = int(i)-1
        v = int(v)
        ans = 0
        for j in range(26):
            ans += trees[chr(97+j)].get(i, v)
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import unittest


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(
            think(
                'abcdbbd',
                [
                    ['2', '3', '6'],
                    ['1', '5', 'z'],
                    ['2', '1', '1'],
                    ['1', '4', 'a'],
                    ['1', '7', 'd'],
                    ['2', '1', '7']
                ]
            ),
            [3, 1, 5]
        )


def solve():
    s, queries = read()
    result = think(s, queries)
    write(result)


def read():
    n = read_int(1)[0]
    s = read_line(n=n)
    q = read_int(1)[0]
    queries = []
    for _ in range(q):
        queries.append(read_line().split(' ')[:3])
    return s, queries


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(s, queries):
    # print(s, queries)
    local_s = list(s)
    result = []
    for q in queries:
        kind = q[0]
        if kind == '1':
            i = int(q[1])
            c = q[2]
            local_s[i - 1] = c
        elif kind == '2':
            left, right = int(q[1]), int(q[2])
            result.append(len(set(local_s[left - 1: right])))
    return result


def write(result):
    for r in result:
        print(r)


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Time Limit Exceeded

Solution code:
class SegTree():
    def __init__(self, N, e=float("inf"), operator_func=min):
        self.e = e
        self.size = N
        self.node = [self.e] * (2*N)
        self.op = operator_func

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x

from operator import or_

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

tree = SegTree(N, e=set(), operator_func=or_)
tree.set_list(S)

Q = int(input())
for _ in range(Q):
    mode, i, v = input().split()
    if mode=="1":
        i = int(i)-1
        tree.update(i, set(v))
    else:
        i = int(i)-1
        v = int(v)
        print(len(tree.get(i, v)))

Submission status: Time Limit Exceeded

Solution code:
class SegTree():
    def __init__(self, N, e=float("inf"), operator_func=min):
        self.e = e
        self.size = N
        self.node = [self.e] * (2*N)
        self.op = operator_func

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x

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

tree = SegTree(N, e=set(), operator_func=lambda x,y:set(x)|set(y))
tree.set_list(S)

Q = int(input())
for _ in range(Q):
    mode, i, v = input().split()
    if mode=="1":
        i = int(i)-1
        tree.update(i, set(v))
    else:
        i = int(i)-1
        v = int(v)
        print(len(tree.get(i, v)))

Submission status: Time Limit Exceeded

Solution code:
import math

class Segment_tree():
    def __init__(self, n, s):
        self.n = n
        self.s = s
        self.size = pow(2, math.ceil(math.log2(self.n))+1) - 1
        self.N = pow(2, math.ceil(math.log2(self.n))) - 1
        self.segment = [set()]*self.size
        for i in range(self.n):
            self.segment[i+self.N] = {self.s[i]}
        for i in range(self.N-1, -1, -1):
            a = self.segment[2*i+1] 
            b = self.segment[2*i+2]
            self.segment[i] = a|b
        
    def undate(self, i, x):
        i += (self.N-1)
        self.segment[i] = {x}
        while i > 0:
            i = (i-1)//2
            self.segment[i] = self.segment[2*i+1] | self.segment[2*i+2]
        
    def find(self, a, b, k, l, r):
        if r <= a or b <= l:
            return set()
        elif a <= l and r <= b:
            return self.segment[k]
        else:
            find_l = self.find(a, b, 2*k+1, l, (l+r)//2)
            find_r = self.find(a, b, 2*k+2, (l+r)//2, r)
            return find_l | find_r
    
    def count(self, a, b):
        return len(self.find(a, b, 0, 0, self.size-self.N))

n = int(input())
s = input()
segment_tree = Segment_tree(n, s)
q = int(input())
for i in range(q):
    key = [str(x) for x in input().split()]
    if key[0] == "1":
        segment_tree.undate(int(key[1]), key[2])
    else:
        print(segment_tree.count(int(key[1])-1, int(key[2])))

Submission status: Time Limit Exceeded

Solution code:
alplst = ['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']
#        [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26]
def alp(s,lst):
	lst[alplst.index(s)] += 1

def alp2(idx,S,c,lst):
	lst[alplst.index(c)] += 1
	lst[alplst.index(S[idx-1])] -= 1

	return lst

def colst(lst):
	return (26-lst.count(0))

def numnum(l,r,alllst):
	ret = []
	for i in range(26):
		if l > 1:
			ret.append(alllst[r-1][i]-alllst[l-2][i])
		else:
			ret.append(alllst[r-1][i]-0)
	return ret


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

	lst = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
	alllst= []
	changelst = []

	for i in range(N):
		alp(S[i],lst)
		alllst.append(lst[:])

	inlst = []

	for i in range(Q):
		inlst.append(input())

	for i in range(Q):
		typ, ia, ib = inlst[i].split()
		if int(typ) == 1:
			changelst.append([int(ia),ib])
		else:
			lstc = numnum(int(ia),int(ib),alllst)[:]
			for chg in changelst:
				if chg[0] <= int(ib) and chg[0] >= (int(ia)):
					lstc = alp2(chg[0],S,chg[1],lstc[:])[:]
			print(colst(lstc))

Submission status: Time Limit Exceeded

Solution code:
# 各文字についての出現位置を平行二分探索木など(順番を保持する配列)で持っておく
import bisect

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

S_list=[c for c in S]

indexes=[[] for _ in range(26)]
for i in range(N):
    indexes[ord(S_list[i])-ord("a")].append(i)
for q in query:
    t=q[0]
    if t=="1":
        i, c = int(q[1])-1, q[2]
        # 文字列情報を上書き
        indexes[ord(S_list[i])-ord("a")].remove(i)
        S_list[i]=c
        bisect.insort(indexes[ord(S_list[i])-ord("a")], i)
    else:
        l, r = int(q[1])-1, int(q[2]) # l以上なのでlはデクリメント
        ans=0
        for i in range(26):
            it = bisect.bisect_left(indexes[i], l)
            if it < len(indexes[i]) and indexes[i][it] < r: 
                ans+=1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 各文字についての出現位置を平行二分探索木など(順番を保持する配列)で持っておく
import bisect

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

indexes=[[] for _ in range(26)]
for i in range(N):
    indexes[ord(S[i])-ord("a")].append(i)
for q in query:
    t=q[0]
    if t=="1":
        i, c = int(q[1])-1, q[2]
        # 文字列情報を上書き
        indexes[ord(S[i])-ord("a")].remove(i)
        S=S[:i]+c+S[i+1:]
        bisect.insort(indexes[ord(S[i])-ord("a")], i)
    else:
        l, r = int(q[1])-1, int(q[2]) # l以上なのでlはデクリメント
        ans=0
        for i in range(26):
            it = bisect.bisect_left(indexes[i], l)
            if it < len(indexes[i]) and indexes[i][it] < r: 
                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):
    a,b,c=input().split()
    if a=='1':
        s[int(b)-1]=c
    else:
        t=set(s[int(b)-1:int(c)])
        print(len(t))