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 numpy as np
N = int(input())
S = list(input())
Q = int(input())
Q_list = np.array([input().split() for _ in range(Q)])
t_list = []
def sub(S, q):
  S[int(q[1])-1] = q[2]
def pri(S, q):
  print(len(np.unique(S[int(q[1])-1:int(q[2])])))
[sub(S, q) for q in Q_list if(int(q[0])==1) or pri(S, q)]

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
S = list(input())
Q = int(input())
Q_list = [input().split() for _ in range(Q)]
t_list = []
def sub(S, q):
  S[int(q[1])-1] = q[2]
def pri(S, q):
  print(len(np.unique(S[int(q[1])-1:int(q[2])])))
[sub(S, q) for q in Q_list if(int(q[0])==1) or pri(S, q)]

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
S = list(input())
Q = int(input())
Q_list = [input().split() for _ in range(Q)]
t_list = []
for q in Q_list:
  type = int(q[0])
  if(type==1):
    S[int(q[1])-1] = q[2]
  else:
    s, e = int(q[1]), int(q[2])
    t = len(np.unique(S[s-1:e]))
    t_list.append(t)
[print(t) for t in t_list]

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
S = list(input())
Q = int(input())
Q_list = [input().split() for _ in range(Q)]
t_list = []
for q in Q_list:
  type = int(q[0])
  if(type==1):
    S[int(q[1])-1] = q[2]
  else:
    s, e = int(q[1]), int(q[2])
    t = 0
    str_list = []
    t = len(np.unique(S[s-1:e]))
    t_list.append(t)
[print(t) for t in t_list]

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
S = list(input())
Q = int(input())
Q_list = [input().split() for _ in range(Q)]
for q in Q_list:
  type = int(q[0])
  if(type==1):
    S[int(q[1])-1] = q[2]
  else:
    s, e = int(q[1]), int(q[2])
    t = 0
    str_list = []
    t = len(np.unique(S[s-1:e]))
    print(t)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
Q = int(input())
for i in range(Q):
  q = input().split()
  q[0] = int(q[0])
  q[1] = int(q[1])
  if(q[0]==1):
    S[q[1]-1] = q[2]
  else:
    q[2] = int(q[2])
    s, e = q[1], q[2]
    t = 0
    str_list = []
    for i in range(s-1,e):
      if(S[i] not in str_list):
        str_list.append(S[i])
        t += 1
    print(t)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
q = int(input())
for _ in range(q):
    i,x,y = input().split()
    if (i == "1"):
        x = int(x)
        s = s[:x-1] + y + s[x:]
    if (i == "2"):
        x = int(x)
        y = int(y)
        ans = s[x-1:y]
        st = set(ans)
        print(len(st))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
q = int(input())
for _ in range(q):
    i,x,y = input().split()
    if (i == "1"):
        x = int(x)
        li = list()
        for b in s:
            li.append(b)
        li[x-1] = y
        s = ""
        for b in li:
            s += b
    if (i == "2"):
        x = int(x)
        y = int(y)
        ans = s[x-1:y]
        st = set()
        for b in ans:
            st.add(b)
        print(len(st))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import collections
# 整数の入力
n = int(input())
s = list(input())
q = int(input())
# スペース区切りの整数の入力
query = [["0"]*3]*q
for i in range(q):
	query[i] = input().split()

for i in range(q):
  if query[i][0] == "1":
    s[int(query[i][1]) - 1] = query[i][2]
  else:
    c = dict(collections.Counter(s[int(query[i][1]) - 1:int(query[i][2]) ]))
    print("{}".format(len(c)))

Submission status: Time Limit Exceeded

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

n = int(input().rstrip('\n'))
s = input().rstrip('\n')
l = [c for c in s]
q = int(input().rstrip('\n'))
Q = [input().rstrip('\n').split() for _ in range(q)]

class SegTree():
    def __init__(self, n_):
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.tree = [2 for _ in range(2 * self.n - 1)]
    def update(self, k, a):
        k += self.n - 1
        self.tree[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.tree[k] = min(self.tree[k * 2 + 1], self.tree[k * 2 + 2])
    def query(self, l, r):
        l += self.n - 1
        r += self.n - 2
        res = 2
        while r-l>1:
            if l&1 == 0:
                res = min(res,self.tree[l])
            if r&1 == 1:
                res = min(res,self.tree[r])
                r -= 1
            l = l//2
            r = (r-1)//2
        if l == r:
            res = min(res,self.tree[l])
        else:
            res = min(min(res,self.tree[l]),self.tree[r])
        return res

d = { c: SegTree(n) for c in "abcdefghijklmnopqrstuvwxyz"}

for i, c in enumerate(s):
    d[c].update(i, 1)


for a, b, c in Q:
    if a == "1":
        b = int(b) - 1
        d[l[b]].update(b, 2)
        d[c].update(b, 1)
        l[b] = c
    else:
        res = 0
        b, c = int(b), int(c)
        for key in d:
            if d[key].query(b-1, c) == 1:
                res += 1
        print(res)

Submission status: Time Limit Exceeded

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

n = int(input().rstrip('\n'))
s = input().rstrip('\n')
l = [c for c in s]
q = int(input().rstrip('\n'))
Q = [input().rstrip('\n').split() for _ in range(q)]

class SegTree():
    def __init__(self, n_):
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.tree = [float('inf') for _ in range(2 * self.n - 1)]
    def update(self, k, a):
        k += self.n - 1
        self.tree[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.tree[k] = min(self.tree[k * 2 + 1], self.tree[k * 2 + 2])
    def query(self, l, r):
        l += self.n - 1
        r += self.n - 2
        res = float('inf')
        while r-l>1:
            if l&1 == 0:
                res = min(res,self.tree[l])
            if r&1 == 1:
                res = min(res,self.tree[r])
                r -= 1
            l = l//2
            r = (r-1)//2
        if l == r:
            res = min(res,self.tree[l])
        else:
            res = min(min(res,self.tree[l]),self.tree[r])
        return res

d = { c: SegTree(n) for c in "abcdefghijklmnopqrstuvwxyz"}

for i, c in enumerate(s):
    d[c].update(i, 1)


for a, b, c in Q:
    if a == "1":
        b = int(b) - 1
        # c = c.rstrip('\n')
        d[l[b]].update(b, float('inf'))
        d[c].update(b, 1)
        l[b] = c
    else:
        res = 0
        b, c = int(b), int(c)
        for key in d:
            if d[key].query(b-1, c) == 1:
                res += 1
        print(res)
# for key in d:
#     print(key)
#     print(d[key].tree[7:])

Submission status: Time Limit Exceeded

Solution code:
import bisect
import collections

def main():
    n = int(input())

    s = list(input())

    q = int(input())

    li = [x for x in s]

    d = [[] for i in range(26)]

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


    for _ in range(q):
        a, *x = input().split()

        if a == "1":
            i = int(x[0]) - 1
            c = x[1]
            o = ord(li[i]) - 97
            on = ord(c) - 97
            index = bisect.bisect_left(d[o], i)
            d[o].pop(index)
            d[on].insert(bisect.bisect_left(d[on], i), i)
            li[i] = c
        else:
            l = int(x[0]) - 1
            r = int(x[1]) - 1
            cnt = 0
            for v in d:
                if len(v) == 0:
                    continue
                index = bisect.bisect_left(v, l)
                if index == len(v):
                    continue
                if v[index] <= r:
                    cnt += 1
            print(cnt)

main()

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())
s = input()
S = [ord(i) - 97 for i in s]
q = int(input())
HEIGHT = math.ceil(math.log(n) / math.log(2))
SIZE = 1 << HEIGHT

def build_tree_for_letter(letter):
    tree = [False for _ in range(2 << HEIGHT)]
    for i in range(1 << HEIGHT):
        tree[i + (1 << HEIGHT)] = True if i < n and s[i] == chr(97 + letter) else False

    for i in range(HEIGHT - 1, -1, -1):
        for x in range(1<<i, 2<<i):
            tree[x] = any((tree[x<<1], tree[(x<<1)+1]))

    return tree


def build():
    return [build_tree_for_letter(letter) for letter in range(26)]



def update(x, letter, positive=True):
    trees[letter][x] = (positive == True)
    while x > 1:
        x >>= 1
        trees[letter][x] = any((trees[letter][x << 1], trees[letter][(x << 1) + 1]))


def query(ll, rr):

    # print("query: ", l, r)
    total = 0
    for letter in range(26):
        l, r = ll, rr
        is_letter = False
        while l < r:
            if l%(2) != 0:
                is_letter = any((is_letter, trees[letter][l]))
                l += 1
            l >>= 1
            if r%(2) != 0:
                r -= 1
                is_letter = any((is_letter, trees[letter][r]))
            r >>= 1
        total += is_letter
    return total



trees = build()

for i in range(q):
    a, b, c = input().split()
    b = int(b) - 1
    if int(a) == 1:
        c = ord(c) - 97
        update(b + SIZE, S[b], positive=False)
        S[b] = c
        update(b + SIZE, c, positive=True)
    else:
        print(query(b + SIZE, int(c)+SIZE))

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())
s = input()
S = [ord(i) - 97 for i in s]
q = int(input())
H = math.ceil(math.log(n) / math.log(2))
LH = 1 << H

def build_tree_for_letter(letter):
    tree = [False for _ in range(2<<H)]
    for i in range(1<<H):
        tree[i + (1<<H)] = True if i < n and s[i] == chr(97 + letter) else False

    for i in range(H-1, -1, -1):
        for x in range(1<<i, 2<<i):
            tree[x] = any((tree[x<<1], tree[(x<<1)+1]))

    return tree


def build():
    trees = []
    for letter in range(26):
        trees.append(build_tree_for_letter(letter))

    return trees


def update(x, letter, positive=True):
    x += (1<<H)
    trees[letter][x] = (positive == True)
    while x > 1:
        x >>= 1
        trees[letter][x] = any((trees[letter][x << 1], trees[letter][(x << 1) + 1]))


def query(ll, rr):

    # print("query: ", l, r)
    total = 0
    for letter in range(26):
        l, r = ll + (1<<H), rr + (1<<H)
        is_letter = False
        while l < r:
            if l%(2) != 0:
                is_letter = any((is_letter, trees[letter][l]))
                l += 1
            l //= 2
            if r%(2) != 0:
                is_letter = any((is_letter, trees[letter][r-1]))
                r -= 1
            r //= 2
        total += is_letter
    return total



trees = build()

for i in range(q):
    a, b, c = input().split()
    b = int(b) - 1
    if int(a) == 1:
        c = ord(c) - 97
        update(b, S[b], positive=False)
        S[b] = c
        update(b, c, positive=True)
    else:
        c = int(c)
        print(query(b, c))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
	def __init__(self, n, *, init = None, data = None, merge = None):
		if init != None and data != None:
			raise Error("init and data cannot be specified at a time")
		if init == None and data == None:
			raise Error("one of init or data must be specified")
		self.n = n
		data_table = []
		if data:
			data_table.append((1, data))
		else:
			data_table.append((1, tuple(init(i, i + 1) for i in range(n))))
		
		w = 2
		if merge == None:
			while w <= n:
				data_table.append((w, tuple(init(i, i + w) for i in range(0, ((n - 1) // w + 1) * w, w))))
				w *= 2
		else:
			last_data = data_table[0][1]
			while w <= n:
				if len(last_data) % 2 == 0:
					new_data = tuple(merge(last_data[i * 2], last_data[i * 2 + 1]) for i in range(0, (n - 1) // w + 1))
				else:
					new_data = tuple(merge(last_data[i * 2], last_data[i * 2 + 1]) for i in range(0, (n - 1) // w)) + (merge(last_data[-1], None), )
				data_table.append((w, new_data))
				last_data = new_data
				w *= 2
		self.data_table = data_table
		
	def data_at(self, i):
		for w, data_list in self.data_table:
			yield data_list[i // w]
	
	def data_range(self, s, e = None):
		if e == None:
			e = s
			s = 0
		if s == 0:
			for w, data_list in reversed(self.data_table):
				if e % (w * 2) >= w:
					yield data_list[e // w - 1]
		elif s < e:
			for w, data_list in self.data_table:
				w2 = w * 2
				m = s % w2
				new_s = s + w2 - m
				if new_s > e:
					break
				if m != 0:
					yield data_list[s // w]
					s = new_s
			if s == e:
				return
			for w, data_list in reversed(self.data_table):
				new_s = s + w
				if new_s <= e:
					yield data_list[s // w]
					s = new_s
			
			return
			for w, data_list in self.data_table:
#				print(f"({s} - {e})")
				w2 = w * 2
				m = s % w2
				if m != 0:
					yield data_list[s // w]
					s += w2 - m
					if s == e:
						break
				m = e % w2
				if m != 0:
					yield data_list[e // w - 1]
					e -= m
					if s == e:
						break
	
	def check(self, merge):
		last_data = self.data_table[0][1]
		for w, data in self.data_table[1:]:
			if len(last_data) % 2 == 0:
				new_data = tuple(merge(last_data[i * 2], last_data[i * 2 + 1]) for i in range(0, (self.n - 1) // w + 1))
			else:
				new_data = tuple(merge(last_data[i * 2], last_data[i * 2 + 1]) for i in range(0, (self.n - 1) // w)) + (last_data[-1], )
			if new_data != data:
				print(new_data)
				print(data)
				raise "hoge"
			last_data = new_data
			w *= 2
	
	def output(self, func):
		for w, data_list in self.data_table:
#			print(f"#{w}: " + ", ".join(func(data) for data in data_list))
			pass


A = ord("a")
N = int(input())
S = list(map(lambda c: ord(c) - A, input().strip()))
Q = int(input())

def count(s, e):
	counts = [0] * 26
	for i in range(s, min(N, e)):
		counts[S[i]] += 1
	return counts

def merge(count1, count2):
	result = list(count1)
	if count2 != None:
		for i in range(26):
			result[i] += count2[i]
	return result

st = SegmentTree(N, init = count, merge = merge)
st.check(merge)

def set2str(s):
	return "".join(chr(A + j) if s[j] > 0 else "" for j in range(26))

for _ in range(Q):
	t, i, q = input().split()
	
	if t == "1":
		i = int(i) - 1
		q = ord(q) - A
		s = S[i]
		for data in st.data_at(i):
			data[s] -= 1
			data[q] += 1
		S[i] = q
		
		st.check(merge)
		
	else:
		l = int(i) - 1
		r = int(q)
		result = [0] * 26
		for data in st.data_range(l, r):
			for i in range(26):
				result[i] += data[i]
		
		count = 0
		for i in range(26):
			if result[i] > 0:
				count += 1
#		st.output(lambda data: "".join(chr(A + j) + str(data[j]) if data[j] > 0 else "" for j in range(26)))
		
		print(count)
#		print("".join(set2str(data) for data in st.data_table[0][1]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q = int(input())
query = [list(input().split()) for i in range(q)]



for i in range(q):
    count = 0
    li = []
    if int(query[i][0]) == 1:
        s[int(query[i][1])-1] = query[i][2]
    else:
        for j in range(int(query[i][1])-1,int(query[i][2])):
            if s[j] not in li:
                count += 1
                li.append(s[j])
        print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
class SegmentTree():
    def __init__(self, list):
        n = len(list)
        self.depth = math.ceil(math.log(n,2))
        num = 2**self.depth
        self.num = num
        self.seg = [0] * (num*2-1)
       
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = 2**(ord(x)-97)
        while k > 0:
            k = (k-1)//2
            self.seg[k] = self.seg[2*k+1]|self.seg[2*k+2]
    
    def query(self, l, r):
        l += self.num-1
        r += self.num-1
        res = self.seg[l]|self.seg[r]
        while r - l > 1:
            if l&1 == 1:
                res = res|self.seg[l+1]
            if r&1 == 0:
                res = res|self.seg[r-1]
            r = (r-1)//2
            l = (l-1)//2
        return bin(res).count('1')
    
N = int(input())
S = input()
s = SegmentTree(list(S))
for i in range(N):
    s.update(i, S[i])
Q = int(input())
for i in range(Q):
    q = input().split()
    if q[0] == '1':
        i = int(q[1]) - 1
        s.update(i, q[2])
    else:
        l, r = int(q[1])-1, int(q[2])-1
        print(s.query(l,r))

Submission status: Time Limit Exceeded

Solution code:
#n = int(input())
#s = input()
#n, k= map(int,input().split())
#da = list(map(int,input().split()))
class SegTree:
    def __init__(self,n):
        self.size=1
        while(n>self.size):
            self.size<<=1
        self.nod=[0 for i in range(self.size*2-1)]
    def update(self,k,a):
        k+=self.size-1
        self.nod[k]+=a
        while(k>0):
            k=(k-1)>>1
            self.nod[k]|=a
    def dedate(self, k, a):
        k += self.size-1
        self.nod[k] -= a
        while(k>0):
            k=(k-1)>>1
            self.nod[k] = self.nod[(k<<1)|1]|self.nod[(k+1)<<1]
    def query(self,a,b,k,l,r):
        if(r<=a or b<=l):
            return 0
        if(a<=l and r<=b):
            return self.nod[k]
        else:
            return self.query(a,b,(k<<1)|1,l,(l+r)>>1)|self.query(a,b,(k+1)<<1,(l+r)>>1,r)

def pop_c(x):
    ret = 0
    while x:
        ret += x&1
        x>>=1
    return ret

n = int(input())
t = input()
q = int(input())
EE = ord('a')
st = SegTree(n)
s = [t[i] for i in range(n)]

def adding(x, c):
    global st
    st.dedate(x, 1<<(ord(s[x])-EE))
    st.update(x, 1<<(ord(c)-EE))
    s[x] = c

def query(l, r):
    now = st.query(l, r+1, 0, 0, st.size)
    return pop_c(now)

for i in range(n):
    st.update(i, 1<<(ord(s[i])-EE))
ans = []
for i in range(q):
    x,l,r = map(str,input().split())
    if x=='1':
        adding(int(l)-1, r)
    else:
        ans.append(query(int(l)-1, int(r)-1))
for i in range(len(ans)):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import math
class SegmentTree():
    def __init__(self, list):
        n = len(list)
        self.depth = math.ceil(math.log(n,2))
        num = 2**self.depth
        self.num = num
        self.seg = [set()] * (num*2-1)
        for i in range(n):
            self.seg[num-1+i] = {list[i]}
        i = num-2
        while i >= 0:
            self.seg[i] = self.seg[2*i+1]|self.seg[2*i+2]
            i -= 1
    
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = {x}
        while k > 0:
            k = (k-1)//2
            self.seg[k] = self.seg[2*k+1]|self.seg[2*k+2]
    
    def query(self, l, r):
        l += self.num-1
        r += self.num-1
        res = self.seg[l]|self.seg[r]
        while r - l > 1:
            if l&1 == 1:
                res = res|self.seg[l+1]
            if r&1 == 0:
                res = res|self.seg[r-1]
            r = (r-1)//2
            l = (l-1)//2
        return res
    
N = int(input())
S = input()
s = SegmentTree(list(S))
Q = int(input())
for i in range(Q):
    q = input().split()
    if q[0] == '1':
        i = int(q[1]) - 1
        s.update(i, q[2])
    else:
        l, r = int(q[1])-1, int(q[2])-1
        print(len(s.query(l,r)))

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
s = input()
ss = [[(1 << ord(c) - ord('a')) for c in s]]
while len(ss[-1]) > 1:
    r = []
    for i in range(0, len(ss[-1]), 2):
        if i == len(ss[-1]) - 1:
            r.append(ss[-1][i])
        else:
            r.append(ss[-1][i] | ss[-1][i + 1])
    ss.append(r)
#print(ss)

def update(j, v):
    ss[0][j] = v
    for k in range(1, len(ss)):
        j = j // 2
        #print('k=', k, 'j=', j)
        if 2 * j + 1 >= len(ss[k - 1]):
            ss[k][j] = ss[k - 1][2 * j]
        else:
            ss[k][j] = ss[k - 1][2 * j] | ss[k - 1][2 * j + 1]
    #print('j=', j, 'v=', v, 'ss=', ss)

def all_or(i, j, k):
    #print('all_or(', i, j, k, ')')
    if i == j:
        return 0
    if k == 0:
        return ss[0][i]
    ik, jk = i >> k, j >> k
    if ik == jk:
        return all_or(i, j, k - 1)
    irest, jrest = i & ((1 << k) - 1), j & ((1 << k) - 1)
    r = 0
    if irest == 0:
        r = ss[k][ik]
    else:
        r = all_or(i, jk * (1 << k), k - 1)
    if jrest != 0:
        r |= all_or(jk * (1 << k), j, k - 1)
    return r

def popcount(v):
    r = 0
    while v != 0:
        v = (v & (v - 1))
        r += 1
    return r

q = int(input())

for i in range(q):
    cs = [x for x in input().split()]
    cs[0], cs[1] = int(cs[0]), int(cs[1]) - 1
    if cs[0] == 1:
        #print('cs[2]=', cs[2], 'mask=', 1 << (ord(cs[2]) - ord('a')))
        update(cs[1], (1 << (ord(cs[2]) - ord('a'))))
    else:
        #print('all_or(', cs[1], int(cs[2]), ')=',all_or(cs[1], int(cs[2]), len(ss) - 1))
        r = 0
        for j in range(cs[1], int(cs[2])):
            r |= ss[0][j]
        #print(popcount(all_or(cs[1], int(cs[2]), len(ss) - 1)))
        print(popcount(r))

Submission status: Time Limit Exceeded

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

seg = [0]*(2*N-1)

def update(k, x):
    k += N-1
    seg[k] = 2**x
    while k:
        k = (k-1)//2
        seg[k] = seg[2*k+1] | seg[2*k+2]
        
def query(p, q):
    p += N-1
    q += N-2
    res = 0
    while q-p > 1:
        if p&1 == 0:
            res = res | seg[p]
        if q&1 == 1:
            res = res | seg[q]
            q -= 1
        p //= 2
        q = (q-1)//2
    if p == q:
        res |= seg[q]
    else:
        res |= seg[p] | seg[q]
    return bin(res).count("1")

def f(s):
    return ord(s) - ord("a") + 1

for i in range(N):
    update(i, f(S[i]))
    
Q = int(input())
for _ in range(Q):
    a,b,c = map(str, input().split())
    if a == "1":
        update(int(b)-1, f(c))
    else:
        print(query(int(b)-1, int(c)))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q = int(input())
ans = []
for i in range(q):
    query = [i for i in input().split()]
    if int(query[0]) == 1:
        i_q = int(query[1])
        c_q = query[2]
        s[i_q-1] = c_q
        # s = s[:i_q-1] + c_q + s[i_q:]
    else:
        l_q = int(query[1])
        r_q = int(query[2])
        ans.append(len(set(s[l_q-1:r_q])))
for out in ans:
    print(out)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
Q = int(input())
L = list(S)
for j in range(Q):
    q = input().split()
    if q[0] == '1':
        i, c = q[1:]
        i = int(i) -1
        L[i] = c
    else:
        l, r = q[1:]
        l = int(l) - 1
        r = int(r) - 1
        print(len(set(L[l:(r+1)])))

Submission status: Time Limit Exceeded

Solution code:
def main():
  n=int(input())
  s=input()
  q=int(input())

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

main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
q=int(input())
 
for i in range(q):
  a,b,c = input().split(" ")
  if int(a) == 1:
    b = int(b)
    s = "".join([s[:b-1],c,s[b:]])
  else:
    b = int(b)
    c = int(c)
    print(len(set(list(s[b-1:c]))))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
Q = int(input())
for q in range(Q):
    t,l,r = input().split()
    if t == "1":
        S[int(l)-1] = r
        #print("".join(S))
    else:
        q2 = set(S[int(l)-1:int(r)])
        #print(q2)
        print(len(q2))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
q=int(input())
 
for i in range(q):
  a,b,c = input().split(" ")
  if int(a) == 1:
    b = int(b)
    s = s[:b-1] + c + s[b:]
  else:
    b = int(b)
    c = int(c)
    print(len(set(list(s[b-1:c]))))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
q=int(input())
#print(s)
 
for i in range(q):
  a,b,c = input().split(" ")
  if int(a) == 1:
    b = int(b)
    s = s[:b-1] + c + s[b:]
    #print(s)
  else:
    b = int(b)
    c = int(c)
    #print(list([j for j in s[b-1:c]]))
    print(len(set(list([j for j in s[b-1:c]]))))

Submission status: Time Limit Exceeded

Solution code:
class segmentTreeSum():
    initValue = 0
    dat = []
    lenTreeList = -1
    depthTreeList = 0
    lenOriginalList = -1

    def __init__(self):
        pass

    def load(self, l):
        # len(l)個よりも大きい2の二乗を得る
        self.lenOriginalList = len(l)
        self.lenTreeList = 2 ** (len(l) - 1).bit_length()  # len 5 なら 2^3 = 8
        self.depthTreeList = (len(l) - 1).bit_length()  # 木の段数(0 origin)
        self.dat = [self.initValue] * (self.lenTreeList * 2)
        # 値のロード
        for i in range(len(l)):
            self.dat[self.lenTreeList - 1 + i] = l[i]
        self.build()

    def build(self):
        for i in range(self.lenTreeList - 2, -1, -1):
            self.dat[i] = self.dat[2 * i + 1] + self.dat[2 * i + 2]

    # 若干無駄なインストラクションあるのでコードレベルでマージしたほうがいいかも
    def addValue(self, i, a):
        nodeId = (self.lenTreeList - 1) + i
        self.dat[nodeId] += a
        self.setValue(i, self.dat[nodeId])

    def setValue(self, i, a):
        """
        set a to list[i]
        """
        # print("setValue: {0}, {1}".format(i, a))
        nodeId = (self.lenTreeList - 1) + i
        # print(" first nodeId: {0}".format(nodeId))
        self.dat[nodeId] = a
        while nodeId != 0:
            nodeId = (nodeId - 1) // 2
            # print(" next nodeId: {0}".format(nodeId))
            self.dat[nodeId] = self.dat[nodeId * 2 + 1] + self.dat[nodeId * 2 + 2]

    def querySub(self, a, b, nodeId, l, r):
        """
        [a,b) 区間の親クエリに対するノードnodeへ[l, r)の探索をデリゲート
        区間については、dataの添え字は0,1,2,3,4としたときに、
        [0,3)なら0,1,2の結果を返す
        """
        # print("querySub: a={0}, b={1}, nodeId={2}, l={3}, r={4}".format(a, b, nodeId, l, r))
        if (r <= a or b <= l):
            return self.initValue
        if a <= l and r <= b:
            return self.dat[nodeId]
        resLeft = self.querySub(a, b, 2 * nodeId + 1, l, (l + r) // 2)
        resRight = self.querySub(a, b, 2 * nodeId + 2, (l + r) // 2, r)
        return resLeft + resRight

    def query(self, a, b):
        return self.querySub(a, b, 0, 0, self.lenTreeList)

    def findNthValueSub(self, x, nodeId):
        """
        [2, 3, 5, 7] = [0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0]
        とマッピングされているセグメント木においてx番目に小さい値を得るための関数
        """
        # print("call findNthValueSub x={0}, nodeId={1} nodeval={2}".format(x, nodeId, self.dat[nodeId]))
        # ここから先は葉ではないノードへの処理
        if self.dat[nodeId] < x:  # このノードが要求されているよりも小さい値しか持たないとき
            return (None, x - self.dat[nodeId])
        if nodeId >= self.lenTreeList - 1:  # nodeIfがノードのときは
            # print(" hit node: nodeId = {0} , x = {1}, retval = {2}".format(nodeId, x, nodeId - (self.lenTreeList - 1)))
            return (True, nodeId - (self.lenTreeList - 1))  # そのindex番号を返す
        # print(" call L()")
        resLeft = self.findNthValueSub(x, 2 * nodeId + 1)  # 左側の探索を行う
        if resLeft[0] != None:  # もし、値が入っているならそれを返す
            # print(" call L: hit")
            return (True, resLeft[1])
        # print(" call R()")
        resRight = self.findNthValueSub(resLeft[1], 2 * nodeId + 2)  # 右側の探索を行う
        return resRight

    def findNthValue(self, x):
        return self.findNthValueSub(x, 0)[1]

n = int(input())
s = input()
sl = list(s)
sl = list(map(lambda x: ord(x) - ord("a"), sl))
sll = []
st = []
for i in range(26):
    sll.append([0] * n)
for i in range(n):
    c = sl[i]
    sll[c][i] += 1
for i in range(26):
    elem = segmentTreeSum()
    elem.load(sll[i])
    st.append(elem)
    #print(elem.query(0, n))
# 0個目が数
#print(st[0].query(0, n)[0])
q = int(input())
for _ in range(q):
    ty, x, y = input().split()
    x = int(x)
    if ty == "1":
        cind = sl[x-1] # 今の文字
        nind = ord(y[0]) - ord("a") # 置き換えるindex
        sl[x-1] = nind
        st[cind].setValue(x-1, 0)
        st[nind].setValue(x-1, 1)
    elif ty == "2":
        x = int(x) - 1
        y = int(y)
        res = 0
        for i in range(26):
            cnt = st[i].query(x , y)
            if cnt != 0:
                res += 1
        print(res)
    else:
        print("error")