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
input = sys.stdin.readline
from operator import or_


def read():
    N = int(input().strip())
    S = input().strip()
    Q = int(input().strip())
    return N, S, Q


class SegmentTree():
    
    def __init__(self, size, op=min, init_value=10**8):
        """初期化"""
        self.size = size
        self.op = op
        self.init_value = init_value
        n = 2 ** ((size-1).bit_length())
        treesize = n * 2
        st = [init_value for i in range(treesize)]
        self.st = st

    @classmethod
    def from_array(cls, a, op=min, init_value=10**8):
        st = cls(len(a), op=op, init_value=init_value)
        for i, x in enumerate(a):
            st.update(i, x)
        return st

    def update(self, key, value):
        """値の更新"""
        offset = len(self.st) // 2
        k = offset + key
        self.st[k] = value
        k >>= 1
        while k > 0:
            self.st[k] = self.op(self.st[k * 2], self.st[k * 2 + 1])
            k >>= 1

    def _query(self, a, b, k, l, r):
        """区間[a, b) に対する累積操作
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        if r <= a or b <= l:
            return self.init_value
        if a <= l and r <= b:
            return self.st[k]
        mid = (l + r) // 2
        lv = self._query(a, b, k * 2, l, mid)
        rv = self._query(a, b, k * 2 + 1, mid, r)
        return self.op(lv, rv)

    def query(self, a, b):
        """区間[a, b) に対する累積操作"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        return self._query(a, b, k=1, l=0, r=len(self.st)//2)


def solve_online(N, S, Q):
    trees = [SegmentTree(N, op=or_, init_value=0) for i in range(26)]
    C = [ord(s) - ord("a") for s in S]
    for i in range(N):
        c = ord(S[i]) - ord("a")
        trees[c].update(i, 1)

    for _ in range(Q):
        op, a, b = input().strip().split()
        if op == "1":
            i, c1 = int(a)-1, ord(b) - ord("a")
            c0 = C[i]
            trees[c0].update(i, 0)
            C[i] = c1
            trees[c1].update(i, 1)
        elif op == "2":
            l, r = int(a)-1, int(b)-1
            s = sum([trees[i].query(l, r+1) for i in range(26)])
            print(s)


if __name__ == '__main__':
    inputs = read()
    outputs = solve_online(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

Solution code:
# BinarySearchTreeの実装
class BinarySearchTree():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None
        self.debris = []

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        if self.debris == []:
            self.data.append(None)
            self.left.append(None)
            self.right.append(None)
            self.parent.append(None)
            return len(self.data) - 1
        else:
            return self.debris.pop(-1)

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
            self.debris = []
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            elif self.right[i] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
            elif self.left[self.right[i]] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.parent[self.left[i]] = j
            elif self.right[self.left[i]] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
                self.right[j] = self.right[i]
                self.parent[self.right[i]] = j
            else:
                j = self.right[i]
                while self.left[j] != None:
                    j = self.left[j]
                self.left[self.parent[j]] = self.right[j]
                if self.right[j] != None:
                    self.parent[self.right[j]] = self.parent[j]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.right[j] = self.right[i]
                self.parent[self.left[i]] = j
                self.parent[self.right[i]] = j
                

            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j
            
            # iの初期化
            self.data[i] = None
            self.left[i] = None
            self.right[i] = None
            self.parent[i] = None
            self.debris.append(i)
    
    def exist(self, x):
        return self.data[self.find(x)] == x

    def empty(self):
        return self.root == None

    def debug(self):
        if self.root == None:
            return 'empty'
        tree = [[self.root]]
        flag = True
        while flag:
            l = []
            for i in tree[-1]:
                if i == '  ':
                    l.append('  ')
                    l.append('  ')
                    continue
                elif self.left[i] == None:
                    l.append('  ')
                else:
                    l.append(self.left[i])
                if self.right[i] == None:
                    l.append('  ')
                else:
                    l.append(self.right[i])
            flag = False
            for i in l:
                if i == '  ':
                    continue
                else:
                    tree.append(l)
                    flag = True
                    break
        for i in range(len(tree)):
            l = []
            for j in tree[i]:
                if j == '  ':
                    l.append(j)
                else:
                    k = str(self.data[j])
                    if len(k) == 1:
                        k = ' ' + k
                    l.append(k)
            n = len(tree) - i
            m = (2**n-1) * '  '
            l = (m.join(l))
            print((2**(n-1)-1) * '  ' + l)
        print()

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False

import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

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

# alphabet毎に整理
alp = [BinarySearchTree() for _ in range(26)]
from random import shuffle
l = [i for i in range(n)]
shuffle(l)
for i in l:
    alp[order(s[i])].add(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        alp[order(s[b])].remove(b)
        alp[order(c)].add(b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i.search(b, c):
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
# BinarySearchTreeの実装
class BinarySearchTree():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None
        self.debris = []

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        if self.debris == []:
            self.data.append(None)
            self.left.append(None)
            self.right.append(None)
            self.parent.append(None)
            return len(self.data) - 1
        else:
            return self.debris.pop(-1)

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
            self.debris = []
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            elif self.right[i] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
            elif self.left[self.right[i]] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.parent[self.left[i]] = j
            elif self.right[self.left[i]] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
                self.right[j] = self.right[i]
                self.parent[self.right[i]] = j
            else:
                j = self.right[i]
                while self.left[j] != None:
                    j = self.left[j]
                self.left[self.parent[j]] = self.right[j]
                if self.right[j] != None:
                    self.parent[self.right[j]] = self.parent[j]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.right[j] = self.right[i]
                self.parent[self.left[i]] = j
                self.parent[self.right[i]] = j
                

            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j
            
            # iの初期化
            self.data[i] = None
            self.left[i] = None
            self.right[i] = None
            self.parent[i] = None
            self.debris.append(i)
    
    def exist(self, x):
        return self.data[self.find(x)] == x

    def empty(self):
        return self.root == None

    def debug(self):
        if self.root == None:
            return 'empty'
        tree = [[self.root]]
        flag = True
        while flag:
            l = []
            for i in tree[-1]:
                if i == '  ':
                    l.append('  ')
                    l.append('  ')
                    continue
                elif self.left[i] == None:
                    l.append('  ')
                else:
                    l.append(self.left[i])
                if self.right[i] == None:
                    l.append('  ')
                else:
                    l.append(self.right[i])
            flag = False
            for i in l:
                if i == '  ':
                    continue
                else:
                    tree.append(l)
                    flag = True
                    break
        for i in range(len(tree)):
            l = []
            for j in tree[i]:
                if j == '  ':
                    l.append(j)
                else:
                    k = str(self.data[j])
                    if len(k) == 1:
                        k = ' ' + k
                    l.append(k)
            n = len(tree) - i
            m = (2**n-1) * '  '
            l = (m.join(l))
            print((2**(n-1)-1) * '  ' + l)
        print()

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False

import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

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

# alphabet毎に整理
alp = [BinarySearchTree() for _ in range(26)]
for i in range(n):
    alp[order(s[i])].add(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        alp[order(s[b])].remove(b)
        alp[order(c)].add(b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i.search(b, c):
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import collections
n=int(input())
s=list(map(str,input()))
q=int(input())
for _ in range(q):
    a,b,c=map(str,input().split())
    if a=='1':
        s[int(b)-1]=c
    else:
        l=[]
        for i in range(int(b)-1,int(c)):
            l.append(s[i])
        print(len(collections.Counter(l)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect

N = int(sys.stdin.readline().rstrip())
S = list(sys.stdin.readline().rstrip())
Q = int(sys.stdin.readline().rstrip())

idx = {chr(ord("a") + i): set() for i in range(26)}

for i, s in enumerate(S):
    idx[s].add(i + 1)

for _ in range(Q):
    t, i, c = sys.stdin.readline().rstrip().split()
    i = int(i)
    if t == "1":
        if S[i - 1] != c:
            idx[S[i - 1]].remove(i)
            idx[c].add(i)
            S[i - 1] = c
    else:
        c = int(c)
        ans = 0
        for a, id in idx.items():
            id = sorted(list(id))
            x = bisect.bisect_left(id, i)
            y = bisect.bisect_right(id, c)
            if y - x:
                ans += 1
        print(ans)

Submission status: Time Limit Exceeded

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

def ctoi(c):
  return ord(c)-97
class Bit:
  def __init__(self, n):
    self.size = n
    self.tree = [[0]*(n+1) for _ in range(26)]
  def query(self,a,i):
    r = 0
    while i > 0:
      r += self.tree[a][i]
      i -= i & -i
    return r
  def update(self,i,a,x):
    while i<=n:
      self.tree[a][i]+=x
      i+=i&(-i)
bi=Bit(n)
for i in range(n):
  bi.update(i+1,ctoi(s[i]),1)
  
for _ in range(q):
  a,b,c=input().split()
  a,b=int(a),int(b)
  if a==1 and s[b-1]!=c:
    bi.update(b,ctoi(s[b-1]),-1)
    bi.update(b,ctoi(c),1)
    s[b-1]=c
  elif a==2:
    c=int(c)
    right=[bi.query(i,c) for i in range(26)]
    left=[bi.query(i,b-1) for i in range(26)]
    ans=0
    for r,l in zip(right,left):
      if r-l>0:
        ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def segfunc(x,y): 
    return max(x,y)
def init(init_val,ide):
    global ide_ele,num,seg
    ide_ele = ide
    n = len(init_val)
    num = 2**(n-1).bit_length()
    seg = [[ide_ele for _ in range(2*num)] for _ in range(26)]
    for i in range(n):
        seg[init_val[i]][i+num-1] = 1
    for a in range(26):
        for i in range(num-2,-1,-1) :
            seg[a][i] = segfunc(seg[a][2*i+1],seg[a][2*i+2])
def update(k,x):
    global s
    x = ord(x)-97
    pre = s[k]
    s[k] = x
    k += num-1
    seg[pre][k] = 0
    seg[x][k] = 1
    while k:
        k = (k-1)//2
        seg[pre][k] = segfunc(seg[pre][k*2+1],seg[pre][k*2+2])
        seg[x][k] = segfunc(seg[x][k*2+1],seg[x][k*2+2])
def query(P,Q):
    if Q <= P:
        return ide_ele
    P += num-1
    Q += num-2
    ans = ide_ele
    for i in range(26):
        res = ide_ele
        p,q = P,Q
        while q-p > 1:
            if p&1 == 0:
                res = segfunc(res,seg[i][p])
            if q&1 == 1:
                res = segfunc(res,seg[i][q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res,seg[i][p])
        else:
            res = segfunc(segfunc(res,seg[i][p]),seg[i][q])
        ans += res
    return ans

def main():
    global s
    n = int(input())
    s = list(input())
    for i in range(n):
        s[i] = ord(s[i])-97
    init(s,0)
    q = int(input())
    for _ in range(q):
        QUERY = list(input().split())
        QUERY[0], QUERY[1] = int(QUERY[0]), int(QUERY[1])
        if QUERY[0] == 1:
            update(QUERY[1]-1,QUERY[2])
        if QUERY[0] == 2:
            print(query(QUERY[1]-1,int(QUERY[2])))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def segfunc(x,y): 
    return max(x,y)
def init(init_val,ide):
    global ide_ele,num,seg
    ide_ele = ide
    n = len(init_val)
    num = 2**(n-1).bit_length()
    seg = [[ide_ele for _ in range(2*num)] for _ in range(26)]
    for i in range(n):
        seg[ord(init_val[i])-97][i+num-1] = 1
    for a in range(26):
        for i in range(num-2,-1,-1) :
            seg[a][i] = segfunc(seg[a][2*i+1],seg[a][2*i+2])
def update(k,x):
    global s
    pre = s[k]
    s[k] = x
    k += num-1
    seg[ord(pre)-97][k] = 0
    seg[ord(x)-97][k] = 1
    while k:
        k = (k-1)//2
        seg[ord(pre)-97][k] = segfunc(seg[ord(pre)-97][k*2+1],seg[ord(pre)-97][k*2+2])
        seg[ord(x)-97][k] = segfunc(seg[ord(x)-97][k*2+1],seg[ord(x)-97][k*2+2])
def query(P,Q):
    if Q <= P:
        return ide_ele
    P += num-1
    Q += num-2
    ans = ide_ele
    for i in range(26):
        res = ide_ele
        p,q = P,Q
        while q-p > 1:
            if p&1 == 0:
                res = segfunc(res,seg[i][p])
            if q&1 == 1:
                res = segfunc(res,seg[i][q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res,seg[i][p])
        else:
            res = segfunc(segfunc(res,seg[i][p]),seg[i][q])
        ans += res
    return ans

def main():
    global s
    n = int(input())
    s = list(input())
    init(s,0)
    q = int(input())
    for _ in range(q):
        QUERY = list(input().split())
        QUERY[0], QUERY[1] = int(QUERY[0]), int(QUERY[1])
        if QUERY[0] == 1:
            update(QUERY[1]-1,QUERY[2])
        if QUERY[0] == 2:
            print(query(QUERY[1]-1,int(QUERY[2])))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left,bisect_right
import string 

dic = {c:[] for c in string.ascii_lowercase}

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

for i,c in enumerate(s,start=1):
  dic[c].append(i)
  
for i in range(q):
  p,l,r = map(str,input().split())
  if p =='1':
    j = int(l)
    c = s[j-1]
    dic[c].pop(bisect_left(dic[c],j))
    dic[r].insert(bisect_left(dic[r],j),j)
    s[j-1] = r
  else:
    ans = 0
    l = int(l)
    r = int(r)
    for c in string.ascii_lowercase:
      pl = bisect_left(dic[c],l)
      if pl < len(dic[c]):
        if dic[c][pl] <= r:
          ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left,bisect_right
import string 

dic = {c:[] for c in string.ascii_lowercase}

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

for i,c in enumerate(s,start=1):
  dic[c].append(i)
  
for i in range(q):
  p,l,r = map(str,input().split())
  if p =='1':
    j = int(l)
    c = s[j-1]
    dic[c].pop(bisect_left(dic[c],j))
    dic[r].insert(bisect_left(dic[r],j),j)
    s[j-1] = r
  else:
    ans = 0
    l = int(l)
    r = int(r)
    for c in dic.keys():
      pl = bisect_left(dic[c],l)
      if pl < len(dic[c]):
        if dic[c][pl] <= r:
          ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left,bisect_right
import string 
dic = {c:[] for c in string.ascii_lowercase}

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

for i,c in enumerate(s,start=1):
  dic[c].append(i)
  
for i in range(q):
  p,l,r = map(str,input().split())
  if p =='1':
    j = int(l)
    c = s[j-1]
    dic[c].pop(bisect_left(dic[c],j))
    dic[r].insert(bisect_left(dic[r],j),j)
    s[j-1] = r
  else:
    ans = 0
    for c in dic.keys():
      if bisect_left(dic[c],int(l)) != bisect_right(dic[c],int(r)):
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left,bisect_right
import string 
dic = {c:[] for c in string.ascii_lowercase}

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

for i,c in enumerate(s,start=1):
  dic[c].append(i)
  
for i in range(q):
  p,l,r = map(str,input().split())
  if p =='1':
    j = int(l)
    c = s[j-1]
    dic[c].pop(bisect_left(dic[c],j))
    dic[r].insert(bisect_left(dic[r],j),j)
    s[j-1] = r
  else:
    ans = 0
    for vs in dic.values():
      if bisect_left(vs,int(l)) != bisect_right(vs,int(r)):
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

for _ in range(Q):
    qt, q1, q2 = input().split()
    if qt == '1':
        S[int(q1)-1] = q2
    else:
        print(len(set(S[int(q1)-1:int(q2)])))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(300000)

class BinaryIndexedTree(object):

    def __init__(self, n):
        # index is 1-based so vals[0] never be used
        self.n = n
        self.vals = [0] * (n + 1)

    def add(self, i, v):
        while i <= self.n:
            self.vals[i] += v
            i += i & -i

    def sum(self, i):
        ret = 0
        while i > 0:
            ret += self.vals[i]
            i -= i & -i
        return ret

    def sum_range(self, l, r):
        # l and r are 1-based index and inclusive
        return self.sum(r) - self.sum(l - 1)


def solve(N, S, Q, queries):
    trees = []
    for i in range(26):
        trees.append(BinaryIndexedTree(N))

    s = []
    for i, c in enumerate(S):
        c_idx = ord(c) - ord('a')
        if 'a' <= c <= 'z':
            trees[c_idx].add(i + 1, 1)
        s.append(c)

    for q in queries:
        if q[0] == '1':
            i, c = int(q[1]), q[2]
            p = s[i - 1]
            s[i - 1] = c
            trees[ord(p) - ord('a')].add(i, -1)
            trees[ord(c) - ord('a')].add(i, 1)
        if q[0] == '2':
            l, r = int(q[1]), int(q[2])
            ret = 0
            for tree in trees:
                cnt = tree.sum_range(l, r)
                if cnt:
                    ret += 1
            print(ret)
        #pprint(get_range_sum(1, 5, bit))
        #print(s)
        #print()

    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))
    S = str(next(tokens))
    Q = int(next(tokens))
    q = []
    for i in range(Q):
        q.append(list(map(str, input().split())))
    solve(N, S, Q, q)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

alphabet = [chr(ord('a') + i) for i in range(26)]

d = {alphabet[i]: [] for i in range(26)}
for i, a in enumerate(s):
    d[a].append(i)

ans = []
for i in range(q):
    query = input().split()

    if query[0] == '1':
        idx, c = int(query[1]) - 1, query[2]
        d[s[idx]].remove(idx)
        bisect.insort_left(d[c], idx)
        s[idx] = c
    else:
        l, r = int(query[1]) - 1, int(query[2]) - 1
        res = 0
        for c in alphabet:
            if bisect.bisect_right(d[c], r) > bisect.bisect_left(d[c], l):
                res += 1
        ans.append(res)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
l=[x for x in s]
q=int(input())
for i in range(q):
  a,b,c=input().split()
  a=int(a)
  b=int(b)

  if a==1:
    l[b-1]=c
  elif a==2:
    c=int(c)
    k=l[b-1:c]
    k=list(set(k))
    print(len(k))
  #print(a,b,c,l)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n=int(input())
  s=list(input())
  q_=int(input())
  q=[input().split() for _ in range(q_)]
  class BIT:
    def __init__(self, n):
      self.n = n
      self.data = [0]*(n+1)
      self.el = [0]*(n+1)
    def sum(self, i):
      s = 0
      while i > 0:
        s += self.data[i]
        i -= i & -i
      return s
    def add(self, i, x):
      # assert i > 0
      self.el[i] += x
      while i <= self.n:
        self.data[i] += x
        i += i & -i
    def get(self, i, j=None):
      if j is None:
        return self.el[i]
      return self.sum(j) - self.sum(i)

  a2n = lambda c: ord(c) - ord('a')
  d=[BIT(n) for _ in range(26)]
  di=[0]*26
  for i in range(1,n+1):
    d[a2n(s[i-1])].add(i,1)
  for qi in q:
    if qi[0]=='1':
      i=int(qi[1])
      c=a2n(qi[2])
      si=a2n(s[i-1])
      d[c].add(i,1)
      d[si].add(i,-1)
      s[i-1]=qi[2]
    else:
      ans=0
      l,r=int(qi[1]),int(qi[2])
      for i in range(26):
        ls=d[i].sum(l-1)
        rs=d[i].sum(r)
        ans+=1 if rs-ls>0 else 0
      print(ans)
if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())

Submission status: Time Limit Exceeded

Solution code:
def main():
  n=int(input())
  s=list(input())
  q_=int(input())
  q=[input().split() for _ in range(q_)]
  """
  n=500000
  s=list('abcdfghijk'*(n//10))
  q_=200
  q=[]
  n2a = lambda c: chr(c%26+1+64).lower()
  for i in range(q_):
    if True:
      q.append(['1',str(i*11),n2a(i)])
    else:
      q.append(['2',str(i),str(i*11)])
  """
  import numpy as np
  a2n = lambda c: ord(c) - ord('a')
  d=[[0]*26]
  di=[0]*26
  for si in s:
    di[a2n(si)]+=1
    d.append(di.copy())
  d=np.array(d)
  for qi in q:
    if qi[0]=='1':
      i=int(qi[1])
      c=a2n(qi[2])
      si=a2n(s[i-1])
      d[i:,c]+=1
      d[i:,si]-=1
      s[i-1]=qi[2]
    else:
      l,r=int(qi[1]),int(qi[2])
      ld=d[l-1]
      rd=d[r]
      print(len([i for i in range(26) if rd[i]-ld[i]>0]))
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

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

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

ans = []
for i in range(q):
    query = input().split()
    if query[0] == "1":
        s[int(query[1])-1] = query[2]
    else:
        ans.append(len(set(s[int(query[1])-1:int(query[2])])))

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

ind_list = [[] for _ in range(26)]

for i, x in enumerate(s):
    ind_list[ord(x)-97].append(i)

for _ in range(q):
    _type, val1, val2 = input().split()
    if _type == '1':
        i = int(val1)-1
        c = val2
        if s[i] == c:
            continue
        ind_list[ord(s[i])-97].remove(i)
        ind_list[ord(c)-97].append(i)
        ind_list[ord(c)-97].sort()
        s[i] = c
    elif _type == '2':
        l = int(val1)-1
        r = int(val2)-1
        ans = 0
        for i in range(26):
            if bisect_right(ind_list[i], r) - bisect_left(ind_list[i], l) > 0:
                ans += 1
        print(ans)
    else:
        print('Exception caught!')
        exit()