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:
"""SegTree, 遅い、、、

Returns:
    [type]: [description]
"""
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)

# AVL tree
# see: AVL tree implementation in python · GitHub https://gist.github.com/girish3/a8e3931154af4da89995#file-avl_tree-py-L12
# see: python AVL木 配列ver 　競技プログラミング　Atcoder - じゅっぴーダイアリー https://juppy.hatenablog.com/entry/2019/02/26/python_AVL%E6%9C%A8_%E9%85%8D%E5%88%97ver_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder_


class Node():
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


class AVLTree():
    def __init__(self, *args):
        self.node = None
        self.height = -1
        self.balance = 0

        if len(args) == 1:
            for i in args[0]:
                self.insert(i)

    def search(self, key):
        """keyがあればkeyを返す。なければNone
        
        Args:
            key ([type]): [description]
        
        Returns:
            [type]: [description]
        """
        if self.node == None:  # 1要素も無いとき
            return

        if self.node.key == None:
            return None
        if self.node.key > key:
            if self.node.left.node == None:
                return None
            else:
                return self.node.left.search(key)
        if self.node.key < key:
            if self.node.right.node == None:
                return None
            else:
                return self.node.right.search(key)
        return self.node.key  # self.node.key == keyの場合

    def insert(self, key):
        tree = self.node

        newnode = Node(key)

        if tree == None:
            self.node = newnode
            self.node.left = AVLTree()
            self.node.right = AVLTree()

        elif key < tree.key:
            self.node.left.insert(key)

        elif key > tree.key:
            self.node.right.insert(key)

        self.rebalance()

    def erase(self, key):
        if self.node != None:
            if self.node.key == key:
                if self.node.left.node == None and self.node.right.node == None:
                    self.node = None  # leaves can be killed at will
                # if only one subtree, take that
                elif self.node.left.node == None:
                    self.node = self.node.right.node
                elif self.node.right.node == None:
                    self.node = self.node.left.node

                # worst-case: both children present. Find logical successor
                else:
                    replacement = self.logical_successor(self.node)
                    if replacement != None:  # sanity check
                        self.node.key = replacement.key

                        # replaced. Now erase the key from right child
                        self.node.right.erase(replacement.key)

                self.rebalance()
                return
            elif key < self.node.key:
                self.node.left.erase(key)
            elif key > self.node.key:
                self.node.right.erase(key)

            self.rebalance()
        else:
            return

    def ex_upper_bound(self, ub, key_lower=None):
        """ub がexclusiveなupper bound.
        つまり、ub より小さい最大の値を返す。なければNone
        
        Args:
            ub (int): exclusiveなupper bound
            key_lower ([type], optional): [description]. Defaults to None.
        
        Returns:
            int: keyより小さい最大の値
        """
        if self.node == None:  # 1要素も無いとき
            return

        if self.node.key == None:
            return key_lower

        if self.node.key > ub:  # ノードの方がub より大きいので左に行く
            if self.node.left.node == None:
                return key_lower
            else:
                return self.node.left.ex_upper_bound(ub, key_lower)

        if self.node.key < ub:  # ノードの方が ub より 小さいので右に行く
            key_lower = self.node.key
            if self.node.right.node == None:
                return key_lower
            else:
                return self.node.right.ex_upper_bound(ub, key_lower)

        #self.node.key == ubの場合
        if self.node.left.node == None:
            return key_lower
        else:  # left以下のもっとも高い数値とkey_lowerのもっとも高いほう
            if key_lower == None:
                return self.logical_predecessor(self.node).key
            else:
                return max(key_lower, self.logical_predecessor(self.node).key)

    def ex_lower_bound(self, lb, key_upper=None):
        """lb がexclusiveなlower bound.
        つまり、lb より大きい最小の値を返す。なければNone
        
        Args:
            lb (int): exclusiveなlower bound.
            key_higher ([type], optional): [description]. Defaults to None.
        
        Returns:
            int: keyより大きい最小の値を返す
        """
        if self.node == None:  # 1要素も無いとき
            return
        if self.node.key == None:
            return key_upper
        if self.node.key > lb:
            key_upper = self.node.key
            if self.node.left.node == None:
                return key_upper
            else:
                return self.node.left.ex_lower_bound(lb, key_upper)
        if self.node.key < lb:
            if self.node.right.node == None:
                return key_upper
            else:
                return self.node.right.ex_lower_bound(lb, key_upper)
        #self.node.key == lbの場合
        if self.node.right.node == None:
            return key_upper
        else:
            if key_upper == None:
                return self.logical_successor(self.node).key
            else:
                return min(key_upper, self.logical_successor(self.node).key)

    def is_leaf(self):
        return (self.height == 0)

    def rebalance(self):
        ''' 
        Rebalance a particular (sub)tree
        '''
        # key inserted. Let's check if we're balanced
        self.update_heights(False)
        self.update_balances(False)
        while self.balance < -1 or self.balance > 1:
            if self.balance > 1:
                if self.node.left.balance < 0:
                    self.node.left.lrotate()  # we're in case II
                    self.update_heights()
                    self.update_balances()
                self.rrotate()
                self.update_heights()
                self.update_balances()

            if self.balance < -1:
                if self.node.right.balance > 0:
                    self.node.right.rrotate()  # we're in case III
                    self.update_heights()
                    self.update_balances()
                self.lrotate()
                self.update_heights()
                self.update_balances()

    def rrotate(self):
        # Rotate left pivoting on self
        A = self.node
        B = self.node.left.node
        T = B.right.node

        self.node = B
        B.right.node = A
        A.left.node = T

    def lrotate(self):
        # Rotate left pivoting on self
        A = self.node
        B = self.node.right.node
        T = B.left.node

        self.node = B
        B.left.node = A
        A.right.node = T

    def update_heights(self, recurse=True):
        if not self.node == None:
            if recurse:
                if self.node.left != None:
                    self.node.left.update_heights()
                if self.node.right != None:
                    self.node.right.update_heights()

            self.height = max(self.node.left.height,
                              self.node.right.height) + 1
        else:
            self.height = -1

    def update_balances(self, recurse=True):
        if not self.node == None:
            if recurse:
                if self.node.left != None:
                    self.node.left.update_balances()
                if self.node.right != None:
                    self.node.right.update_balances()

            self.balance = self.node.left.height - self.node.right.height
        else:
            self.balance = 0

    def logical_predecessor(self, node):
        """Find the biggest valued node in LEFT child
        
        Args:
            node (Node): [description]
        
        Returns:
            Node: the biggest valued node in LEFT child
        """
        node = node.left.node
        if node != None:
            while node.right != None:
                if node.right.node == None:
                    return node
                else:
                    node = node.right.node
        return node

    def logical_successor(self, node):
        """Find the smallest valued node in RIGHT child
        
        Args:
            node (Node): [description]
        
        Returns:
            Node: the smallest valued node in RIGHT child
        """
        node = node.right.node
        if node != None:  # just a sanity check

            while node.left != None:
                if node.left.node == None:
                    return node
                else:
                    node = node.left.node
        return node

    def check_balanced(self):
        if self == None or self.node == None:
            return True

        # We always need to make sure we are balanced
        self.update_heights()
        self.update_balances()
        return ((abs(self.balance) < 2) and self.node.left.check_balanced()
                and self.node.right.check_balanced())

    def inorder_traverse(self):
        if self.node == None:
            return []

        inlist = []
        l = self.node.left.inorder_traverse()
        for i in l:
            inlist.append(i)

        inlist.append(self.node.key)

        l = self.node.right.inorder_traverse()
        for i in l:
            inlist.append(i)

        return inlist

    def display(self, level=0, pref=''):
        '''
        Display the whole tree. Uses recursive def.
        TODO: create a better display using breadth-first search
        '''
        self.update_heights()  # Must update heights before balances
        self.update_balances()
        if (self.node != None):
            print('-' * level * 2, pref, self.node.key,
                  "[" + str(self.height) + ":" + str(self.balance) + "]",
                  'L' if self.is_leaf() else ' ')
            if self.node.left != None:
                self.node.left.display(level + 1, '<')
            if self.node.left != None:
                self.node.right.display(level + 1, '>')


##################################################################################

import string


def resolve():
    N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    Q = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ

    # N, D = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # h_list = [int(x) for x in sys.stdin.readline().split()]  # 複数int

    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    # v_list = [int(sys.stdin.readline().split()[0]) for _ in range(N)]
    grid = [[x for x in sys.stdin.readline().split()]
            for _ in range(Q)]  # int grid

    S = [c for c in S]

    tree_dict = dict()
    for c in string.ascii_lowercase:
        tree_dict[c] = AVLTree()

    for i, c in enumerate(S):
        tree_dict[c].insert(i)

    for _type, a, b in grid:
        if _type == '1':
            a = int(a) - 1
            if S[a] == b:
                pass
            else:
                tree_dict[S[a]].erase(a)
                tree_dict[b].insert(a)
                S[a] = b

        else:
            a = int(a) - 1
            b = int(b) - 1

            ret = 0
            for avl in tree_dict.values():
                higher = avl.ex_lower_bound(a - 1)
                if higher is not None and higher <= b:
                    ret += 1

            print(ret)


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7"""
        output = """3
1
5"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7"""
        output = """3
1
5"""
        self.assertIO(input, output)

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline


class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [[0] * (n + 1) for _ in range(26)]

    def bit_query(self, character, idx):
        if idx == 0:
            return 0
        sum_of_query = 0
        while idx > 0:
            sum_of_query += self.tree[character][idx]
            idx -= idx & (-idx)
        return sum_of_query

    def update(self, character, idx, x):
        while idx <= self.n:
            self.tree[character][idx] += x
            idx += idx & (-idx)
        return


N = int(input())
S = [''] + list(input())
Q, *query = map(str, read().split())
bit = BIT(N)
for idx, i in enumerate(S[1:], 1):
    bit.update(ord(i) - 97, idx, 1)
for a, b, c in zip(*[iter(query)] * 3):
    b = int(b)
    if a == '1':
        bit.update(ord(c) - 97, b, 1)
        bit.update(ord(S[b]) - 97, b, -1)
        S[b] = c
    else:
        c = int(c)
        print(sum(1 for i in range(26) if bit.bit_query(i, c) - bit.bit_query(i, b - 1) > 0))

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":
            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:
cmin = lambda a,b : a if a<b else b
cmax = lambda a,b : a if a>b else b
iin = lambda : int(input())
lin = lambda : list(map(int,input().split()))
rin = lambda n : [int(input()) for _ in range(n)]

n = iin()
s = input()
q = iin()
ans = []
for i in range(q):
    f,a,b = map(lambda x:int(x)-1 if x.isdigit() else x,input().split())
    if f==0:
        if a==n-1:
            s = s[:a] + b
        else:
            s = s[:a] + b + s[a+1:]
    else:
        if b==n-1:
            ans += [len(set(s[a:]))]
        else:
            ans += [len(set(s[a:b+1]))]

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import sys
sys.setrecursionlimit(10**6)

n=i1()
s=input()
q=i1()
N=0
while n:
  n>>=1
  N+=1
n=2**N

t=[set([]) for i in range(2*n-1)]

def ud(i,x):
  i+=n-1
  t[i]=x
  while i:
    i=(i-1)//2
    t[i]=t[i*2+1] | t[i*2+2]

def qr(a,b,k,l,r):
  
  if r<=a or b<=l:
     return set([])
  elif a<=l and r<=b:
     
     return t[k]
  else:
     return qr(a,b,k*2+1,l,(l+r)//2) | qr(a,b,k*2+2,(l+r)//2,r)

for i in range(len(s)):
  ud(i,set([s[i]]))

while q:
 [ty,i,c]=[i for i in input().split()]
 ty=int(ty)
 i=int(i)
 if ty==1:
   ud(i-1,set([c]))
 else:
   c=int(c)
   
   print(len(qr(i-1,c,0,0,n)))
   
 q-=1

Submission status: Time Limit Exceeded

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import math
import sys
sys.setrecursionlimit(10**6)

n=i1()
s=input()
q=i1()

n=2**(int(math.log2(n))+1)

t=[set([]) for i in range(2*n-1)]

def ud(i,x):
  i+=n-1
  t[i]=x
  while i:
    i=(i-1)//2
    t[i]=t[i*2+1] | t[i*2+2]

def qr(a,b,k,l,r):
  
  if r<=a or b<=l:
     return set([])
  elif a<=l and r<=b:
     
     return t[k]
  else:
     return qr(a,b,k*2+1,l,(l+r)//2) | qr(a,b,k*2+2,(l+r)//2,r)

for i in range(len(s)):
  ud(i,set([s[i]]))

while q:
 [ty,i,c]=[i for i in input().split()]
 ty=int(ty)
 i=int(i)
 if ty==1:
   ud(i-1,set([c]))
 else:
   c=int(c)
   
   print(len(qr(i-1,c,0,0,n)))
   
 q-=1

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


class SegmentTree:
    def __init__(self, A):
        self.n = 2**(len(A)-1).bit_length()
        self.identity = set()
        self.seg = [self.identity] * (2 * self.n)
        
        for i, a in enumerate(A):
            self.seg[self.n-1+i] = set(a)
        for i in range(self.n-2,-1,-1):
            self.seg[i] = self.seg[2*i+1] | self.seg[2*i+2]

            
    def update(self, k, a):
        k += self.n - 1
        self.seg[k] = set(a)
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.seg[k*2+1] | self.seg[k*2+2]

            
    def query(self, a, b):
        if b == a:
        	return 1
        a += self.n - 1
        b += self.n - 2
        res = self.identity
        while b - a > 1:
            if a & 1 == 0:
                res = res | self.seg[a]
            if b & 1 == 1:
                res = res | self.seg[b]
                b -= 1
            a = a // 2
            b = (b - 1) // 2
        if a == b:
            res = res | self.seg[a]
        else:
            res = res | self.seg[a] | self.seg[b]
        
        return len(res)


def main():
    N = int(readline())
    s = readline().strip()
    seg = SegmentTree(list(s))
    #print(seg.seg)

    Q = int(readline())
    for _ in range(Q):
        q, a, b = map(str, readline().split())
        if q == "1":
            seg.update(int(a)-1, b)
        else:
            print(seg.query(int(a)-1, int(b)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
Q = int(input())
# N*Q=10**10程度の１重の繰り返しだから，何となくなる?

Query = []
for _ in range(Q):
    Query.append(input().split())
for q in Query:
    if q[0] == '1':
        ind = int(q[1])-1
        new_char = q[2]
        S[ind] = q[2]
    else:
        start_ind = int(q[1])-1
        end_ind = int(q[2])-1
        count_list = []
        for s in S[start_ind:end_ind+1]:
            if not s in count_list:
                count_list.append(s)
        print(len(count_list))

Submission status: Time Limit Exceeded

Solution code:
#13:19
n = int(input())
s = input()
t = []
for i in range(n):
  t.append(ord(s[i])-97)
q = int(input())
scale = 19
seg = [[0 for _ in range(2**(scale+1))] for _ in range(26)]
for i in range(n):
  tmp = int(i) + 2 ** scale
  x = t[i]
  while tmp != 0:
    seg[x][tmp] += 1
    tmp //= 2
#print(seg)
raw = []
for _ in range(q):
  d,a,b = input().split()
  d = int(d)
  if d == 1:
    a = int(a) - 1
    b = ord(b) - 97
  else:
    a = int(a) - 2
    b = int(b) - 1
  raw.append([d,a,b])
for p in range(q):
  d,a,b = raw[p]
  if d == 1:
    tmp = int(a)
    c = t[tmp]
    tmp += 2**scale
    while tmp != 0:
      seg[c][tmp] -= 1
      tmp //= 2
    tmp = int(a)
    t[tmp] = b
    tmp += 2**scale
    while tmp != 0:
      seg[b][tmp] += 1
      tmp //= 2
  else:
    ans = 0
    for d in range(26):
      l = 0
      r = 0
      if a == -1:
        l = 0
      else:
        tmp = a + 2**scale
        l += seg[d][tmp]
        while tmp != 1:
          if tmp & 1:
            l += seg[d][tmp-1]
          tmp //= 2
      tmp = b + 2**scale
      r += seg[d][tmp]
      while tmp != 1:
        if tmp & 1:
          r += seg[d][tmp-1]
        tmp //= 2
      if r > l:
        ans += 1
      #print(d,r,l)
    print(ans)
#print(t)

Submission status: Time Limit Exceeded

Solution code:
#13:19
n = int(input())
s = input()
t = []
for i in range(n):
  t.append(ord(s[i])-97)
q = int(input())
scale = 19
seg = [[0 for _ in range(2**(scale+1))] for _ in range(26)]
for i in range(n):
  tmp = int(i) + 2 ** scale
  x = t[i]
  while tmp != 0:
    seg[x][tmp] += 1
    tmp //= 2
#print(seg)
raw = []
for _ in range(q):
  d,a,b = input().split()
  d = int(d)
  if d == 1:
    a = int(a) - 1
    b = ord(b) - 97
  else:
    a = int(a) - 2
    b = int(b) - 1
  raw.append([d,a,b])
for p in range(q):
  d,a,b = raw[p]
  if d == 1:
    tmp = int(a)
    c = t[tmp]
    tmp += 2**scale
    while tmp != 0:
      seg[c][tmp] -= 1
      tmp >>= 1
    tmp = int(a)
    t[tmp] = b
    tmp += 2**scale
    while tmp != 0:
      seg[b][tmp] += 1
      tmp >>= 1
  else:
    ans = 0
    for d in range(26):
      l = 0
      r = 0
      if a == -1:
        l = 0
      else:
        tmp = a + 2**scale
        l += seg[d][tmp]
        while tmp != 1:
          if tmp % 2 == 1:
            l += seg[d][tmp-1]
          tmp >>= 1
      tmp = b + 2**scale
      r += seg[d][tmp]
      while tmp != 1:
        if tmp % 2 == 1:
          r += seg[d][tmp-1]
        tmp >>= 1
      if r > l:
        ans += 1
      #print(d,r,l)
    print(ans)
#print(t)

Submission status: Time Limit Exceeded

Solution code:
#13:19
n = int(input())
s = input()
t = []
for i in range(n):
  t.append(ord(s[i])-97)
q = int(input())
seg = [[0 for _ in range(2**20)] for _ in range(26)]
for i in range(n):
  tmp = int(i) + 2**19
  x = t[i]
  while tmp != 0:
    seg[x][tmp] += 1
    tmp //= 2
#print(seg)
raw = []
for _ in range(q):
  d,a,b = input().split()
  d = int(d)
  if d == 1:
    a = int(a) - 1
    b = ord(b) - 97
  else:
    a = int(a) - 2
    b = int(b) - 1
  raw.append((d,a,b))
for p in range(q):
  d,a,b = raw[p]
  if d == 1:
    tmp = int(a)
    c = t[tmp]
    tmp += 2**19
    while tmp != 0:
      seg[c][tmp] -= 1
      tmp //= 2
    tmp = int(a)
    t[tmp] = b
    tmp += 2**19
    while tmp != 0:
      seg[b][tmp] += 1
      tmp //= 2
  else:
    ans = 0
    for d in range(26):
      l = 0
      r = 0
      if a == -1:
        l = 0
      else:
        tmp = a + 2**19
        l += seg[d][tmp]
        while tmp != 1:
          if tmp % 2 == 1:
            l += seg[d][tmp-1]
          tmp //= 2
      tmp = b + 2**19
      r += seg[d][tmp]
      while tmp != 1:
        if tmp % 2 == 1:
          r += seg[d][tmp-1]
        tmp //= 2
      if r > l:
        ans += 1
      #print(d,r,l)
    print(ans)
#print(t)

Submission status: Time Limit Exceeded

Solution code:
#13:19
n = int(input())
s = input()
t = []
for i in range(n):
  t.append(ord(s[i])-97)
q = int(input())
seg = [[0 for _ in range(1048576)] for _ in range(26)]
for i in range(n):
  tmp = int(i) + 524288
  x = t[i]
  while tmp != 0:
    seg[x][tmp] += 1
    tmp //= 2
#print(seg)
raw = []
for _ in range(q):
  d,a,b = input().split()
  d = int(d)
  if d == 1:
    a = int(a) - 1
    b = ord(b) - 97
  else:
    a = int(a) - 2
    b = int(b) - 1
  raw.append([d,a,b])
for p in range(q):
  d,a,b = raw[p]
  if d == 1:
    tmp = int(a)
    c = t[tmp]
    tmp += 524288
    while tmp != 0:
      seg[c][tmp] -= 1
      tmp //= 2
    tmp = int(a)
    t[tmp] = b
    tmp += 524288
    while tmp != 0:
      seg[b][tmp] += 1
      tmp //= 2
  else:
    ans = 0
    for d in range(26):
      l = 0
      r = 0
      if a == -1:
        l = 0
      else:
        tmp = a + 524288
        l += seg[d][tmp]
        while tmp != 1:
          if tmp % 2 == 1:
            l += seg[d][tmp-1]
          tmp //= 2
      tmp = b + 524288
      r += seg[d][tmp]
      while tmp != 1:
        if tmp % 2 == 1:
          r += seg[d][tmp-1]
        tmp //= 2
      if r > l:
        ans += 1
      #print(d,r,l)
    print(ans)
#print(t)

Submission status: Time Limit Exceeded

Solution code:
#13:19
n = int(input())
s = input()
t = []
for i in range(n):
  t.append(ord(s[i])-97)
q = int(input())
seg = [[0 for _ in range(2**20)] for _ in range(26)]
for i in range(n):
  tmp = int(i) + 2**19
  x = t[i]
  while tmp != 0:
    seg[x][tmp] += 1
    tmp //= 2
#print(seg)
raw = []
for _ in range(q):
  d,a,b = input().split()
  d = int(d)
  if d == 1:
    a = int(a) - 1
    b = ord(b) - 97
  else:
    a = int(a) - 2
    b = int(b) - 1
  raw.append([d,a,b])
for p in range(q):
  d,a,b = raw[p]
  if d == 1:
    tmp = int(a)
    c = t[tmp]
    tmp += 2**19
    while tmp != 0:
      seg[c][tmp] -= 1
      tmp //= 2
    tmp = int(a)
    t[tmp] = b
    tmp += 2**19
    while tmp != 0:
      seg[b][tmp] += 1
      tmp //= 2
  else:
    ans = 0
    for d in range(26):
      l = 0
      r = 0
      if a == -1:
        l = 0
      else:
        tmp = a + 2**19
        l += seg[d][tmp]
        while tmp != 1:
          if tmp % 2 == 1:
            l += seg[d][tmp-1]
          tmp //= 2
      tmp = b + 2**19
      r += seg[d][tmp]
      while tmp != 1:
        if tmp % 2 == 1:
          r += seg[d][tmp-1]
        tmp //= 2
      if r > l:
        ans += 1
      #print(d,r,l)
    print(ans)
#print(t)

Submission status: Time Limit Exceeded

Solution code:
#13:19
n = int(input())
s = input()
t = []
for i in range(n):
  t.append(ord(s[i])-97)
q = int(input())
scale = 19
seg = [[0 for _ in range(2**(scale+1))] for _ in range(26)]
for i in range(n):
  tmp = int(i) + 2 ** scale
  x = t[i]
  while tmp != 0:
    seg[x][tmp] += 1
    tmp //= 2
raw = []
for _ in range(q):
  g,a,b = input().split()
  g = int(g)
  if g == 1:
    a = int(a) - 1
    b = ord(b) - 97
  else:
    a = int(a) - 2
    b = int(b) - 1
  raw.append([g,a,b])
def plus(d,e,j):
  e += 2**scale
  while e != 0:
    seg[d][e] += j
    e //= 2
def sun(d,e):
  if e == -1:
    return 0
  e += 2**scale
  r = seg[d][e]
  while e != 1:
    if e % 2 == 1:
      r += seg[d][e-1]
    e //= 2
  return r
for p in range(q):
  g,a,b = raw[p]
  if g == 1:
    c = t[a]
    plus(c,a,-1)
    t[a] = b
    plus(b,a,1)
  else:
    ans = 0
    for d in range(26):
      if sun(d,a) != sun(d,b):
        ans += 1
    print(ans)
#print(t)

Submission status: Time Limit Exceeded

Solution code:
#13:19
n = int(input())
s = input()
t = []
for i in range(n):
  t.append(ord(s[i])-97)
q = int(input())
scale = 19
seg = [[0 for _ in range(2**(scale+1))] for _ in range(26)]
for i in range(n):
  tmp = int(i) + 2 ** scale
  x = t[i]
  while tmp != 0:
    seg[x][tmp] += 1
    tmp //= 2
#print(seg)
raw = []
for _ in range(q):
  d,a,b = input().split()
  d = int(d)
  if d == 1:
    a = int(a) - 1
    b = ord(b) - 97
  else:
    a = int(a) - 2
    b = int(b) - 1
  raw.append([d,a,b])
for p in range(q):
  d,a,b = raw[p]
  if d == 1:
    tmp = int(a)
    c = t[tmp]
    tmp += 2**scale
    while tmp != 0:
      seg[c][tmp] -= 1
      tmp //= 2
    tmp = int(a)
    t[tmp] = b
    tmp += 2**scale
    while tmp != 0:
      seg[b][tmp] += 1
      tmp //= 2
  else:
    ans = 0
    for d in range(26):
      l = 0
      r = 0
      if a == -1:
        l = 0
      else:
        tmp = a + 2**scale
        l += seg[d][tmp]
        while tmp != 1:
          if tmp % 2 == 1:
            l += seg[d][tmp-1]
          tmp //= 2
      tmp = b + 2**scale
      r += seg[d][tmp]
      while tmp != 1:
        if tmp % 2 == 1:
          r += seg[d][tmp-1]
        tmp //= 2
      if r > l:
        ans += 1
      #print(d,r,l)
    print(ans)
#print(t)

Submission status: Time Limit Exceeded

Solution code:
#13:19
n = int(input())
s = input()
t = []
for i in range(n):
  t.append(ord(s[i])-ord('a'))
q = int(input())
scale = 19
seg = [[0 for _ in range(2**(scale+1))] for _ in range(26)]
for i in range(n):
  tmp = int(i) + 2 ** scale
  x = t[i]
  while tmp != 0:
    seg[x][tmp] += 1
    tmp //= 2
#print(seg)
#print(seg[2])
for _ in range(q):
  d,a,b = input().split()
  if d == '1':
    b = ord(b) - ord('a')
    tmp = int(a) - 1
    c = t[tmp]
    tmp += 2**scale
    while tmp != 0:
      seg[c][tmp] -= 1
      tmp //= 2
    tmp = int(a) - 1
    t[tmp] = b
    tmp += 2**scale
    while tmp != 0:
      seg[b][tmp] += 1
      tmp //= 2
  else:
    a = int(a) - 2
    b = int(b) - 1
    ans = 0
    for d in range(26):
      l = 0
      r = 0
      if a == -1:
        l = 0
      else:
        tmp = a + 2**scale
        l += seg[d][tmp]
        while tmp != 1:
          if tmp % 2 == 1:
            l += seg[d][tmp-1]
          tmp //= 2
      tmp = b + 2**scale
      r += seg[d][tmp]
      while tmp != 1:
        if tmp % 2 == 1:
          r += seg[d][tmp-1]
        tmp //= 2
      if r > l:
        ans += 1
      #print(d,r,l)
    print(ans)
#print(t)