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: Accepted

Solution code:
abc=list("abcdefghijklmnopqrstuvwxyz")

class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    def update(self, k: int, x):
        k += self.N0 - 1
        ############################
        self.data[k] = x
        ###########################
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        ##########################
        a, b = [], []
        while L < R:
            if L & 1:
                a.append(L - 1)
                L += 1
            if R & 1:
                R -= 1
                b.append(R - 1)
            L >>= 1
            R >>= 1
        for i in a + b[::-1]:
            res = self.segfunc(res, self.data[i])
        ##########################
        return res



idx={}
for i in range(len(abc)):
    idx[abc[i]]=i
#print(idx)
N=int(input())
S=list(input())
Q=int(input())
L=[[0]*(N+1) for _ in range(26)]

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


for i in range(N):
    s=S[i]
    L[idx[s]][i+1]=1
    

segdict={}
for i in range(26):
    segdict[i]=SegmentTree(L[i],add,0)

for i in range(Q):
    query=input().split()
    num=int(query[0])

    if num==1:
        i=int(query[1])
        c=query[2]
        nows=S[i-1]
        segdict[idx[nows]].update(i,0)
        segdict[idx[c]].update(i,1)
        S[i-1]=c
    else:
        l=int(query[1])
        r=int(query[2])
        sub=0
        for j in range(26):
            x=segdict[j].query(l,r+1)
            if x>0:
                sub+=1
        print(sub)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial, gcd
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
import sys  # def input(): return sys.stdin.readline().rstrip() # sys.setrecursionlimit(10**6)

class SegTree:  # 0-index !!!
    """
    fx: モノイドXでの二項演算
    ex: モノイドXでの単位元
    init(seq, fx, ex): 配列seqで初期化 O(N)
    update(i, x): i番目の値をxに更新 O(logN)
    query(l, r): 区間[l,r)をfxしたものを返す O(logN)
    get(i): i番目の値を返す
    show(): 配列を返す
    """

    def __init__(self, seq, fx, ex):
        self.n = len(seq)
        self.fx = fx
        self.ex = ex
        self.size = 1<<(self.n - 1).bit_length()
        self.tree = [ex] * (self.size * 2)
        # build
        for i, x in enumerate(seq, start=self.size):
            self.tree[i] = x
        for i in reversed(range(1, self.size)):
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, i, x):  # O(log(n))
        i += self.size
        self.tree[i] = x
        while i:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

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

    def query(self, l, r):  # l = r の場合はたぶんバグるので注意
        tmp_l = self.ex
        tmp_r = self.ex
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                tmp_l = self.fx(tmp_l, self.tree[l])
                l += 1
            if r & 1:
                tmp_r = self.fx(self.tree[r - 1], tmp_r)  # 交換法則を仮定しない(順序大事に)
            l >>= 1
            r >>= 1
        return self.fx(tmp_l, tmp_r)

    def get(self, i):
        return self.tree[self.size + i]

    def show(self):
        return self.tree[self.size: self.size + self.n]

# ---------------------- #

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

n = int(input())
s = input()
q = int(input())
queries = [input().split() for _ in range(q)]

A = [set(x) for x in s]
seg = SegTree(A, fx=func, ex=set())

for t, *arg in queries:
    if t == "1":
        i, c = arg
        i = int(i) - 1
        seg.update(i, set(c))
    else:
        l, r = (int(x) - 1 for x in arg)
        ans = seg.query(l, r + 1)
        print(len(ans))

Submission status: Accepted

Solution code:
class SegT():
    def __init__(self, size, origin):
        self.size = 1
        while self.size < size: self.size *= 2
        self.data = [set() for _ in range(self.size * 2 - 1)]
        for i in range(size):
            self.data[i+self.size-1] = origin[i]
        for i in range(self.size-2,-1,-1):
            self.data[i] = self.data[i*2+1] | self.data[i*2+2]

    
    def update(self, i, x):
        i += (self.size - 1)
        self.data[i] = {x}
        while i > 0:
            i = (i - 1) // 2
            self.data[i] = self.data[i*2+1] | self.data[i*2+2]
        
    def get(self, a, b, node=0, l=0, r=-1):
        if r < 0: r = self.size
        if r <= a or b <= l: return set()
        if a <= l and r <= b: return self.data[node]
        vl = self.get(a, b, node*2+1, l, (l+r)//2)
        vr = self.get(a, b, node*2+2, (l+r)//2, r)
        return vl | vr

N = int(input())
S = input()
Q = int(input())
origin = [{i} for i in S]

segt = SegT(N, origin)

for i in range(Q):
    t, l, r = input().split()
    if t == "1":
        segt.update(int(l)-1, r)
    else:
        x = segt.get(int(l)-1,int(r))
        print(len(x))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

#####segfunc#####
def segfunc(x, y):
    return x * y
#################

#####ide_ele#####
ide_ele = 1
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

N = getN()
s = input()
Q = getN()
query = [input().split() for i in range(Q)]

S = []
for i in s:
    # 面倒なので文字を数値化
	S.append(ord(i) - ord("a"))

seg = [SegTree([1] * N, segfunc, ide_ele) for _ in range(26)]

# 入力
for i in range(N):
	seg[S[i]].update(i, 0)

for i in range(Q):
	a, b, c = query[i]
	if int(a) == 1:
        # 何番目
		b = int(b) - 1
        # もともと１番目にあったものを1（消滅）させる
		seg[S[b]].update(b, 1)
		t = ord(c) - ord("a")
		seg[t].update(b, 0)
		S[b] = t

	else:
		b = int(b) - 1
		c = int(c)
		cnt = 0
		for se in seg:
            # 1 * 1 * 0 * 1 *...
            # 区間内に一つでも0があれば0
			if se.query(b, c) == 0:
				cnt += 1
		print(cnt)

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


def LI(): return list(map(int,input().split()))


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))

# rstrip().decode('utf-8')

#####segfunc#####
def segfunc(x, y):
    return x*y
#################

#####ide_ele#####
ide_ele = 1
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def main():
	n=II()
	s=input().rstrip().decode()
	S=[]
	for i in s:
		S.append(ord(i)-ord("a"))
	
	seg=[SegTree([1]*n,segfunc,ide_ele) for _ in range(26)]
	
	#print(S)
	#print(seg)
	for i in range(n):
		seg[S[i]].update(i,0)
	
	q=II()
	for _ in range(q):
		a,b,c=input().split()
		if int(a)==1:
			b=int(b)-1
			seg[S[b]].update(b,1)
			t=ord(c)-ord("a")
			seg[t].update(b,0)
			S[b]=t
		
		else:
			#print(S)
			b=int(b)-1
			c=int(c)
			cnt=0
			for se in seg:
				if se.query(b,c)==0:
					cnt+=1
			print(cnt)
			
	
	

if __name__=="__main__":
	main()

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


def LI(): return list(map(int,input().split()))


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))

# rstrip().decode('utf-8')

#####segfunc#####
def segfunc(x, y):
    return x*y
#################

#####ide_ele#####
ide_ele = 1
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def main():
	n=II()
	s=input()
	S=[]
	for i in s:
		S.append(ord(i)-ord("a"))
	
	seg=[SegTree([1]*n,segfunc,ide_ele) for _ in range(26)]
	
	#print(S)
	#print(seg)
	for i in range(n):
		seg[S[i]].update(i,0)
	
	q=II()
	for _ in range(q):
		a,b,c=input().split()
		if int(a)==1:
			b=int(b)-1
			seg[S[b]].update(b,1)
			t=ord(c)-ord("a")
			seg[t].update(b,0)
			S[b]=t
		
		else:
			#print(S)
			b=int(b)-1
			c=int(c)
			cnt=0
			for se in seg:
				if se.query(b,c)==0:
					cnt+=1
			print(cnt)
			
	
	

if __name__=="__main__":
	main()

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


def LI(): return list(map(int,input().split()))


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))

# rstrip().decode('utf-8')

#####segfunc#####
def segfunc(x, y):
    return x*y
#################

#####ide_ele#####
ide_ele = 1
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def main():
	n=II()
	s=input()
	S=[]
	for i in s:
		S.append(ord(i)-ord("a"))
	
	seg=[SegTree([1]*n,segfunc,ide_ele) for _ in range(26)]
	
	#print(S)
	#print(seg)
	for i in range(n):
		seg[S[i]].update(i,0)
	
	q=II()
	for _ in range(q):
		a,b,c=input().split()
		if int(a)==1:
			b=int(b)
			seg[S[b-1]].update(b-1,1)
			t=ord(c)-ord("a")
			seg[t].update(b-1,0)
			S[b-1]=t
		
		else:
			#print(S)
			b=int(b)
			c=int(c)
			cnt=0
			for se in seg:
				if se.query(b-1,c)==0:
					cnt+=1
			print(cnt)
			
	
	

if __name__=="__main__":
	main()

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


def LI(): return list(map(int,input().split()))


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))

# rstrip().decode('utf-8')

#####segfunc#####
def segfunc(x, y):
    return x*y
#################

#####ide_ele#####
ide_ele = 1
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def main():
	n=II()
	s=input()
	S=[]
	for i in s:
		S.append(ord(i)-ord("a"))
	
	seg=[SegTree([1]*n,segfunc,ide_ele) for _ in range(26)]
	
	#print(S)
	#print(seg)
	for i in range(n):
		seg[S[i]].update(i,0)
	
	q=II()
	for _ in range(q):
		a,b,c=input().split()
		if int(a)==1:
			b=int(b)
			seg[S[b-1]].update(b-1,1)
			seg[ord(c)-ord("a")].update(b-1,0)
			S[b-1]=ord(c)-ord("a")
		
		else:
			#print(S)
			b=int(b)
			c=int(c)
			cnt=0
			for se in seg:
				if se.query(b-1,c)==0:
					cnt+=1
			print(cnt)
			
	
	

if __name__=="__main__":
	main()

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


def LI(): return list(map(int,input().split()))


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))

# rstrip().decode('utf-8')

class BinaryIndexedTree:
	def __init__(self,n,default=0):
		self.s=[default]*(n+1)
		self.n=n
	
	def add(self,val,idx):
		while idx<self.n+1:
			self.s[idx]=self.s[idx]+val
			idx+=idx&(-idx)
		return
	
	def get(self,idx):
		res=0
		while idx>0:
			res=res+self.s[idx]
			idx-=idx&(-idx)
		return res

from collections import defaultdict

def main():
	n=II()
	s=input()
	S=[0]+list(s)
	
	d=defaultdict(lambda:BinaryIndexedTree(n))
	
	for i,si in enumerate(s):
		#print(i,si)
		d[si].add(1,i+1)
	
	q=II()
	for _ in range(q):
		f,a,b=input().split()
		if int(f)==1:
			a=int(a)
			d[S[a]].add(-1,a)
			d[b].add(1,a)
			S[a]=b
		else:
			#print(S,a,b)
			a=int(a)
			b=int(b)
			cnt=0
			for bit in d.values():
				if bit.get(b)-bit.get(a-1)>0:
					cnt+=1
			print(cnt)
		
	

if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
N=int(input())
S=input()
slst=[s for s in S]
Q=int(input())

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
 
bits=[Bit(N) for _ in range(26)]

for i in range(N):
    ch=ord(S[i])-ord('a')
    bits[ch].add(i+1,1)

for _ in range(Q):
    t,a,b=input().split()

    if t=='1':
        a=int(a)
        pos=a-1
        nextc=ord(b)-ord('a')
        beforec=ord(slst[pos])-ord('a')

        if nextc!=beforec:
            bits[beforec].add(a,-1)
            bits[nextc].add(a,1)
            slst[pos]=b
            
    else:
        l=int(a)
        r=int(b)

        cnt=[0]*26

        for i in range(26):
            cnt[i]+=bits[i].sum(r)
        
        if l-1>0:
            for i in range(26):
                cnt[i]-=bits[i].sum(l-1)
        
        ans=0

        for i in range(26):
            if cnt[i]>0:
                ans+=1
        
        print(ans)

Submission status: Accepted

Solution code:
# Segment tree (Bitwise Or)
from operator import or_


class SegmentTree:
    _f = None
    _data = None
    _offset = None
    _size = None

    def __init__(self, size, f):
        self._f = f
        self._size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

    def build(self, iterable):
        f = self._f
        data = self._data
        data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            data[i] = f(data[i * 2 + 1], data[i * 2 + 2])

    def update(self, index, value):
        f = self._f
        data = self._data
        i = self._offset + index
        data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            data[i] = f(data[i * 2 + 1], data[i * 2 + 2])

    def query(self, start, stop):
        def iter_segments(data, l, r):
            while l < r:
                if l & 1 == 0:
                    yield data[l]
                if r & 1 == 0:
                    yield data[r - 1]
                l = l // 2
                r = (r - 1) // 2
        f = self._f
        it = iter_segments(self._data, start + self._offset,
                           stop + self._offset)
        result = next(it)
        for e in it:
            result = f(result, e)
        return result


def conv(c):
    return 1 << (ord(c) - ord('a'))


N = int(input())
S = input()

st = SegmentTree(N, or_)
st.build(conv(c) for c in S)

Q = int(input())
for _ in range(Q):
    q = input().split()
    if q[0] == '1':
        i, c = q[1:]
        i = int(i) - 1
        st.update(i, conv(c))
    elif q[0] == '2':
        l, r = map(int, q[1:])
        print(bin(st.query(l - 1, r)).count('1'))

Submission status: Accepted

Solution code:
N = int(input())
S = ["*"]*(N+1)
S[1:] = list(input())
Q = int(input())
q1,q2,q3 = [0]*Q,[0]*Q,[0]*Q
for i in range(Q):
    tmp = input().split()
    q1[i],q2[i] = map(int,tmp[:2])
    if q1[i] == 2:
        q3[i] = int(tmp[2])
    else:
        q3[i] = tmp[2]

class BIT:
    def __init__(self, n, init_list):
        self.num = n + 1
        self.tree = [0] * self.num
        for i, e in enumerate(init_list):
            self.update(i, e)

    #a_kにxを加算
    def update(self, k, x):
        k = k + 1
        while k < self.num:
            self.tree[k] += x
            k += (k & (-k))
        return

    def query1(self, r):
        ret = 0
        while r > 0:
            ret += self.tree[r]
            r -= r & (-r)
        return ret

    #通常のスライスと同じ。lは含み、rは含まない
    def query2(self, l, r):
        return self.query1(r) - self.query1(l)

s_pos = [BIT(N+1,[0]*(N+1)) for _ in range(26)]

for i in range(1,N+1):
    s_pos[ord(S[i]) - ord("a")].update(i,1)

alphabets = [chr(ord("a") + i) for i in range(26)]

for i in range(Q):
    if q1[i] == 1:
        s_pos[ord(S[q2[i]]) - ord("a")].update(q2[i],-1)
        S[q2[i]] = q3[i]
        s_pos[ord(q3[i]) - ord("a")].update(q2[i],1)
    else:
        ans = 0
        for c in alphabets:
            if s_pos[ord(c) - ord("a")].query2(q2[i],q3[i]+1) > 0:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



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

### BIT 
def init(bit, values):
    for i,v in enumerate(values):
        update(bit,i,v)
#a1 ~ aiまでの和 O(logn)
def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res

#ai += x(logN)
def update(bit,i,x):
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return

l = [chr(v) for v in range(ord("a"), ord("z")+1)]
d = {c: [0] * (n+1) for c in l}
for i,c in enumerate(s):
    update(d[c], i+1, 1)
s = list(s)
ans = []
for i in range(q):
    v,i,c = input().split()
    if v=="1":
        i = int(i)-1
        if d[s[i]][i+1]>=1:
            update(d[s[i]], i+1, -1)
        update(d[c], i+1, 1)
        s[i] = c
    else:
        ll,rr = int(i),int(c)
        val = sum(query(d[c], rr) - query(d[c], ll-1) >= 1 for c in l)
        ans.append(val)
write("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

seg_unit = 0


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


def build(seg, raw_data):
    N = len(seg) // 2
    seg[N:] = raw_data
    for i in range(N - 1, 0, -1):
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])


def set_val(seg, i, x):
    N = len(seg) // 2
    i += N
    seg[i] = x
    while i > 1:
        i >>= 1
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])


def fold(seg, l, r):
    vl = vr = 0
    N = len(seg) // 2
    l, r = l + N, r + N
    while l < r:
        if l & 1:
            vl = seg_f(vl, seg[l])
            l += 1
        if r & 1:
            r -= 1
            vr = seg_f(seg[r], vr)
        l, r = l >> 1, r >> 1
    return seg_f(vl, vr)

def main(N, S, query):
    seg = np.zeros(N + N, np.int64)
    build(seg, 1 << S)
    for q in query:
        t, a, b = q.split()
        if t == b'1':
            a, b = int(a) - 1, ord(b) - ord('a')
            set_val(seg, a, 1 << b)
        else:
            a, b = int(a) - 1, int(b)
            x = fold(seg, a, b)
            print(bin(x).count('1'))

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.int64
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    seg_f = cc_export(seg_f, (i8, i8))
    build = cc_export(build, (i8[:], i8[:]))
    set_val = cc_export(set_val, (i8[:], i8, i8))
    fold = cc_export(fold, (i8[:], i8, i8))
    cc.compile()

from my_module import seg_f, build, set_val, fold

N = int(readline())
S = np.array(list(readline().rstrip()), np.int64) - ord('a')
query = readlines()[1:]

main(N, S, query)