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: Wrong Answer

Solution code:
n=int(input())
S=input()
q=int(input())

D=[[0]*26 for _ in range(n+1)]
for i,s in enumerate(S):
  for j in range(26):
    if j==ord(s)-97:
      D[i+1][j]=D[i][j]+1
    else:
      D[i+1][j]=D[i][j]

n_max=5*10**5
nn=n_max.bit_length()+1
BITS=[[0]*(2**nn) for _ in range(26)]
for i in range(26):
  BITS[i].insert(0,0)

def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT

for _ in range(q):
  q1,q2,q3=map(str,input().split())
  if q1=="1":
    num=int(q2)-1
    prev=ord(S[num])-97
    new=ord(q3)-97
    bitadd(BITS[prev],num,-1)
    bitadd(BITS[new],num,1)
  else:
    l,r=int(q2),int(q3)
    ans=0
    for i in range(26):
      diff=D[r][i]-D[l-1][i]+bitsum(BITS[i],r)-bitsum(BITS[i],l-1)
      if diff:
        ans+=1
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

def main():
  n = int(input())
  s = input()
  q = int(input())
  queries = [list(input().split()) for i in range(q)]
  for query in queries:
    if query[0] == "1":
      a = int(query[1]) - 1
      s = s[:a] + query[2] + s[a:]
    else:
      start = int(query[1]) - 1
      end = int(query[2])
      ans = set(s[start:end])
      print(len(ans))
      
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        # 引数が1つなら一点の値を取得
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

N = INT()
S = [ord(c)-97 for c in input()]
BITs = [BIT(N+1) for i in range(26)]
for i, s in enumerate(S):
    BITs[s].add(i, 1)

Q = INT()
for _ in range(Q):
    q = list(input().split())
    if q[0] == '1':
        _, i, c = q
        i = int(i) - 1
        c = ord(c) - 97
        if S[i] != c:
            prev = S[i]
            BITs[prev].add(i, -1)
            BITs[c].add(i, 1)
    else:
        _, l, r = q
        l, r = int(l) - 1, int(r) - 1
        ans = 0
        for c in range(26):
            if BITs[c].get(l, r+1) > 0:
                ans += 1
        print(ans)

Submission status: Wrong Answer

Solution code:
class SegmentTree1():
    """
    1-indexed Segment Tree
    """
    def __init__(self, n_, ele_id, operation_func):
        self.n = 1 << (n_ - 1).bit_length()  # size
        self.data = [ele_id] * (2 * self.n)  # binary tree
        self.ele_id = ele_id  # identity element
        self.operation_func = operation_func  # binary operation of monoid

    def __getitem__(self, idx):
        return self.data[idx + self.n]

    def build(self, data_init):
        for i in range(len(data_init)):
            self.data[i + self.n] = data_init[i]
        for i in range(self.n - 1, 0, -1):
            self.data[i] = self.operation_func(self.data[2 * i],
                                               self.data[2 * i + 1])

    def update(self, idx, x):
        # change idx-th element to x (idx : 0-indexed)
        idx += self.n
        self.data[idx] = x
        while idx > 1:
            idx = idx >> 1
            self.data[idx] = self.operation_func(self.data[2 * idx],
                                                 self.data[2 * idx + 1])

    def query(self, l, r):
        # query for interval [l, r) (l, r : 0-indexed)
        l += self.n
        r += self.n
        ret = self.ele_id
        while l < r:
            if l & 1:  # right child
                ret = self.operation_func(ret, self.data[l])
                l += 1
            if r & 1:  # right child
                r -= 1
                ret = self.operation_func(ret, self.data[r])
            # go to parent-nodes
            l = l >> 1
            r = r >> 1
        return ret


n = int(input())
s = input()
ELE = set()
operation_func = lambda a, b: a | b
st_set = SegmentTree1(n, ELE, operation_func)
st_set.build([set(si) for si in s])
q = int(input())
for _ in range(q):
    k, a, b = input().split()
    k = int(k)
    a = int(a)
    if k == 1:
        # type1: update
        st_set.update(a, set(b))
    else:
        # type2: calc
        b = int(b)
        a -= 1
        print(len(st_set.query(a, b)))

Submission status: Wrong Answer

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

for i in range(Q):
	typ , a, b = input().split()
	if(typ == '1'):
		i = int(a)
		c = b
		if(i == 0):
			S = c + S[1:]
		else:
			S = S[:i-1] + c + S[i+1:]

	
	if(typ == '2'):
		l = int(a)
		r = int(b)
		S_part = S[l-1:r]

		print(len(set(S_part)))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [ord(i) - 97 for i in input()]
Q = int(input())

# 添字が1から始まることに注意
class BinaryIndexedTree() :
  def __init__(self, N) :
    self.size = N
    self.tree = [0] * (N + 1)
      
  def sum(self, i) :
    s = 0
    while i > 0 :
      s += self.tree[i]
      i -= i & -i
    return s
      
  def add(self, i, x) :
    while i <= self.size :
      self.tree[i] += x
      i += i & -i
      
alph = [BinaryIndexedTree(N + 10) for i in range(26)]
for i in range(N) :
  alph[S[i]].add(i + 1, 1)

for _ in range(Q) :
  type, x, y = input().split()
  if type == '1' :
    x = int(x)
    s = S[x - 1]
    alph[s].add(x, -1)
    alph[ord(y) - 97].add(x, 1)
  else :
    x, y = int(x), int(y)
    ret = 0
    for i in range(26) :
      if alph[i].sum(y) - alph[i].sum(x - 1) > 0 :
        ret += 1
    print(ret)

Submission status: Wrong Answer

Solution code:

class BinaryIndexedTree:
    def __init__(self, size):
        size = 1 << (size-1).bit_length()
        self.data = [0] * (size+1)
        self.size = size
    
    def add(self, i, w):
        i += 1
        while i <= self.size:
            self.data[i] += w
            i += i & -i

    def sum(self, i):
        """
        [0,i)
        """
        result = 0
        while i > 0:
            result += self.data[i]
            i -= i & -i
        return result

    __getitem__ = sum

    def lower_bound(self, v):
        """
        return smallest i such that v < sum(data[:i])
        """

        s,pos = 0,0
        N = self.size
        k = N
        while k > 0:
            i = pos+k
            if i <= N:
                x = s+self.data[i]
                if x < v:
                    s = x
                    pos = i
            k >>= 1
        return pos

N = int(input())
S = input()
S = list(ord(c)-ord('a') for c in S)
bits = tuple(BinaryIndexedTree(N) for _ in range(26))

for i,c in enumerate(S):
    bit = bits[c]
    bit.add(i, 1)


def q1(i, c):
    i = int(i)-1
    c = ord(c)-ord('c')
    bit = bits[S[i]]
    bit.add(i,-1)
    bit = bits[c]
    bit.add(i,1)
    S[i] = c
def q2(l,r):
    l,r = int(l)-1,int(r)
    print(sum(bit.sum(r) > bit.sum(l) for bit in bits))


Q = int(input())
for _ in range(Q):
    q,x,y = input().split()

    if q == '1':
        q1(x,y)
    else:
        q2(x,y)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    class Bit:
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

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

        def add(self, i, x):
            while i <= self.size:
                self.tree[i] += x
                i += i & -i

    N = int(input())
    S = input().rstrip('\n')
    Q = int(input())

    bit = [Bit(N) for _ in range(26)]
    for i, s in enumerate(S):
        j = ord(s) - 97
        bit[j].add(i+1, 1)
    for _ in range(Q):
        flg, l, r = input().split()
        if flg == '1':
            i = int(l)
            c = r
            si = S[i-1]
            bit[ord(si)-97].add(i, -1)
            bit[ord(c)-97].add(i, 1)
        else:
            l = int(l)
            r = int(r)
            ans = 0
            for j in range(26):
                if bit[j].sum(r) - bit[j].sum(l-1):
                    ans += 1
            print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
    A='abcdefghijklmnopqrstuvwxyz'
    D=dict()
    for i,a in enumerate(A):
        D[a]=i
    n=int(input())
    S=input().strip()
    L=[set() for _ in range(26)]
    for i,s in enumerate(S):
        k=D[s]
        L[k].add(i)
    q=int(input())
    for _ in range(q):
        #print(L)
        k,a,b=input().strip().split()
        if k=='1':
            i=int(a)-1
            s=S[i]
            l1=D[s]
            l2=D[b]
            L[l1].discard(i)
            L[l2].add(i)
        else:
            l=int(a)-1
            r=int(b)-1
            #print(L)
            ans=0
            for i in range(26):
                if not L[i]:
                    continue
                B=list(L[i])
                B.sort()
                if not (l>B[-1] or r<B[0]):
                    #print(B)
                    ans+=1
            print(ans)
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


class SegTree:
    def __init__(self, N):
        self.N = N
        self._N = 1<<((N-1).bit_length())
        self.node = [0]*2*self._N

    def build(self,lis):
        for i in range(self.N):
            self.node[i+self._N-1] = lis[i]
        for i in range(self._N-2,-1,-1):
            self.node[i] = self.node[i*2+1] | self.node[i*2+2]
        return

    def update(self,i,x):
        i += self._N-1
        self.node[i] = x
        while i:
            i >>= 1
            self.node[i] = self.node[i*2+1] | self.node[i*2+2]

    def query(self,p,q,idx=0,a=0,b=None):
        if b is None:
            b = self._N
        if q <= p or b <= p or q <= a:
            return 0
        elif p <= a and b <= q:
            return self.node[idx]
        else:
            res1 = self.query(p,q,idx*2+1,a,(a+b)//2)
            res2 = self.query(p,q,idx*2+2,(a+b)//2,b)
            return res1 | res2

n = ni()
oa = ord('a')
s = list(map(lambda x: 1<<(ord(x)-oa), list(input())))
q = ni()
S = SegTree(n)
S.build(s)
for _ in range(q):
    x,y,z = input().split()
    if x == '1':
        y = int(y)
        S.update(y-1, 1<<(ord(z)-oa))
    else:
        y = int(y)
        z = int(z)
        v = S.query(y-1,z)
        print(popcount(v))

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007
import operator
class SegmentTree:
    def __init__(self, size, default, op = operator.add):
        self.size = 2**size.bit_length()
        self.dat = [default]*(self.size*2)
        self.op = op

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

    def add(self, i, x):
        i += self.size
        self.dat[i] = self.op(self.dat[i], x)
        while i > 0:
            i >>= 1
            self.dat[i] = self.op(self.dat[i], x)

    def get(self, a, b = None):
        if b is None:
            b = a + 1
        l, r = a + self.size, b + self.size
        res = None
        while l < r:
            if l & 1:
                if res is None:
                    res = self.dat[l]
                else:
                    res = self.op(res, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                if res is None:
                    res = self.dat[r]
                else:
                    res = self.op(res, self.dat[r])
            l >>= 1
            r >>= 1
        return res
def solve():
    n = I()
    S = list(input())
    m = ord("z")-ord("a")+1
    s = [SegmentTree(n,0) for i in range(m)]
    for i in range(n):
        k = ord(S[i])-ord("a")
        s[k].update(i,1)
    Q = I()
    for _ in range(Q):
        q = input().split()
        if q[0] == "1":
            i = int(q[1])-1
            if S[i] == q[2]:
                continue
            k = ord(S[i])-ord("a")
            s[k].update(i,0)
            k = ord(q[2])-ord("a")
            s[k].update(i,1)
        else:
            l,r = q[1:]
            l = int(l)
            r = int(r)
            ans = 0
            for k in range(m):
                if s[k].get(l-1,r):
                    ans += 1
            print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def interval_sum(self, i, j): # i <= x < j の区間
        return self.sum(j - 1) - self.sum(i - 1)


n = I()
S = S()
D = defaultdict(lambda:BIT(n))
for i in range(n):
    D[S[i]].add(i, 1)

q = I()
for j in range(q):
    qi, a, b = LS()
    a = int(a)
    if qi == '1':
        D[S[a - 1]].add(a, -1)
        D[b].add(a, 1)
    else:
        ret = 0
        for i in range(97, 123):
            if D[chr(i)].interval_sum(a - 1, int(b)):
                ret += 1
        print(ret)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007
import operator
class SegmentTree:
    def __init__(self, size, default, op = operator.add):
        self.size = 2**size.bit_length()
        self.dat = [default]*(self.size*2)
        self.op = op

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

    def add(self, i, x):
        i += self.size
        self.dat[i] = self.op(self.dat[i], x)
        while i > 0:
            i >>= 1
            self.dat[i] = self.op(self.dat[i], x)

    def get(self, a, b = None):
        if b is None:
            b = a + 1
        l, r = a + self.size, b + self.size
        res = None
        while l < r:
            if l & 1:
                if res is None:
                    res = self.dat[l]
                else:
                    res = self.op(res, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                if res is None:
                    res = self.dat[r]
                else:
                    res = self.op(res, self.dat[r])
            l >>= 1
            r >>= 1
        return res
def solve():
    n = I()
    S = list(input())
    m = ord("z")-ord("a")+1
    print(m)
    s = [SegmentTree(n,0) for i in range(m)]
    for i in range(n):
        k = ord(S[i])-ord("a")
        s[k].update(i,1)
    Q = I()
    for _ in range(Q):
        q = input().split()
        if q[0] == "1":
            i = int(q[1])-1
            if S[i] == q[2]:
                continue
            k = ord(S[i])-ord("a")
            s[k].update(i,0)
            k = ord(q[2])-ord("a")
            s[k].update(i,1)
        else:
            l,r = q[1:]
            l = int(l)
            r = int(r)
            ans = 0
            for k in range(m):
                if s[k].get(l-1,r):
                    ans += 1
            print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

class Node:
    def __init__(self,value,index=0):
        self.value = value
        self.index = index

    def __str__(self):
        return 'val : ' + str(self.value) + ' index : ' + str(self.index)

# 0-indexed SegmentTree
class SegmentTree:
    def __init__(self,N,default_list,default_value=INF):
        self.N0 = pow(2,(N-1).bit_length())
        self.nodes = [Node(default_value,i+1-self.N0) for i in range(2*self.N0-1)]
        for i in reversed(range(2*self.N0-1)):
            ind = i+1-self.N0
            if ind >= N:
                self.nodes[i].value = default_value
            elif N > ind >= 0:
                self.nodes[i].value = default_list[ind]
            else:
                self.nodes[i] = self.process(self.nodes[i*2+1],self.nodes[i*2+2])

    def __getitem__(self,key): # getiten : ST[i]
        return self.nodes[key+self.N0-1].value

    def __setitem__(self,i,x): # update : ST[i] = x
        i += self.N0 - 1
        self.nodes[i].value = x
        while i > 0:
            i = (i-1)//2
            self.nodes[i] = self.process(self.nodes[i*2+1],self.nodes[i*2+2])

    def __str__(self):
        return '['+', '.join(map(str,[self.nodes[i+self.N0-1].value for i in range(self.N0)]))+']'

    def query(self,L,R): #[L,R)の値
        retnode = Node(0,0)
        L += self.N0
        R += self.N0
        while L < R:
            if R&1 :
                R -= 1
                retnode = self.process(retnode,self.nodes[R-1])
            if L&1 :
                retnode = self.process(retnode,self.nodes[L-1])
                L += 1
            L >>= 1; R >>= 1
        return retnode

    def process(self,node_x,node_y): #x,yが子の時，親に返る値
        return Node(node_x.value|node_y.value)

N = inp()
S = list(input())

a = ord("a")
slist = []
for s in S:
    slist.append(1<<(ord(s)-a))


ST = SegmentTree(N, default_list=slist, default_value=0)

Q = inp()
ans = []
for _ in range(Q):
    a,b,c = input().split()
    if a == "2":
        ret = ST.query(int(b)-1,int(c))
        ans.append(str(bin(ret.value)).count("1"))
    else:
        tmp = 1<<(ord(c)-ord("a"))
        ST[int(b)] = tmp


print("\n".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    N = int(input())
    S = list(input())
    Q = int(input())
    charcum = [[0]*(N+1) for _ in range(26)]
    alphabets = list("abcdefghijklmnopqrstuvwxyz")
    c2n = {c: i for i, c in enumerate(alphabets)}
    n2c = {i: c for c, i in c2n.items()}

    for char in alphabets:
        num = c2n[char]
        for i in range(1, N+1):
            charcum[num][i] = charcum[num][i-1] + int(S[i-1]==char)
    # delta = [[0]*(N+1) for _ in range(26)]
    change = {char: [] for char in range(26)}
    for _ in range(Q):
        tmp = list(input().split())
        if tmp[0] == "1":
            _, i, c = tmp
            i = int(i)
            bef = S[i-1]
            if bef == c:
                continue
            change[c2n[bef]].append((i, -1))
            change[c2n[c]].append((i, 1))
            S[i-1] = c
            # delta[c2n[bef]][i] -= 1
            # delta[c2n[c]][i] += 1
        else:
            _, l, r = tmp
            l = int(l)
            r = int(r)
            ans = 0
            for char in range(26):
                cum_l = charcum[char][l-1]
                cum_r = charcum[char][r]
                for idx, d_cum in change[char]:
                    if idx <= l-1:
                        cum_l += d_cum
                        cum_r += d_cum
                    elif l <= idx <= r:
                        cum_r += d_cum
                if cum_r - cum_l > 0:
                    ans += 1
            print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
s = [ord(i)-97 for i in s]

dic = {}
for i in range(26):
    dic[i] = []

for i in range(n):
    dic[s[i]].append(i)

for i in range(26):
    dic[i].append(float('inf'))

from bisect import bisect_left
q = int(input())
for i in range(q):
    x, y, z = input().split()
    if x == '1':
        y, z = int(y) - 1, ord(z) - 97
        p = bisect_left(dic[s[y]], y)
        dic[s[y]].pop(p)
        dic[z].insert(bisect_left(dic[z], y), y)
        s[y] = z
    else:
        res = 0
        y, z = int(y) - 1, int(z) - 1
        for i in range(26):
            p = dic[i][bisect_left(dic[i], y)]
            if p <= z:
                res += 1
        print(res)

Submission status: Time Limit Exceeded

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

dic = {}
for i in range(26):
    dic[chr(i+97)] = []

for i in range(n):
    dic[s[i]].append(i)

for i in range(26):
    dic[chr(i+97)].append(float('inf'))

from bisect import bisect_left
q = int(input())
for i in range(q):
    x, y, z = input().split()
    if x == '1':
        y = int(y) - 1
        p = bisect_left(dic[s[y]], y)
        dic[s[y]].pop(p)
        dic[z].insert(bisect_left(dic[z], y), y)
        s[y] = z
    else:
        res = 0
        y, z = int(y) - 1, int(z) - 1
        for i in range(26):
            p = dic[chr(i+97)][bisect_left(dic[chr(i+97)], y)]
            if p <= z:
                res += 1
        print(res)

Submission status: Time Limit Exceeded

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

for _ in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, c = int(query[1]), query[2]
        S[i-1] = c
    elif query[0] == '2':
        l, r = int(query[1]), int(query[2])
        S_set = set(S[(l - 1):r])
        print(len(S_set))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q = int(input())
for _ in range(q):
  t,a,b = map(str,input().split())
  if t == '1':
    s[int(a)-1] = b
  else:
    print(len(set(s[int(a)-1:int(b)])))

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)

    def add(self, i, x=1):
        i += 1
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def get_sum(self, i):
        i += 1
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i & -i
        return x

    # Return sum for [l, r)
    def get_sum_range(self, l, r):
        return self.get_sum(r - 1) - self.get_sum(l - 1)


def main():
    N = int(readline())
    S = readline().strip()
    Q = int(readline())
    query = [readline().split() for _ in range(Q)]

    bit = [BIT(N) for _ in range(26)]
    for i, c in enumerate(S):
        bit[ord(c) - ord('a')].add(i)

    S = list(S)
    ans = []

    for q in query:
        if q[0] == '1':
            i = int(q[1]) - 1
            c = q[2]
            bit[ord(S[i]) - ord('a')].add(i, -1)
            bit[ord(c) - ord('a')].add(i, 1)
            S[i] = c
        else:
            res = 0
            l, r = int(q[1]) - 1, int(q[2]) - 1
            for i in range(26):
                if bit[i].get_sum_range(l, r + 1):
                    res += 1
            ans.append(res)

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

    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    class segTree:
        def __init__(self,n):
            if bin(n).count("1") == 1:
                self.leaves = 2**(n.bit_length()-1)
            else:
                self.leaves = 2**n.bit_length()
            self.identity = set()
            self.tree = [self.identity]*(self.leaves*2)

        def merge(self,x,y):
            #ここにマージ処理を書く
            return x | y

        def update(self,i,x):
            i = i+self.leaves
            self.tree[i] = set(x)
            i >>= 1
            while i > 0:
                self.tree[i] = self.merge(self.tree[i*2],self.tree[i*2+1])
                i >>= 1

        def query(self,l,r):
            #[l:r)のクエリ結果を返す
            l = l + self.leaves
            r = r + self.leaves
            res = self.identity
            while l < r:
                if l&1:
                    res = self.merge(res,self.tree[l])
                    l += 1
                if r&1:
                    r -= 1
                    res = self.merge(res,self.tree[r])
                l >>= 1
                r >>= 1
            return res
    N = int(input())
    st = segTree(N)
    S = input()
    Q = int(input())
    for i in range(N):
        st.update(i,S[i])

    for _ in range(Q):
        q,a,b = input().split()
        if q == "1":
            st.update(int(a)-1,b)
        else:
            print(len(st.query(int(a)-1,int(b))))
main()

Submission status: Time Limit Exceeded

Solution code:
class segTree:
    def __init__(self,n):
        if bin(n).count("1") == 1:
            self.leaves = 2**(n.bit_length()-1)
        else:
            self.leaves = 2**n.bit_length()
        self.identity = set()
        self.tree = [self.identity]*(self.leaves*2)

    def merge(self,x,y):
        #ここにマージ処理を書く
        return x | y

    def update(self,i,x):
        i = i+self.leaves
        self.tree[i] = set(x)
        i >>= 1
        while i > 0:
            self.tree[i] = self.merge(self.tree[i*2],self.tree[i*2+1])
            i >>= 1

    def query(self,l,r):
        #[l:r)のクエリ結果を返す
        l = l + self.leaves
        r = r + self.leaves
        res = self.identity
        while l < r:
            if l&1:
                res = self.merge(res,self.tree[l])
                l += 1
            if r&1:
                r -= 1
                res = self.merge(res,self.tree[r])
            l >>= 1
            r >>= 1
        return res
N = int(input())
st = segTree(N)
S = input()
Q = int(input())
for i in range(N):
    st.update(i,S[i])

for _ in range(Q):
    q,a,b = input().split()
    if q == "1":
        st.update(int(a)-1,b)
    else:
        print(len(st.query(int(a)-1,int(b))))