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:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

class Segment_Tree:
    __slots__ = ['ide_ele', 'size', 'num', 'seg', 'segfunc']

    def __init__(self, size, func, element):
        #####単位元######
        self.ide_ele = element
        self.size = size

        #num:n以上の最小の2のべき乗
        self.num = 2 ** (self.size - 1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num

        #####segfunc######
        self.segfunc = func

    def apply(self, apply_seq):
        #set_val
        for i in range(self.size):
            self.seg[i + self.num - 1] = apply_seq[i]    
        #built
        for i in range(self.num - 2, -1, -1) :
            self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
        
    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            k = (k-1) // 2
            self.seg[k] = self.segfunc(self.seg[k * 2 + 1],  self.seg[k * 2 + 2])
        
    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q & 1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2 
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res


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

n = int(input())
st = Segment_Tree(n,segor,0)
S = input()
data = [0] * n
for i,si in enumerate(S):
  k = ord(si)-ord("a")
  data[i] = 1 << k
st.apply(data)
Q = int(input())
for _ in range(Q):
  typo,a,b = input().split()
  if typo == "1":
    st.update(int(a)-1,1 << (ord(b)-ord("a")))
  if typo == "2":
    print(bin((st.query(int(a)-1,int(b))))[2:].count("1"))

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
q=int(input())
c=[chr(i) for i in range(97, 97+26)]
l=[input().split() for i in range(q)]

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

def init(init_val,c):
  for i in range(n):
    seg[c][i+num-1]=init_val[i]
  for i in range(num-2,-1,-1):
    seg[c][i]=segfunc(seg[c][2*i+1],seg[c][2*i+2])

def update(k,x,c):
  k+=num-1
  seg[c][k]+=x
  while k:
    k=(k-1)//2
    seg[c][k]=segfunc(seg[c][k*2+1],seg[c][k*2+2])

def query(p,q,c):
  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[c][p])
    if q&1==1:
      res=segfunc(res,seg[c][q])
      q-=1
    p=p//2
    q=(q-1)//2
  if p==q:
    res=segfunc(res,seg[c][p])
  else:
    res=segfunc(segfunc(res,seg[c][p]),seg[c][q])
  return res

ide_ele=0

num=2**(n-1).bit_length()
seg=[[ide_ele]*2*num for i in range(26)]

L=[[0 for i in range(n)] for j in range(26)]
for i in range(n):
  L[c.index(s[i])][i]+=1

for i in range(26):
  init(L[i],i)

for i in range(q):
  if l[i][0]=='1':
    update(int(l[i][1])-1,1,c.index(l[i][2]))
    update(int(l[i][1])-1,-1,c.index(s[int(l[i][1])-1]))
    s[int(l[i][1])-1]=l[i][2]
  else:
    ct=0
    for j in range(26):
      if query(int(l[i][1])-1,int(l[i][2]),j)!=0:
        ct+=1
    print(ct)

Submission status: Accepted

Solution code:
# ABC157e


#print(bin(toBitSet([1, 2, 3, 2])))

# for i in range(97, 123):
#    print(chr(i))


def main():
    import sys
    sys.setrecursionlimit(10**6)
    # 再帰関数を使わない限りPypyで出すこと

    class SegmentTree:
        #####単位元######
        ide_ele = 0

        # num:n以上の最小の2のべき乗

        def segfunc(self, x, y):
            return x | y  # 例としてmin関数を設定

        def __init__(self, n):
            super().__init__()
            self.num = 2**(n-1).bit_length()  # nは元々の配列の長さ
            self.seg = [self.ide_ele]*(2*self.num+1)

        def init(self, init_val):  # セグ木にしたい配列を渡す
            # set_val
            for i in range(len(init_val)):
                self.seg[i+self.num-1] = init_val[i]
            # built
            for i in range(self.num-2, -1, -1):
                self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])

        def update(self, k, x):
            k += self.num-1
            self.seg[k] = x
            while k:
                k = (k-1)//2
                self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])

        def query(self, p, q):
            if q <= p:
                return ide_ele
            p += self.num-1
            q += self.num-2
            res = self.ide_ele
            while q-p > 1:
                if p & 1 == 0:
                    res = self.segfunc(res, self.seg[p])
                if q & 1 == 1:
                    res = self.segfunc(res, self.seg[q])
                    q -= 1
                p = p//2
                q = (q-1)//2
            if p == q:
                res = self.segfunc(res, self.seg[p])
            else:
                res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
            return res

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

    def toBitSet(numberSet):
        theSet = 0
        for i in numberSet:
            theSet = theSet | 1 << i
        return theSet

    def alphabetToZeroIndexed(alphabet):
        return ord(alphabet) - 97

    tree = SegmentTree(n)

    for i in range(n):
        tree.update(i+1, toBitSet([alphabetToZeroIndexed(s[i])]))

    for _ in range(q):
        a, b, c = input().split()
        b = int(b)
        if int(a) == 1:
            tree.update(b, toBitSet([alphabetToZeroIndexed(c)]))
        else:
            c = int(c)
            print(bin(tree.query(b, c+1)).count('1'))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
N = int(input())
S = list(input())
Q = int(input())
alpha = "abcdefghijklmnopqrstuvwxyz"
d = dict()

for x in alpha:
    d[x] = ord(x) - 97


class segment_tree:
    n = 0
    segtree = []

    def __init__(self, A):
        N = len(A)
        self.n = (N-1).bit_length()
        self.n = 1 << self.n
        self.segtree = [0 for i in range(2*self.n)]
        for i in range(N):
            self.segtree[self.n+i-1] = 1 << d[A[i]]
        for i in range(self.n - 2, -1, -1):
            self.segtree[i] = self.segtree[i*2 + 1] | self.segtree[i*2 + 2]

    def update(self, i, x):
        id = self.n+i - 1
        self.segtree[id] = 1 << d[x]
        while(id > 0):
            id = (id - 1) // 2
            self.segtree[id] = self.segtree[id *
                                            2 + 1] | self.segtree[id*2 + 2]

    def query(self, a, b, k, l, r):
        if r <= a or l >= b:
            return(0)
        if a <= l and r <= b:
            return(self.segtree[k])
        else:
            vl = self.query(a, b, k*2+1, l, (l+r)//2)
            vr = self.query(a, b, k*2+2, (l+r)//2, r)
            return(vl | vr)


def popcount(x):
    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
    x = x + (x >> 8)  # 16bitごと
    x = x + (x >> 16)  # 32bitごと
    x = x + (x >> 32)  # 64bitごと = 全部の合計
    return x & 0x0000007f


ST = segment_tree(S[:-1])
N = (N-1).bit_length()
N = 1 << N

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

    if t == "1":
        a = int(a)
        ST.update(a-1, b)
    elif t == "2":
        a = int(a)
        b = int(b)
        ret = ST.query(a-1, b, 0, 0, N)
        print(popcount(ret))

    # print(ST.segtree)

Submission status: Accepted

Solution code:
# ABC157e


#print(bin(toBitSet([1, 2, 3, 2])))

# for i in range(97, 123):
#    print(chr(i))


def main():
    import sys
    sys.setrecursionlimit(10**6)
    # 再帰関数を使わない限りPypyで出すこと

    #####segfunc######
    def segfunc(x, y):
        return x | y  # 例としてmin関数を設定

    def init(init_val):  # セグ木にしたい配列を渡す
        # set_val
        for i in range(len(init_val)):
            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):
        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):
        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

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

    n = int(input())
    s = list(input())
    q = int(input())
    # num:n以上の最小の2のべき乗
    num = 2**(n-1).bit_length()  # nは元々の配列の長さ
    seg = [ide_ele] * (2 * num+1)

    def toBitSet(numberSet):
        theSet = 0
        for i in numberSet:
            theSet = theSet | 1 << i
        return theSet

    def alphabetToZeroIndexed(alphabet):
        return ord(alphabet)-97

    for i in range(n):
        update(i+1, toBitSet([alphabetToZeroIndexed(s[i])]))

    for _ in range(q):
        a, b, c = input().split()
        b = int(b)
        if int(a) == 1:
            update(b, toBitSet([alphabetToZeroIndexed(c)]))
        else:
            c = int(c)
            print(bin(query(b, c+1)).count('1'))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input().strip())
    s = list(input().strip())

    bit = [[0] * 26 for _ in range(n + 1)]

    def query(i):
        result = [0] * 26
        while i:
            for j, x in enumerate(bit[i]):
                result[j] += x
            i -= i & -i
        return result
    
    def update(i, c, val):
        j = ord(c) - ord("a")
        while i < len(bit):
            bit[i][j] += val
            i += i & -i

    for i, c in enumerate(s, 1):
        update(i, c, 1)

    q = int(input().strip())
    for _ in range(q):
        Q = input().strip().split()
        if Q[0] == "1":
            i, c = int(Q[1]), Q[2]
            update(i, s[i - 1], -1)
            update(i, c, 1)
            s[i - 1] = c
        else:
            l, r = int(Q[1]), int(Q[2])
            cnt = [x - y for x, y in zip(query(r), query(l - 1))]
            print(sum(x > 0 for x in cnt))


main()

Submission status: Accepted

Solution code:
# coding: UTF-8
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    class BIT():
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s
    
    N=int(input())
    S=list(input())
    Q=int(input())
    bit=[BIT(N) for _ in range(26)]
    
    S2=[0]*N
    
    for i in range(N):
        S2[i]=ord(S[i])-ord('a')
    
    for i,x in enumerate(S2):
        bit[x].add(i,1)
    
    for _ in range(Q):
        a,b,c=input().split()
        if a=='1':
            b=int(b)-1
            c=ord(c)-ord('a')
            bit[c].add(b,1)
            bit[S2[b]].add(b,-1)
            S2[b]=c
        else:
            b=int(b)-1
            c=int(c)-1
            ans=0
            for i in range(26):
                if bit[i].sum(c)-bit[i].sum(b-1):
                    ans+=1
            print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
#####segfunc######
def segfunc(x,y):
    return x | y

def init(init_val):
    #set_val
    for i in range(len(init_val)):
        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):
    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):
    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())[:-1]
ide_ele = 0
num =2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
s = [2 ** (ord(i) - ord('a')) for i in s]
init(s)
q = int(input())
for i in range(q):
    tmp = input()
    a,b,c = tmp[:-1].split()
    if a == "1":
        update(int(b)-1, 2 ** (ord(c) - ord('a')))
    else:
        if b == c:
            print(1)
        else:
            tmp = query(int(b)-1, int(c))
            tmp = format(tmp, 'b')
            print(tmp.count('1'))

Submission status: Accepted

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


class SegTree:
    def __init__(self, size):
        n = 1
        while n < size:
            n *= 2
        self.size = n
        self.data = [0] * (n*2)

    # change the i-th value from a to b
    def update(self, i, a, b):
        i += self.size - 1
        if a >= 0:
            self.data[i] &= ~(1 << a)
        self.data[i] |= 1 << b
        while i > 0:
            i = (i - 1) // 2
            self.data[i] = self.data[i*2+1] | self.data[i*2+2]

    def query(self, a, b):
        return self._query(a, b, 0, 0, self.size)

    def _query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.data[k]
        vl = self._query(a, b, k*2+1, l, (l+r)//2)
        vr = self._query(a, b, k*2+2, (l+r)//2, r)
        return vl | vr


N = int(input())
S = list(input().rstrip())
st = SegTree(N)
for i in range(N):
    st.update(i, -1, ord(S[i])-ord('a'))
Q = int(input())
for _ in range(Q):
    t, x, y = input().split()
    if t == '1':
        i = int(x) - 1
        c = y
        st.update(i, ord(S[i])-ord('a'), ord(c)-ord('a'))
        S[i] = c
    else:
        l = int(x) - 1
        r = int(y) - 1
        ans = 0
        bit = st.query(l, r+1)
        for i in range(26):
            ans += (bit >> i) & 1
        print(ans)

Submission status: Accepted

Solution code:
import sys


class SegTreeSet:
    """
    bitフラグで集合を管理するセグメント木

    要素の種類数は特に明示的に与える必要は無いが、まぁ常識の範囲内で
    """

    def __init__(self, n, initial=0):
        """
        :param n: 文字列長
        :param initial: 初期値
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [initial] * (n2 << 1)
        self.initial = initial

    def initial_construct(self, s):
        for i, x in enumerate(s, start=self.offset):
            self.tree[i] = x
        for i in range(self.offset - 1, 0, -1):
            self.tree[i] = self.tree[i << 1] | self.tree[(i << 1) + 1]

    def update(self, i, x):
        """
        i番目の値にxをXOR

        :param i: index(0-indexed)
        :param x: Bit flag for operating bitwise_xor on leaf node
        """
        i += self.offset
        self.tree[i] ^= x
        while i > 1:
            self.tree[i >> 1] = self.tree[i] | self.tree[i ^ 1]
            i >>= 1

    def get_size(self, a, b):
        """
        [a, b)の要素種数を得る

        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.initial

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result |= self.tree[r - 1]
            if l & 1:
                result |= self.tree[l]
                l += 1
            l >>= 1
            r >>= 1

        return bin(result).count('1')


char_mappings = {chr(i + 97): 1 << i for i in range(26)}

n = int(input())
s = input()
s = list(s)
st = SegTreeSet(n)
st.initial_construct(map(char_mappings.get, s))
q = int(input())
ans = []
for line in sys.stdin:
    i, j, k = line.rstrip().split()
    if i == '1':
        j = int(j) - 1
        if s[j] == k:
            continue
        b = char_mappings[k] | char_mappings[s[j]]
        st.update(j, b)
        s[j] = k
    else:
        l = int(j) - 1
        r = int(k)
        ans.append(st.get_size(l, r))
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    s = input()
    m = int(input())
    abc = [input().split() for _ in [0]*m]
    alphabet = 'abcdefghijklmnopqrstuvwxyz'

    class segtree():
        def __init__(self, base, ini):  # self,モノイド,元の配列
            # ini：上限（下限）,base：元の配列,monoid：モノイド,tree：セグ木,depth：treeの深さ,
            # basesize：baseの要素数,treesize：treeの要素数,num：treesize-basesize
            # 初期値（上限とか下限）を決定
            self.ini = ini
            # セグ木の要素数（num）および深さ（depth）を計算
            self.basesize = len(base)
            self.num, self.depth = 1, 1
            while self.num < self.basesize:
                self.num *= 2
                self.depth += 1
            self.num -= 1
            # 関数（モノイド、今回はmin）を設定
            self.monoid = lambda x, y: x | y
            # セグ木を構築
            self.treesize = self.num*2+1
            self.tree = [None]*self.treesize
            # segtree[m]以降に代入したい配列を入力していく
            for i in range(self.num, self.num+self.basesize):
                self.tree[i] = base[i-self.num]
            for i in range(self.num+self.basesize, self.treesize):
                self.tree[i] = ini
            # segtree[m]以降の情報を使って、0に向かってセグ木を構築していく
            for i in range(self.num-1, -1, -1):
                self.tree[i] = self.monoid(self.tree[2*i+1], self.tree[2*i+2])

        # 条件を満たす(サンプルの条件はs以下になること)最大のインデックスを返す関数
        def max_index(self, index_func):
            # 探していく
            i = 0
            while i < self.num:
                k = 2*i+1
                if index_func(self.tree[k+1]):
                    i = k+1
                    continue
                if index_func(self.tree[k]):
                    i = k
                    continue
                return -1
            return i-self.num

        # 条件を満たす(サンプルの条件はs以下になること)最小のインデックスを返す関数
        def min_index(self, index_func):
            # 探していく
            i = 0
            while i < self.num:
                k = 2*i+1
                if index_func(self.tree[k]):
                    i = k
                    continue
                if index_func(self.tree[k+1]):
                    i = k+1
                    continue
                return -1
            return i-self.num

        # 半開区間[lower,upper)の最小値（とか）を探す関数
        def search(self, lower, upper):
            # 返り値を初期化
            ret = self.ini
            l = lower+self.num
            r = upper+self.num
            while l < r:
                if r % 2 == 0:
                    r -= 1
                    ret = self.monoid(ret, self.tree[r])
                if l % 2 == 0:
                    ret = self.monoid(ret, self.tree[l])
                    l += 1
                l //= 2
                r //= 2
            return ret

        # base[i]をsに更新したときにセグ木全体を更新する関数
        def update(self, index, new_value):
            i = index+self.num
            self.tree[i] = new_value
            while i != 0:
                i = (i-1)//2
                temp = self.monoid(self.tree[2*i+1], self.tree[2*i+2])
                if self.tree[i] != temp:
                    self.tree[i] = temp
                    continue
                break

    d = {alphabet[i]: i for i in range(26)}
    seg = segtree([2**d[s[i]] for i in range(n)], 0)

    for a, b, c in abc:
        if a == "1":
            b = int(b)
            seg.update(b-1, 2**d[c])
        else:
            b, c = int(b), int(c)
            print(bin(seg.search(b-1, c)).count("1"))


main()

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
Q = int(input())
query = [input().split() for _ in range(Q)]

bit = [[0 for _ in range(26)] for _ in range(N + 1)]

def bit_add(i, s, j):
    ss = ord(s) - ord("a")
    while i <= N:
        bit[i][ss] += j
        i += i & - i
        
def bit_sum(i):
    s = [0] * 26
    while i:
        for j in range(26):
            s[j] += bit[i][j]
        i -= i & -i
    return s
for i in range(1, N + 1):
    s = S[i - 1]
    bit_add(i, s, 1)

for x, y, z in query:
    if x == "1":
        y = int(y)
        bit_add(y, S[y - 1], -1)
        bit_add(y, z, 1)
        S[y - 1] = z
    if x == "2":
        answer = 0
        y, z = int(y) - 1, int(z)
        sum_y = bit_sum(y)
        sum_z = bit_sum(z)
        for i in range(26):
            if sum_z[i] - sum_y[i] > 0:
                answer += 1
        print(answer)

Submission status: Accepted

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

import bisect

N = int(input())
indexess = [[] for _ in range(26)]

S = list(input())
for i, s in enumerate(S):
    indexess[ord(s) - 97].append(i)


Q = int(input())
for _ in range(Q):
    q1,q2, q3 = input().split()
    q2 = int(q2)

    if q1 == '1':
        s0 = S[q2-1]
        if s0 != q3:
            S[q2-1] = q3
            
            indexes = indexess[ord(s0) - 97]
            del indexes[bisect.bisect_left(indexes, q2-1)]
            bisect.insort(indexess[ord(q3) - 97], q2-1)

    else:
        cnt = 0
        q3 = int(q3)
        for indexes in indexess:
            
            if bisect.bisect_left(indexes, q2-1) < bisect.bisect_right(indexes, q3-1):
                cnt += 1

        print(cnt)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc157/tasks/abc157_e

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

sc = iter(open(0).read().split())
ni = lambda: int(next(sc))
ns = lambda: next(sc)

N, S, Q = ni(), list(ns()), ni()

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

A = []
for _ in range(Q):
    if ni() == 1:
        i, c = ni(), ns()
        B[ord(S[i - 1]) - ord('a')].add(i, -1)
        S[i - 1] = c
        B[ord(c) - ord('a')].add(i, 1)
    else:
        l, r = ni(), ni()
        A.append(sum(b.sum(l - 1) < b.sum(r) for b in B))

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub, or_

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)



def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                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.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret


@mt
def slv(N, S, Q):
    st = [SegmentTree([1 if ord(c) == ord('a')+ _ else 0 for c in S], add, 0) for _ in range(26)]
    S = [c for c in S]
    for q in Q:
        if q[0] == '1':
            i = int(q[1]) - 1
            c = S[i]
            st[ord(c)-ord('a')].update(i, 0)
            c = q[2]
            st[ord(c)-ord('a')].update(i, 1)
            S[i] = c
        if q[0] == '2':
            i = int(q[1]) - 1
            j = int(q[2]) - 1
            ans = 0
            for k in range(26):
                if st[k].query(i, j+1) > 0:
                    ans += 1
            print(ans)

# def slv(N, S, Q):
#     st = SegmentTree([1 << (ord(c) - ord('a')) for c in S], or_, 0)

#     for q in Q:
#         if q[0] == '1':
#             i = int(q[1]) - 1
#             c = q[2]
#             st.update(i, 1 << (ord(c) - ord('a')))
#         if q[0] == '2':
#             i = int(q[1]) - 1
#             j = int(q[2]) - 1
#             ans = 0
#             v = st.query(i, j+1)
#             for k in range(26):
#                 if (1 << k) & v:
#                     ans += 1
#             print(ans)


def main():
    N = read_int()
    S = read_str()
    Q = [read_str_n() for _ in range(read_int())]
    (slv(N, S, Q))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
NN = 19
X = [0] * ((1<<NN+1)-1)
 
def popcount(x):
    x -= (x >> 1) & 0x55555555
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x += x >> 8
    x += x >> 16
    return x & 0x3f

def update(a, x):
    i = (1<<NN) - 1 + a
    X[i] = x
    while True:
        i = (i-1) // 2
        X[i] = X[2*i+1] | X[2*i+2]
        if i == 0:
            break

def rangeor(a, b):
    l = a + (1<<NN)
    r = b + (1<<NN)
    x = 0
    while l < r:
        if l%2:
            x |= X[l-1]
            l += 1
        if r%2:
            r -= 1
            x |= X[r-1]
        l >>= 1
        r >>= 1
    return x

N = int(input())
A = [ord(a) - 97 for a in input()]
for i, a in enumerate(A):
    X[(1<<NN) + i] = 1 << a
for i in range((1<<NN)-1)[::-1]:
    X[i] = X[i*2+1] | X[i*2+2]

Q = int(input())
for _ in range(Q):
    a, b, c = input().rstrip().split()
    if a == "1":
        b = int(b)
        c = ord(c) - 97
        update(b, 1<<c)
    else:
        b, c = int(b), int(c)
        print(popcount(rangeor(b, c+1)))