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:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']
Yn=['Yes','No']
 
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
#ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

# Binary Indexed Tree
# Bit.add(i,x)    : add x at i-th value
# Bit.sum(i)      : get sum up to i-th value
# Bit.l_bound(w)  : get lower bound of index where w can be inserted

class Bit:
    def __init__(self,n):
        self.size=n
        self.m=len(bin(self.size))-2
        self.arr=[0]*(2**self.m+1)
        
    def __str__(self):
        a=[self.sum(i+1)-self.sum(i) for i in range(self.size)]
        return str(a)
        
    def add(self,i,x):
        k=0
        while i<=self.size:
            k+=1
            self.arr[i]+=x
            i+=i&(-i)
        return
    
    def sum(self,i):
        rt=0
        while i>0:
            rt+=self.arr[i]
            i-=i&(-i)
        return rt
    
    def l_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<self.size and self.arr[x+k]<w:
                w-=self.arr[x+k]
                x+=k
            k//=2
        return x+1
        
    def u_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<self.size and self.arr[x+k]<=w:
                w-=self.arr[x+k]
                x+=k
            k//=2
        return x+1
        
class Bit0(Bit):
    def add(self,j,x):
        super().add(j+1,x)
    def l_bound(self,w):
        return max(super().l_bound(w)-1,0)
    def u_bound(self,w):
        return max(super().u_bound(w)-1,0)

class Multiset(Bit0):
    def __init__(self,max_v):
        super().__init__(max_v)
    def insert(self,x):
        super().add(x,1)
    def find(self,x):
        return super().l_bound(super().sum(x))
    def __str__(self):
        return str(self.arr)


show_flg=False
show_flg=True


n=I()
s=StoI()
q=I()

bt=[Bit0(n) for i in range(26)]


for i in range(n):
    bt[s[i]].add(i,1)

for _ in range(q):
    t,a,b=input().split()
    if t=='1':
        i,c=int(a)-1,ord(b)-97
        old=s[i]
        s[i]=c
        bt[c].add(i,1)
        bt[old].add(i,-1)
    else:
        l,r=int(a)-1,int(b)-1
        ans=0
        for i in range(26):
            if bt[i].sum(r+1)-bt[i].sum(l)>0:
                ans+=1
        print(ans)

Submission status: Accepted

Solution code:
class Binary_Indexed_Tree:
    def __init__(self, n):
        self.size = n
        self.tree = [0 for _ in range(n+1)]

    # a[i]にxを加算(1 <= i <= n) 1-indexed
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & (-i)

    # a[1] から a[t] までの合計を得る (1 <= t <= n)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)

        return s

alpha_small_dict = {chr(i):i-97 for i in range(97, 97+26)} #辞書ver
n = int(input())
S = input()
data = [[0 for i in range(n)] for j in range(26)]

bit = [Binary_Indexed_Tree(n) for i in range(26)]
for i,x in enumerate(S):
    bit[alpha_small_dict[x]].add(i+1,1)
    data[alpha_small_dict[x]][i] = 1
q = int(input())
for i in range(q):
    x,y,z = input().split()
    x,y = int(x),int(y)
    #print(x,y,z)
    if x == 1:
        num = alpha_small_dict[z]
        for j in range(26):
            if data[j][y-1] == 1:
                data[j][y-1] = 0
                bit[j].add(y,-1)
                break
        data[num][y-1] = 1
        bit[num].add(y,1)
    else:
        z = int(z)
        ans = 0
        for j in range(26):
            if bit[j].sum(z)-bit[j].sum(y-1) >= 1:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)


class SegmentTree:
    """
    引数：
        N: 処理する区間の長さ
        operator: モノイド演算 (max, min, __add__,ラムダ式,関数定義など)
        UNIT: 単位元
        a: 長さNの配列 a で初期化（a を与えない場合、単位元で初期化）
    注意: 内部的には 1-indexed
    """

    def __init__(self, N, operator, unit, a=None):
        self.op = operator
        self.UNIT = unit

        self.N0 = 2**(N-1).bit_length()
        self.tree = [self.UNIT]*(2*self.N0)
        if a != None:
            self.tree[self.N0:self.N0+N] = a[:]
            for k in range(self.N0-1, 0, -1):
                self.tree[k] = self.op(self.tree[2*k], self.tree[2*k+1])

    # a_k の値を x に更新
    def update(self, k, x):
        k += self.N0
        self.tree[k] = x
        k //= 2
        while k:
            self.tree[k] = self.op(self.tree[2*k], self.tree[2*k+1])
            k //= 2

    # 区間[l,r)をopでまとめる
    def query(self, l, r):
        L = l + self.N0
        R = r + self.N0
        s = self.UNIT
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(self.tree[R], s)
            if L & 1:
                s = self.op(s, self.tree[L])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def get(self, k):  # k番目の値を取得。query[k,k]と同じ
        return self.tree[k + self.N0]

    def all(self):
        return self.tree[1]


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


def ope(x, y):
    r = []
    if type(x) is str and type(y) is str:
        r = [x, y]
    elif type(x) is str:
        r = [x] + y
    elif type(y) is str:
        r = x + [y]
    else:
        r = x + y

    return list(set(r))


seg = SegmentTree(N, ope, '-', S)

Q = int(input())

ans = []
for _ in range(Q):
    q, a, b = input().split()

    if q == '1':
        seg.update(int(a) - 1, b)
    else:
        r = seg.query(int(a) - 1, int(b))
        ans.append(str(len(r)-1))


print("\n".join(ans))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

class SegmentTree:
    def __init__(self, a):
        # Operator
        self.op = lambda a, b : max(a, b)
        # Identity element
        self.e = 0 

        self.n = len(a)
        self.lv = (self.n - 1).bit_length()
        self.size = 2**self.lv
        self.data = [self.e] * (2*self.size - 1)
        # Bisect checking function 
        self._check = lambda x, acc : acc >= x
        self._acc = self.e

        self.initialize(a)

    # Initialize data
    def initialize(self, a):
        for i in range(self.n):
            self.data[self.size + i - 1] = a[i]
        for i in range(self.size-2, -1, -1):
            self.data[i] = self.op(self.data[i*2 + 1], self.data[i*2 + 2])

    # Update ak as x (0-indexed)
    def update(self, k, x):
        k += self.size - 1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = self.op(self.data[2*k+1], self.data[2*k+2])

    # Min value in [l, r) (0-indexed)
    def fold(self, l, r):
        L = l + self.size; R = r + self.size
        s = self.e
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s, self.data[R-1])
            if L & 1:
                s = self.op(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

    def _bisect_forward(self, x, start, k):
        # When segment-k is at the bottom, accumulate and return.
        if k >= self.size - 1:
            self._acc = self.op(self._acc, self.data[k])
            if self._check(x, self._acc):
                return k - (self.size - 1)
            else:
                return -1
        width = 2**(self.lv - (k+1).bit_length() + 1)
        mid = (k+1) * width + width // 2 - self.size 
        # When left-child isn't in range, just look at right-child. 
        if mid <= start:
            return self._bisect_forward(x, start, 2*k + 2)
        # When segment-k is in range and has no answer in it, accumulate and return -1
        tmp_acc = self.op(self._acc, self.data[k])
        if start <= mid - width // 2 and not self._check(x, tmp_acc):
            self._acc = tmp_acc
            return -1
        # Check left-child then right-child
        vl = self._bisect_forward(x, start, 2*k + 1)
        if vl != -1:
            return vl
        return self._bisect_forward(x, start, 2*k + 2)
    
    # Returns min index s.t. start <= index and satisfy check(data[start:idx)) = True
    def bisect_forward(self, x, start=None):
        if start:
            ret = self._bisect_forward(x, start, 0)
        else:
            ret = self._bisect_forward(x, 0, 0)
        self._acc = self.e
        return ret

    def _bisect_backward(self, x, start, k):
        # When segment-k is at the bottom, accumulate and return.
        if k >= self.size - 1:
            self._acc = self.op(self._acc, self.data[k])
            if self._check(x, self._acc):
                return k - (self.size - 1)
            else:
                return -1
        width = 2**(self.lv - (k+1).bit_length() + 1)
        mid = (k+1) * width + width // 2 - self.size 
        # When right-child isn't in range, just look at right-child. 
        if mid >= start:
            return self._bisect_backward(x, start, 2*k + 1)
        # When segment-k is in range and has no answer in it, accumulate and return -1
        tmp_acc = self.op(self._acc, self.data[k])
        if start > mid + width // 2 and not self._check(x, tmp_acc):
            self._acc = tmp_acc
            return -1
        # Check right-child then left-child
        vl = self._bisect_backward(x, start, 2*k + 2)
        if vl != -1:
            return vl
        return self._bisect_backward(x, start, 2*k + 1)
    
    # Returns max index s.t. index < start and satisfy check(data[idx:start)) = True
    def bisect_backward(self, x, start=None):
        if start:
            ret = self._bisect_backward(x, start, 0)
        else:
            ret = self._bisect_backward(x, self.n, 0)
        self._acc = self.e
        return ret

n = int(input())
s = input().rstrip()
bit_array = [[0] * n for _ in range(26)]
orda = ord("a")
for i, ch in enumerate(s):
    bit_array[ord(ch) - orda][i] = 1

sts = []
for i in range(26):
    sts.append(SegmentTree(bit_array[i]))

q = int(input())
for _ in range(q):
    q1, q2, q3 = [item for item in input().split()]
    if q1 == "1":
        iq = int(q2) - 1
        cq = q3
        for index in range(26):
            sts[index].update(iq, 0)
        sts[ord(cq) - orda].update(iq, 1)
    else:
        lq = int(q2) - 1
        rq = int(q3) 
        ret = 0
        for index in range(26):
            if sts[index].fold(lq, rq) != 0:
                ret += 1
        print(ret)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
sl = list(input())
q = int(input())


# Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
        self.el = [0] * (n + 1)

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

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

    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


dic = defaultdict(lambda: BIT(n))
ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
for idx, s in enumerate(sl):
    dic[s].add(idx+1, 1)
for _ in range(q):
    a, b, c = map(str, input().split())
    if a == "1":
        b = int(b)
        dic[sl[b-1]].add(b, -1)
        dic[c].add(b, 1)
        sl[b-1] = c
    else:
        b = int(b)
        c = int(c)
        ans = 0
        for s in ascii_lowercase:
            if dic[s].get(b-1, c) > 0:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
class SegmentTree:
	def __init__(self, orig, func, unit):
		_len = len(orig)
		self.func = func
		self.size = 1 << (_len - 1).bit_length()
		self.tree = [unit] * self.size + orig + [unit] * (self.size - _len)
		self.unit = unit

		for i in range(self.size - 1, 0, -1):
			self.tree[i] = func(self.tree[i * 2], self.tree[i * 2 + 1])

	def update(self, i, v):
		i += self.size
		self.tree[i] = v
		while i:
			i //= 2
			self.tree[i] = self.func(self.tree[i * 2], self.tree[i * 2 + 1])

	def find(self, l, r):
		l += self.size
		r += self.size
		ret = self.unit
		while l < r:
			if l & 1:
				ret = self.func(ret, self.tree[l])
				l += 1
			if r & 1:
				r -= 1
				ret = self.func(ret, self.tree[r])
			l //= 2
			r //= 2
		return ret

import sys
input = sys.stdin.readline
from operator import or_

def main():
	input()
	seg = SegmentTree([1 << ord(x) - 97 for x in input()[:-1]], or_, 0)
	ans = []
	for _ in range(int(input())):
		f, x, y = input().split()
		if f == "1":
			seg.update(int(x) - 1, 1 << ord(y) - 97)
		else:
			ans.append(bin(seg.find(int(x) - 1, int(y))).count("1"))
	print(*ans)

if __name__=="__main__":
	main()

Submission status: Accepted

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

L = 20
M = [1<<i for i in range(L)]
T = [[0]*m for m in M]

o = ord('a')

for i, c in enumerate(S):
    T[-1][i] = 1<<(ord(c)-o)

for l in range(L-2, -1, -1):
    for i in range(M[l]):
        T[l][i] = T[l+1][i*2] | T[l+1][i*2+1]
    
def q(layer, n, l, r):
    length_block = (1<<(L-1))//M[layer]
    ml = length_block*n
    mr = ml + length_block

    if l==ml and r==mr:
        return T[layer][n]
    
    center = ml + length_block//2

    ret = 0
    if l<center: ret |= q(layer+1, n*2  , l, min(r,center))
    if r>center: ret |= q(layer+1, n*2+1, max(l,center), r)

    return ret

Q = int(input())
for _ in range(Q):
    t, a1, a2 = input().split()
    if t=='1':
        i = int(a1)-1
        c = a2
        T[-1][i] = 1<<(ord(c)-o)
        for l in range(L-2, -1, -1):
            i = i//2
            T[l][i] = T[l+1][i*2] | T[l+1][i*2+1]
        
    else:
        l = int(a1)-1
        r = int(a2)
        x = q(0, 0, l, r)
        ans = 0
        for i in range(26):
            if (x>>i)&1: ans+=1
        print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
q=int(input())
def segfunc(x,y):
    return x|y
def init(init_val,var):
    #set_val
    for i in range(n):
        seg[var][i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[var][i]=segfunc(seg[var][2*i+1],seg[var][2*i+2]) 
    
def update(k,x,var):
    k += num-1
    seg[var][k] = x
    while k:
        k = (k-1)//2
        seg[var][k] = segfunc(seg[var][k*2+1],seg[var][k*2+2])
    
def query(p,q,var):
    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[var][p])
        if q&1 == 1:
            res = segfunc(res,seg[var][q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[var][p])
    else:
        res = segfunc(segfunc(res,seg[var][p]),seg[var][q])
    return res

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[[ide_ele]*2*num for i in range(26)]
for i in range(n):
    update(i,1,ord(s[i])-97)
for i in range(q):
    a,b,c=input().split()
    if a=="1":
        update(int(b)-1,0,ord(s[int(b)-1])-97)
        s[int(b)-1]=c
        update(int(b)-1,1,ord(c)-97)
    else:
        ans=0
        for j in range(26):
            ans+=query(int(b)-1,int(c),j)
        print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
kijun = ord("a")
n = int(readline())
s = readline().rstrip().decode('utf-8')
q = int(readline())
lst1 = [0]*n

def pow(n,p): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2
            p //= 2
        else:
            res = res * n
            p -= 1
    return res

for i in range(n):
    lst1[i] = pow(2,(ord(s[i])-kijun))
#####segfunc######
def segfunc(x,y):
    return x|y

def init(init_val): #渡されたリストでsegを初期化
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x): #segの要素kをxに変更(セグ木全体の更新)
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q): #区間[p,q)での、segfuncに準じた値を返す
    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

#####単位元######
"""
最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
　　和のセグ木 → 0　(上の単位元の説明を参照)
　　積のセグ木 → 1　(上の単位元の説明を参照)
　　gcdのセグ木 → 0　(gcdを更新しない値は0)
"""
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num #単位元の配列(計算結果に影響を及ぼさない配列)を作成

init(lst1)

def judge(u):
    res = 0
    for i in range(27):
        if u>>i & 1:
            res += 1
    return res

for i in range(q):
    t,x,y = readline().rstrip().decode('utf-8').split()
    if t == "1":
        update(int(x)-1,pow(2,ord(y)-kijun))
    else:
        print(judge(query(int(x)-1,int(y))))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        #for i,l in enumerate(L):
        #    self.add(i,l)
        self.N0 = 1
        while self.N0*2 <= self.N:
            self.N0 *= 2

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret

    #you can use this function when the BIT has only non-negative values.
    def lower_bound(self, w):
        if w<=0:
            return 0
        x = 0
        k = self.N0
        while k>0:
            if x+k<=self.N:
                if self.bit[x+k-1]<w:
                    w-=self.bit[x+k-1]
                    x+=k
            k//=2
        return x+1


def main():
    #da=BIT([1,2,3])
    #print(da.bit)
    #print(da.sum(0))
    N = int(input())

    B = [BIT([0]*N) for i in range(26)]

    S = list(input())

    for i in range(N):
        B[ord(S[i]) - ord("a")].add(i, 1)

    Q = int(input())

    for i in range(Q):
        a,b,c = input().split()
        if a=="1":
            #print(B[0].bit)
            index = int(b)-1
            c = c
            if not S[index]==c:
                old = ord(S[index]) - ord("a")
                num = ord(c) - ord("a")
                B[num].add(index, 1)
                B[old].add(index, -1)
                S[index] = c
        else:
            #print(B[0].bit)
            #print(B[0].sum(1))
            l = int(b)-1
            r = int(c)-1
            ans = 0
            for j in range(26):
                if l==0:
                    if B[j].sum(r)>0:
                        ans+=1
                else:
                    if B[j].sum(r)-B[j].sum(l-1)>0:
                        ans+=1

            print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class SegmentTree():
    def __init__(self,size,unit,f):
        self.size=size
        self.data=[unit for _ in range(2*size)]
        self.unit=unit
        self.f=f
    def update(self,i,x):
        c=self.data
        f=self.f
        i+=self.size
        c[i]=x
        while i>1:
            i//=2
            c[i]=f(c[i*2],c[i*2+1])
    def add(self,i,x):
        c=self.data
        f=self.f
        i+=self.size
        c[i]=f(c[i],x)
        while i>1:
            i//=2
            c[i]=f(c[i*2],c[i*2+1])
    def query(self,l,r):
        c=self.data
        f=self.f
        x=self.unit
        y=self.unit
        l+=self.size
        r+=self.size
        while l<r:
            if l%2:
                x=f(x,c[l])
                l+=1
            if r%2:
                r-=1
                y=f(c[r],y)
            l//=2
            r//=2
        return f(x,y)
def main():
    N = int( input())
    S = list( input())
    Q = int( input())
    Query = [ tuple( input().split()) for _ in range(Q)]
    for i in range(40):
        if N < pow(2,i):
            n = pow(2,i)
            break
    A = [SegmentTree(n, 0, lambda a,b : a+b) for _ in range(26)]
    a = ord('a')
    for i in range(N):
        A[ord(S[i]) - a].update(i, 1)
    ANS = []
    for t, i, c in Query:
        if t == '1':
            i = int(i)
            A[ord(S[i-1])-a].update(i-1, 0)
            A[ord(c)-a].update(i-1,1)
            S[i-1] = c
        else:
            i, c = int(i), int(c)
            ans = 0
            for j in range(26):
                if A[j].query(i-1, c) > 0:
                    ans += 1
            ANS.append(ans)
    print('\n'.join( map(str, ANS)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left

n = int(input())
s = list(input())
q = int(input())
query = [input() for _ in range(q)]

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

for i, x in enumerate(s):
    p[ord(x) - ord('a')].append(i)

for x in query:
    a, b, c = x.split()
    #print(c)
    if a == '1':
        b = int(b) - 1
        if s[b] == c:
            continue
        d = ord(s[b]) - ord('a')
        e = ord(c) - ord('a')
        temp = bisect_left(p[d], b)
        p[d].pop(temp)
        temp = bisect_left(p[e], b)
        p[e].insert(temp, b)
        s[b] = c
    else:
        b = int(b) - 1
        c = int(c) - 1
        #print(b, c)
        ans = 0
        for i in range(26):
            L = bisect_left(p[i], b)
            if L >= len(p[i]):
                continue
            if p[i][L] <= c:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
al=list('abcdefghijklmnopqrstuvwxyz')
#####segfunc######                                                              
def segfunc(x,y):
    return x|y

def init(init_val):
    #set_val                                                                    
    for i in range(n):
        seg[i+num-1]=1<<al.index(init_val[i])
    #built                                                                      
    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]=x
    while k+1:
        k=(k-1)//2
        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])
    ans=0
    while res>0:
        if res%2==1:
            ans+=1
        res=res//2
    return ans

ide_ele=0
n=int(input())
num=2**(n-1).bit_length()
seg=[ide_ele]*2*num
a=list(input())
init(a)
ans=0
q=int(input())

for i in range(q):
    p=list(map(str,input().split()))
    if p[0]=='1':
        update(int(p[1])-1,1<<al.index(p[2]))
    else:
        print(query(int(p[1])-1,int(p[2])))
#for i in range(n):
    #ans=max(gcd(query(0,i),query(i+1,n)),ans)
#print(ans)

Submission status: Accepted

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

sys.setrecursionlimit(300000)



def update(i, val, n, bi_tree, sign=1):
    i += 1
    while i < n:
        bi_tree[i][val] += (1 * sign)
        i += i & -i


def get_sum(i, bi_tree):
    ans = [0] * 26
    while i > 0:
        tmp = bi_tree[i]
        for j in range(26):
            ans[j] += tmp[j]
        i -= i & -i
    return ans


def get_range_sum(left, right, bi_tree):
    r_sum = get_sum(right, bi_tree)
    l_sum = get_sum(left - 1, bi_tree)
    for i in range(26):
        r_sum[i] -= l_sum[i]
    return r_sum


from pprint import pprint

def solve(N, S, Q, queries):
    #arr.insert(0, 0)   # insert dummy node for 1-based indexing
    #bit = [0 for i in range(n+1)]
    bit = [[0] * 26 for i in range(N + 1)]
    s = []
    for i, c in enumerate(S):
        if 'a' <= c <= 'z':
            update(i, ord(c) - ord('a'), N + 1, bit)
        s.append(c)

    for q in queries:
        if q[0] == '1':
            i, c = int(q[1]) - 1, q[2]
            p = s[i]
            update(i, ord(p) - ord('a'), N + 1, bit, -1)
            update(i, ord(c) - ord('a'), N + 1, bit, 1)
            s[i] = c
        if q[0] == '2':
            l, r = int(q[1]), int(q[2])
            counts = get_range_sum(l, r, bit)
            ret = 0
            for x in counts:
                if x > 0:
                    ret += 1
            print(ret)
        #pprint(get_range_sum(1, 5, bit))
        #print(s)
        #print()

    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

#seg_tree
def init(n, s):
    num = len(str(bin(n-1))) -2
    seg = [0] * (2**(num+1))
    seg_num = 2**num

    for i in range(n):
        tmp = ord(s[i]) - 97
        seg[i + seg_num] = 1 << tmp

    for i in range(seg_num-1, 0, -1):
        seg[i] = seg[i*2] | seg[i*2+1]

    return seg, seg_num

def calc_sum(head, tail):
    head += seg_num
    tail += seg_num
    l = []
    while(head <= tail):
        if(head == tail):
            l.append(head)
            break

        if(head % 2 == 1):
            l.append(head)
            head += 1
        head = head //2

        if(tail % 2 == 0):
            l.append(tail)
            tail -= 1
        tail = tail //2

    ans = 0
    for i in l:
        ans = ans | seg[i]
    ans = str(bin(ans)).count('1')
    return(ans)

def update(i,s):
    i += seg_num
    tmp = ord(s) - 97
    seg[i] = 1 << tmp
    while(i > 1):
        i = i//2
        seg[i] = seg[2*i] | seg[2*i+1]

seg,seg_num = init(n,s)

for i in range(q):
    q1,q2,q3 = input().split()
    if(q1 =='1'):
        update(int(q2)-1, q3)
    else:
        q2,q3 = int(q2),int(q3)
        print(calc_sum(q2-1, q3-1))

Submission status: Accepted

Solution code:
n=int(input())
ss=input()
dps=['a']*n
from collections import defaultdict
d=defaultdict(list)
for i in range(n):
    d[ss[i]].append(i)
    dps[i]=ss[i]
sorted(d.items())

Q=int(input())
import bisect
for i in range(Q):
    num,ii,c=input().split()
    #print(d)
    if num=='1':
        if c==dps[int(ii)-1]:
            continue
        bisect.insort_left(d[c],int(ii)-1)
        d[dps[int(ii)-1]].remove(int(ii)-1)
        dps[int(ii)-1]=c
    else:
        l,r=int(ii)-1,int(c)-1
        count=0
        for k,lst in d.items():
            idx=bisect.bisect_left(lst,l)
            idx1=bisect.bisect_right(lst,r)
            count+=((idx1-idx)>0)
            #print(lst,l,r,count)
        print(count)
        pass