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:
f=input
n,s,q=int(f()),list(f()),int(f())
d={chr(97+i):[] for i in range(26)}
for i in range(n):
  d[s[i]]+=[i]
from bisect import *
for i in range(q):
  a,b,c=input().split()
  b=int(b)-1
  if a=='1':
    d[s[b]].pop(bisect(d[s[b]],b)-1)
    s[b]=c
    insort(d[c],b)
  else:
    t=0
    for l in d.values():
      m=bisect(l,b-1)
      if m<len(l) and l[m]<int(c): t+=1
    print(t)

Submission status: Time Limit Exceeded

Solution code:
f=input
n,s,q=int(f()),list(f()),int(f())
L=[[] for i in range(26)]
for i in range(n):
  L[ord(s[i])-97].append(i)
from bisect import *
for i in range(q):
  a,b,c=input().split()
  b=int(b)-1
  if a=='1':
    l=L[ord(s[b])-97]
    l.pop(bisect(l,b)-1)
    s[b]=c
    insort(L[ord(c)-97],b)
  else:
    t=0
    for l in L:
      m=bisect(l,b-1)
      if m<len(l) and l[m]<int(c): t+=1
    print(t)

Submission status: Time Limit Exceeded

Solution code:
f=input
n,s,q=int(f()),list(f()),int(f())
L=[[] for i in range(26)]
for i in range(n):
  L[ord(s[i])-97]+=[i]
from bisect import *
for i in range(q):
  a,b,c=input().split()
  b=int(b)-1
  if a=='1':
    l=L[ord(s[b])-97]
    l.pop(bisect(l,b)-1)
    s[b]=c
    insort(L[ord(c)-97],b)
  else:
    t=0
    for l in L:
      m=bisect(l,b-1)
      if m<len(l) and l[m]<int(c): t+=1
    print(t)

Submission status: Time Limit Exceeded

Solution code:
f=input
n,s,q=int(f()),list(f()),int(f())
L=[[]*n for i in range(26)]
for i in range(n):
  L[ord(s[i])-97]+=[i]
from bisect import *
for i in range(q):
  a,b,c=input().split(); b=int(b)-1
  if a=='1':
    l=L[ord(s[b])-97]
    l.pop(bisect(l,b)-1)
    s[b]=c
    insort(L[ord(c)-97],b)
  else:
    t=0
    for l in L:
      m=bisect(l,b-1)
      if m<len(l) and l[m]<int(c): t+=1
    print(t)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = [0] + list(input())
Q = int(input())

Query = [list(input().split()) for i in range(Q)]

for i in range(Q):
    if Query[i][0] == '1':
        S[int(Query[i][1])] = Query[i][2]
    else:
        s = {S[j] for j in range(int(Query[i][1]),int(Query[i][2])+1)}
        print(len(s))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = [0] + list(input())
Q = int(input())

Query = [list(input().split()) for i in range(Q)]

for i in range(Q):
    if Query[i][0] == '1':
        S[int(Query[i][1])] = Query[i][2]
    else:
        s = set([])
        for j in range(int(Query[i][1]),int(Query[i][2])+1):
            s.add(S[j])
        print(len(s))

Submission status: Time Limit Exceeded

Solution code:
s=int(input())
a=list(input())
n=int(input())
for i in range(n):
    x,y,z=map(str,input().split())
    if(int(x)==1):
        y=int(y)
        a[y-1]=z
    else:
        y,z=int(y),int(z)
        w=set(a[y-1:z])
        print(len(w))

Submission status: Time Limit Exceeded

Solution code:
#segtree ライブラリ
#BITライブラリの作成
#リストの要素を1,0で長さをｎとした時に使える
class BIT:
    def __init__(self,n):
        self.n=n
        self.data=[0]*(n+1)
    def to_sum(self,i):
        s=0     
        while i>0:
            s+=self.data[i]
            i-=(i& -i)
        return s
    def add(self,i,x):
        while i<=self.n:
            self.data[i]+=x
            i+=(i & -i)
    def get(self,i,j):
        return self.to_sum(j)-self.to_sum(i-1)
n=int(input())
s=list(input())
q=int(input())
que=[]

for i in range(q):
    p=list(input().split())
    que.append(p)
alpha="abcdefghijklmnopqrstuvwxyz"
segtree={alpha[i]:BIT(n) for i in range(26)}  
for i in range(n):
    segtree[s[i]].add(i+1,1)
for q in que:
    x,y,z=q[0],q[1],q[2]
    if int(x)==1:
        #y文字目をzに変更する
        y=int(y)  
        for i in range(26):
            if segtree[alpha[i]].get(y,y)==1:
                segtree[alpha[i]].add(y,-1)
                break
        segtree[z].add(y,1)
    else:
        ans=0
        for i in range(26):
            if segtree[alpha[i]].get(int(y),int(z))>0:
                ans+=1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    def segfunc(x, y):
        return x | y

    def init(arr):
        for i in range(n):
            seg[i+num-1] = set(arr[i])
        for i in range(num-2,-1,-1) :
            seg[i] = segfunc(seg[2*i+1],seg[2*i+2]) 
        
    def update(k,x):
        k += num-1
        seg[k].clear()
        seg[k] = set(x)
        while k:
            k = (k-1)//2
            seg[k].clear()
            seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
        
    def query(p,q):
        if q<=p:
            return ide_ele
        p += num-1
        q += num-2
        res=ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res,seg[p])
            if q&1 == 1:
                res = segfunc(res,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res,seg[p])
        else:
            res = segfunc(segfunc(res,seg[p]),seg[q])
        return res

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

    ide_ele = set()

    num =2**((n-1).bit_length())

    # セグ木初期化
    seg=[ide_ele]*2*num
    init(s)

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections

n=int(input())
s=list(input())
Q=int(input())
q=[]
for i in range(Q):
    x=input().split()
    q.append(x)

for i in range(Q):
    if q[i][0]=="1":
        s[int(q[i][1])-1]= q[i][2]
    elif q[i][0]=="2":
        u=s[int(q[i][1])-1: int(q[i][2])]
        print(len(collections.Counter(u)))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from collections import defaultdict
sys.setrecursionlimit(10**7)

def run():

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

    bins = [0] * N# a: ord('a') - 97
    for i,s in enumerate(S):
        id = ord(s) - 97
        bins[i] |= 1<<id

    for type, i, c in queries:
        if type == '1':
            i = int(i) - 1
            old = ord(S[i]) - 97
            new = ord(c) - 97
            bins[i] -= 1<<old
            bins[i] |= 1<<new
            S[i] = c
        else:
            i,c= int(i), int(c)
            ret = 0
            for k in range(i-1, c):
                ret |= bins[k]

            print(bin(ret).count("1"))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from collections import defaultdict
sys.setrecursionlimit(10**7)

def run():

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

    bins = [0] * 26# a: ord('a') - 97
    for i,s in enumerate(S[::-1]):
        id = ord(s) - 97
        bins[id] |= 1<<i

    for type, i, c in queries:
        if type == '1':
            i = int(i) - 1
            old = ord(S[i]) - 97
            new = ord(c) - 97
            bins[old] -= 1<<(N-1-i)
            bins[new] |= 1<<(N-1-i)
            S[i] = c
        else:
            i,c= int(i), int(c)
            ret = 0
            for v in bins:
                v >>= N-c
                if v & ((1<<c-i+1)-1):
                    ret+=1
            print(ret)

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from collections import defaultdict
sys.setrecursionlimit(10**7)

def run():

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

    bins = [0] * 26# a: ord('a') - 97
    for i,s in enumerate(S[::-1]):
        id = ord(s) - 97
        bins[id] |= 1<<i

    for type, i, c in queries:
        if type == '1':
            i = int(i) - 1
            old = ord(S[i]) - 97
            new = ord(c) - 97
            bins[old] -= 1<<(N-1-i)
            bins[new] |= 1<<(N-1-i)
            S[i] = c
        else:
            i,c= int(i), int(c)
            ret = 0
            for v in bins:
                v >>= N-c
                if v & int("1"*(c-i+1),2):
                    ret+=1
            print(ret)

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
sys.setrecursionlimit(10**7)
def run():

    N = int(sysread())
    S = list('0'+input())
    Q = int(sysread())
    queries = []
    for _ in range(Q):
        queries.append(sysread().split())

    for t, i, c in queries:
        if t == '1':
            i = int(i)
            S[i] = c
        else:
            i,c = int(i), int(c)
            tmp = S[i:c+1]
            count = len(set(tmp))
            print(count)
if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
sys.setrecursionlimit(10**7)
import numpy as np
def run():
    N = int(sysread())
    S = list('0'+input())
    Q = int(sysread())
    queries = []
    for _ in range(Q):
        queries.append(sysread().split())

    a2z = 'abcdefghijklmnopqrstuvwxyz'
    a2num = {val:idx for idx, val in enumerate(a2z)}
    counts = np.array([[0] * len(a2z) for _ in range(N+1)])
    counts[1][a2num[S[1]]] += 1
    for idx, s in enumerate(S[2:],2):
        counts[idx, :] = counts[idx-1, :]
        counts[idx, a2num[s]] += 1

    for t, i, c in queries:
        if t == '1':
            i = int(i)
            counts[i:, a2num[S[i]]] -= 1
            counts[i:, a2num[c]] += 1
            S[i] = c
        else:
            i,c = int(i), int(c)
            count = (counts[c,:] - counts[i-1, :] > 0).sum()
            print(count)
if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from itertools import combinations
sys.setrecursionlimit(10**7)
#import numpy as np
def run():

    N = int(sysread())
    S = list('0'+input())
    Q = int(sysread())
    queries = []
    for _ in range(Q):
        queries.append(sysread().split())

    a2z = 'abcdefghijklmnopqrstuvwxyz'
    a2num = {val:idx for idx, val in enumerate(a2z)}
    counts = [[0] * len(a2z) for _ in range(N+1)]
    counts[1][a2num[S[1]]] += 1
    for idx, s in enumerate(S[2:],2):
        for k in range(len(a2z)):
            counts[idx][k] = counts[idx-1][k]
        counts[idx][a2num[s]] += 1

    for t, i, c in queries:
        if t == '1':
            i = int(i)
            for k in range(i, N+1):
                counts[k][a2num[S[i]]] -= 1
                counts[k][a2num[c]] += 1
            S[i] = c
        else:
            count = 0
            i,c = int(i), int(c)
            for k in range(len(a2z)):
                count += int((counts[c][k] - counts[i-1][k]) > 0)
            print(count)
if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(input())
q=int(input())
que=[list(input().split()) for _ in range(q)]
for q1,q2,q3 in que:
  if q1=='1':
    s[int(q2)-1]=q3
  else:
    print(len(set(s[int(q2)-1:int(q3)])))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
import sys
readlines = sys.stdin.readline
def main():

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

	d = {}
	for i in range(n):
		d.setdefault(s[i], []).append(i)

	flag = {}
	for i in range(q):
		q1,q2,q3 = map(str,input().split())
		if q1 == '1':
			q2 = int(q2) - 1
			if s[q2] != q3:
				flag.setdefault(s[q2], []).append(q2)
				d.setdefault(q3, []).append(q2)
				flag[s[q2]].sort()
				d[q3].sort()
				s[q2] = q3
		else:
			ans = 0
			q2 = int(q2) - 1
			q3 = int(q3) - 1
			if q2 == q3:
				print(1)
				continue
			for string,l in d.items():
				res = 0
				left = bisect_left(l,q2)
				right = bisect_right(l,q3)
				if string in flag:
					left2 = bisect_left(flag[string],q2)
					right2 = bisect_right(flag[string],q3)
				else:
					left2 = 0
					right2 = 0
				if left != right:
					if right - left > right2 - left2:
						res = 1
				ans += res
				#print(string,l,res)
			print(ans)
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

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

d = {}
for i in range(n):
	d.setdefault(s[i], []).append(i)

flag = {}
for i in range(q):
	q1,q2,q3 = map(str,input().split())
	if q1 == '1':
		q2 = int(q2) - 1
		if s[q2] != q3:
			flag.setdefault(s[q2], []).append(q2)
			d.setdefault(q3, []).append(q2)
			flag[s[q2]].sort()
			d[q3].sort()
			s[q2] = q3
	else:
		ans = 0
		q2 = int(q2) - 1
		q3 = int(q3) - 1
		if q2 == q3:
			print(1)
			continue
		for string,l in d.items():
			res = 0
			left = bisect_left(l,q2)
			right = bisect_right(l,q3)
			if string in flag:
				left2 = bisect_left(flag[string],q2)
				right2 = bisect_right(flag[string],q3)
			else:
				left2 = 0
				right2 = 0
			if left != right:
				if right - left > right2 - left2:
					res = 1
			ans += res
			#print(string,l,res)
		print(ans)

Submission status: Time Limit Exceeded

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

for i in range(Q):
  inp = input().split()
  if inp[0] == "1":
    S[int(inp[1])-1] = inp[2]
  if inp[0] == "2":
    print(len(set(S[int(inp[1])-1:int(inp[2])])))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(input())
q=int(input())
for i in range(q):
  query=list(input().split())
  l=int(query[1])-1
  if query[0]=='1':
    s[l]=query[2]
  else:
    r=int(query[2])
    t=s[l:r]
    #print(t)
    print(len(set(t)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():

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


main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2) # 要素を単位元で初期化

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

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = lres | self.dat[l]
                l += 1
            if r & 1:
                r -= 1
                rres = self.dat[r] | rres # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = lres | rres
        return len(res)

N = ir()
S = sr()
seg = SegmentTree(N, default=set())
for i in range(N):
    seg.update(i, set(S[i]))
    
Q = ir()
for _ in range(Q):
    a, b, c = sr().split()
    if a == '1':
        seg.update(int(b)-1, set(c))
    else:
        print(seg.query(int(b)-1, int(c)))

# 03

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : x|y, default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2) # 要素を単位元で初期化
        self.f = f

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

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return len(res)

N = ir()
S = sr()
seg = SegmentTree(N, f=lambda x,y : x|y, default=set())
for i in range(N):
    seg.update(i, set(S[i]))
    
Q = ir()
for _ in range(Q):
    a, b, c = sr().split()
    if a == '1':
        seg.update(int(b)-1, set(c))
    else:
        print(seg.query(int(b)-1, int(c)))

# 03

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np

from operator import add

class segtree:

    def __init__(self, n,operator,identity):
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_leaves = 2**(len(nb)-1)
        else:
            self.num_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_leaves * 2)]
        self.identity = identity
        self.operator =operator
        self.n = n

    def build(self,init_arr):
        for i in range(self.n):
            self.array[i+self.num_leaves] = init_arr[i]
        for i in range(self.num_leaves):
            pt = self.num_leaves-1-i
            self.array[pt] = self.operator(self.array[pt*2],self.array[pt*2+1])


    def update(self,x,val):
        actual_x = x+self.num_leaves
        # self.array[actual_x] = self.operator(self.array[actual_x],val)
        self.array[actual_x] = val
        while actual_x > 0 :
            actual_x = actual_x//2
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        width_of_floor = self.num_leaves//(2**depth)
        leaf_right = leaf_left+width_of_floor-1

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
            return self.operator(val_l,val_r)

    def find(self, l, r):
        #findの方が高速
        l += self.num_leaves
        r += self.num_leaves+1
        ret = self.identity
        while l < r:
            if l & 1:
                ret = self.operator(ret, self.array[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.operator(ret, self.array[r])
            l //= 2
            r //= 2
        return ret







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

trees = [segtree(n, add, 0) for i in range(26)]
buf = [[0 for i in range(n)] for j in range(26)]


for i in range(n):
    c = ord(s[i]) - 97
    buf[c][i] = 1


for i in range(26):
    trees[i].build(buf[i])




s = list(s)

for i in range(q):
    ty, i, c = input().split()

    if ty == "1":
        i = int(i)
        ct = ord(c) - 97
        base = ord(s[i-1])-97
        if base == ct:
            continue
        # print(c,s[i-1],i-1)
        trees[ct].update(i-1,1)
        trees[base].update(i-1,0)
        s[i-1] = c
        # print(s)
        # print(trees[base].array[8:])
    else:
        i = int(i)
        c = int(c)
        i -= 1
        c -= 1
        tp = 0
        for j in range(26):
            # print(trees[j].find(i,c),end=" ")
            if trees[j].find(i,c) > 0:
                tp += 1
        print(tp)
# for t in trees:
#     print(t.array[8:])

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np

class segtree:

    def __init__(self, n,operator,identity):
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_leaves = 2**(len(nb)-1)
        else:
            self.num_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_leaves * 2)]
        self.identity = identity
        self.operator =operator
        self.n = n

    def build(self,init_arr):
        for i in range(self.n):
            self.array[i+self.num_leaves] = init_arr[i]
        for i in range(self.num_leaves):
            pt = self.num_leaves-1-i
            self.array[pt] = self.operator(self.array[pt*2],self.array[pt*2+1])


    def update(self,x,val):
        actual_x = x+self.num_leaves
        # self.array[actual_x] = self.operator(self.array[actual_x],val)
        self.array[actual_x] = val
        while actual_x > 0 :
            actual_x = actual_x//2
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        width_of_floor = self.num_leaves//(2**depth)
        leaf_right = leaf_left+width_of_floor-1

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
            return self.operator(val_l,val_r)

    def find(self, l, r):
        l += self.num_leaves
        r += self.num_leaves+1
        ret = self.identity
        while l < r:
            if l & 1:
                ret = self.operator(ret, self.array[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.operator(ret, self.array[r])
            l //= 2
            r //= 2
        return ret




def addf(a, b):
    return a+b


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

trees = [segtree(n, addf, 0) for i in range(26)]
buf = [[0 for i in range(n)] for j in range(26)]


for i in range(n):
    c = ord(s[i]) - 97
    buf[c][i] = 1


for i in range(26):
    trees[i].build(buf[i])

# for t in trees:
#     print(t.array[8:])




s = list(s)

for i in range(q):
    ty, i, c = input().split()

    if ty == "1":
        i = int(i)
        ct = ord(c) - 97
        base = ord(s[i-1])-97
        if base == ct:
            continue
        # print(c,s[i-1],i-1)
        trees[ct].update(i-1,1)
        trees[base].update(i-1,0)
        s[i-1] = c
        # print(s)
        # print(trees[base].array[8:])
    else:
        i = int(i)
        c = int(c)
        i -= 1
        c -= 1
        tp = 0
        for j in range(26):
            # print(trees[j].find(i,c),end=" ")
            if trees[j].find(i,c) > 0:
                tp += 1
        print(tp)
# for t in trees:
#     print(t.array[8:])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
_s = input()
q = int(input())
query = [input() for _ in range(q)]

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

def bitadd(_bit, i, x):
    while i <= n:
        _bit[i] += x
        i += i & (-i)
    return _bit

al = [chr(ord('a') + i) for i in range(26)]
al_to_idx = dict()
for i in range(26):
    al_to_idx[al[i]] = i

s = list(_s).copy()

# init
import math
n_ = int(math.log2(n)) + 1
bit = [[0] * (2 ** n_ + 1) for _ in range(26)]
for i in range(n):
    idx = al_to_idx[s[i]]
    bit[idx] = bitadd(bit[idx], i + 1, 1)
# print(bit)

for i in range(q):
    _query = query[i].split(' ')
    if _query[0] == '1':
        # decrement old
        idx = al_to_idx[s[int(_query[1]) - 1]]
        bit[idx] = bitadd(bit[idx], int(_query[1]), -1)

        s[int(_query[1]) - 1] = _query[2]
        # print(s)

        # increment
        idx = al_to_idx[_query[2]]
        bit[idx] = bitadd(bit[idx], int(_query[1]), 1)

    else:
        _ans = 0
        for idx in range(26):
            _bit = bit[idx]
            c = bitsum(_bit, int(_query[2])) - bitsum(_bit, int(_query[1]) - 1)
            if c != 0:
                _ans += 1
        print(_ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**9)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import collections

n = ni()
s = ns()
s = list(s)
q = ni()

for i in range(q):
	a,b,c = nn()
	if int(a) == 1:
		s[int(b)-1] = c
	else:
		ss = collections.Counter(s[int(b)-1:int(c)])
		print(len(ss.keys()))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree():
    def __init__(self,n):
        self.e = 0
        self.r = 0 #ノードの段数
        cnt = 0
        while cnt<n:
            cnt=2**self.r
            self.r +=1
        self.tree = [self.e]*(2**self.r -1)# 0-index
        self.n = 2**(self.r-1) #一番下のnodeの数
    def func(self,a,b): #適宜書き換え
        return a|b
    def update(self,i,val):
        i += self.n -1
        self.tree[i] = val
        while i>0:
            i = (i-1)//2
            self.tree[i] = self.func(self.tree[i*2+1],self.tree[i*2+2])

    def query(self,l,r):
        l += self.n -1
        r += self.n -1 #開区間 idxはr-1
        lval = self.e
        rval = self.e
        while r>l:
            if l%2 == 0:
                lval = self.func(lval,self.tree[l])
                l+=1
            if r%2==0:
                rval = self.func(rval,self.tree[r-1])
                r-=1
            r//=2
            l//=2
        return self.func(lval,rval)
    def index(self,i):
        return i+self.n -1
def sid(s):
    return ord(s)-ord("a") #chr("a") == 0

import sys
input = sys.stdin.readline
n = int(input())
S = input()[:-1]
Q = int(input())
seg = SegmentTree(n)
for i in range(n):
    s = S[i]
    seg.update(i,2**(sid(s)))
for q in range(Q):
    num,a,b = input().split()
    if num=="1":
        seg.update(int(a)-1,2**sid(b))
        #print(a,b,list(map(lambda x:bin(x)[2:],seg.tree)))
    else:
        print(bin(seg.query(int(a)-1,int(b))).count("1"))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree(object):
    """
    セグメントツリー (0-indexed)

    1. 値の更新 O(logN)
    2. 区間クエリ O(logN)
    """
    def __BinOp(self, x, y):
        """ セグ木で使用する二項演算 """
        return x | y

    def __init__(self, init_ele, N:int):
        """
        セグ木を構築する

        init_ele: 単位元 
        N: 要素数
        """
        self.__init_ele = init_ele
        self.__n = 1
        while self.__n < N:
            self.__n <<= 1

        self.__dat = [init_ele] * (2 * self.__n)
    
    def update(self, k:int, x):
        """ k番目の値をxに変更する """
        k += self.__n - 1
        self.__dat[k] = x
        while k:
            k = (k - 1) // 2
            self.__dat[k] = self.__BinOp(
                self.__dat[k * 2 + 1], self.__dat[k * 2 + 2]
                )
    
    def query(self, p:int, q:int):
        """ 区間クエリ [p,q) """
        if q <= p: return self.__init_ele
        p += self.__n - 1
        q += self.__n - 2
        res = self.__init_ele
        while q - p > 1:
            if not (p & 1):
                res = self.__BinOp(res, self.__dat[p])
            if q & 1:
                res = self.__BinOp(res, self.__dat[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        res = self.__BinOp(res, self.__dat[p])
        if p != q: res = self.__BinOp(res, self.__dat[q])
        return res
    
    def get_num(self, k:int):
        """ k番目の値を取得する """
        k += self.__n - 1
        return self.__dat[k]

############################################################
from collections import defaultdict

N = int(input())

alpha = defaultdict(int)
for i, s in enumerate(range(ord('a'), ord('z') + 1)):
    alpha[chr(s)] = 1 << i

ST = SegmentTree(0, N)
for i, s in enumerate(tuple(input())):
    ST.update(i, alpha[s])

Q = int(input())
for _ in range(Q):
    x,y,z = map(str,input().split())
    x = int(x); y = int(y)
    if x == 1:
        ST.update(y - 1, alpha[z])
    else:
        z = int(z)
        print(bin(ST.query(y - 1, z)).count("1"))