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 .

Solution (Python):
n=int(input())
s=list(input())
x=[{ord(c)-ord('a')} for c in s]


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

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

def update(k, x):
    k += num - 1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[2*k+1], seg[2*k+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 = set()


num = 2**(n-1).bit_length()
seg = [ide_ele]*2*num

x=init(x)
q=int(input())

for i in range(q):
    t,l,r=input().split()

    if t=='1':
        update(int(l)-1,{ord(r)-ord('a')})
    
    else:
        print(len(query(int(l)-1,int(r))))

Solution (Python):
class SegTree():
    def segFunc(self, x, y):
        return x+y
    def searchIndexFunc(self, val):
        return True
    def __init__(self, ide, init_val):
        n = len(init_val)
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        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, idx, val):
        idx += self.num-1
        self.seg[idx] = val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def addition(self, idx, val):
        idx += self.num-1
        self.seg[idx] += val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def multiplication(self, idx, val):
        idx += self.num-1
        self.seg[idx] *= val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segFunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def query(self, begin, end):
        if end <= begin:
            return self.ide_ele
        begin += self.num-1
        end += self.num-2
        res = self.ide_ele
        while begin + 1 < end:
            if begin&1 == 0:
                res = self.segFunc(res, self.seg[begin])
            if end&1 == 1:
                res = self.segFunc(res, self.seg[end])
                end -= 1
            begin = begin//2
            end = (end-1)//2
        if begin == end:
            res = self.segFunc(res, self.seg[begin])
        else:
            res = self.segFunc(self.segFunc(res, self.seg[begin]), self.seg[end])
        return res
    def getLargestIndex(self, begin, end):
        L, R = begin, end
        if not self.searchIndexFunc(self.query(begin, end)):
            return None
        while L+1 < R:
            P = (L+R)//2
            if self.searchIndexFunc(self.query(P, R)):
                L = P
            else:
                R = P
        return L
    def getSmallestIndex(self, begin, end):
        L, R = begin, end
        if not self.searchIndexFunc(self.query(begin, end)):
            return None
        while L+1 < R:
            P = (L+R+1)//2
            if self.searchIndexFunc(self.query(L, P)):
                R = P
            else:
                L = P
        return L

def main():
    n = int(input())
    s = input()
    alp = [[0]*n for _ in range(26)]
    for i, c in enumerate(s):
        alp[ord(c) - ord("a")][i] = 1
    seg = [SegTree(0, alp[i]) for i in range(26)]
    q = int(input())
    ans = []
    for _ in range(q):
        a, b, c = map(str, input().split())
        if a == "1":
            b = int(b) - 1
            for i in range(26):
                if alp[i][b] == 1:
                    alp[i][b] = 0
                    seg[i].update(b, 0)
            alp[ord(c) - ord("a")][b] = 1
            seg[ord(c) - ord("a")].update(b, 1)
        else:
            b, c = int(b)-1, int(c)
            cnt = 0
            for i in range(26):
                if seg[i].query(b, c) > 0:
                    cnt += 1
            ans.append(cnt)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)

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

    def get_sum(self, i):
        i += 1
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i & -i
        return x

    
    def get_sum_range(self, l, r):
        return self.get_sum(r - 1) - self.get_sum(l - 1)


def main():
    N = int(readline())
    S = readline().strip()
    Q = int(readline())

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

    S = list(S)
    ans = []

    for _ in range(Q):
        n, a, b = readline().split()
        if n == '1':
            i = int(a) - 1
            if b != S[i]:
                bit[ord(S[i]) - ord('a')].add(i, -1)
                bit[ord(b) - ord('a')].add(i, 1)
                S[i] = b
        else:
            res = 0
            for i in range(26):
                if bit[i].get_sum_range(int(a) - 1, int(b)):
                    res += 1
            ans.append(res)

    print(*ans, sep='\n')

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)

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

    def get_sum(self, i):
        i += 1
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i & -i
        return x

    
    def get_sum_range(self, l, r):
        return self.get_sum(r - 1) - self.get_sum(l - 1)


def main():
    N = int(readline())
    S = readline().strip()
    Q = int(readline())

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

    S = list(S)
    ans = []

    for _ in range(Q):
        n, a, b = readline().split()
        if n == '1':
            i = int(a) - 1
            if b != S[i]:
                bit[ord(S[i]) - ord('a')].add(i, -1)
                bit[ord(b) - ord('a')].add(i, 1)
                S[i] = b
        else:
            res = 0
            l, r = int(a) - 1, int(b) - 1
            for i in range(26):
                if bit[i].get_sum_range(l, r + 1):
                    res += 1
            ans.append(res)

    print(*ans, sep='\n')

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)

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

    def get_sum(self, i):
        i += 1
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i & -i
        return x

    
    def get_sum_range(self, l, r):
        return self.get_sum(r - 1) - self.get_sum(l - 1)


def main():
    N = int(readline())
    S = readline().strip()
    Q = int(readline())
    query = [readline().split() for _ in range(Q)]

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

    S = list(S)
    ans = []

    for q in query:
        if q[0] == '1':
            i = int(q[1]) - 1
            c = q[2]
            bit[ord(S[i]) - ord('a')].add(i, -1)
            bit[ord(c) - ord('a')].add(i, 1)
            S[i] = c
        else:
            res = 0
            l, r = int(q[1]) - 1, int(q[2]) - 1
            for i in range(26):
                if bit[i].get_sum_range(l, r + 1):
                    res += 1
            ans.append(res)

    print(*ans, sep='\n')

    return


if __name__ == '__main__':
    main()

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

query=[]
for i in range(q):
    query.append(input())

ide_ele = set()

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

class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        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 += 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):
        
        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

al = [{s[i]} for i in range(n)]
seg = SegTree(al, segfunc, ide_ele)

for q in query:
    que,a,b=q.split()

    if que == "1":
        seg.update(int(a)-1,set(b))
    else:
        ret=seg.query(int(a)-1,int(b))
        print(len(ret))

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





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



ide_ele1 = set()


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

al = [{s[i]} for i in range(n)]
seg = SegTree(al, segfunc1, ide_ele1)

for i in range(q):
    x,y,z = input().split()
    y = int(y) - 1
    if x == "1":
        seg.update(y, {z})
    if x == "2":
        ans = len(seg.query(y, int(z)))
        print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    from collections import Counter
    class BIT:
        def __init__(self,n):
            self.size = n
            self.tree = [Counter([]) for _ in range(n+1)]
    
        def change(self,i,x,y):
            while i <= self.size:
                if x in self.tree[i]:
                    self.tree[i][x] -= 1
                if y not in self.tree[i]:
                    self.tree[i][y] = 0
                self.tree[i][y] += 1
                i += i&-i
    
        def sum(self,i):
            res = Counter([])
            while i > 0:
                res += self.tree[i]
                i -= i&-i
            return res

    N = int(input())
    st = BIT(N)
    S = list(input())
    Q = int(input())
    for i in range(N):
        st.change(i+1," ",S[i])

    for _ in range(Q):
        q,a,b = input().split()
        if q == "1":
            st.change(int(a),S[int(a)-1],b)
            S[int(a)-1] = b
        else:
            res = st.sum(int(b)) - st.sum(int(a)-1)
            ans = 0
            for v in res.values():
                if v > 0:
                    ans += 1
            print(ans)
main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()


class SegmentTree:

    __slots__ = ["func", "e", "original_size", "n", "data"]

    def __init__(self, length_or_list, func, e):
        self.func = func
        self.e = e
        if isinstance(length_or_list, int):
            self.original_size = length_or_list
            self.n = 1 << ((length_or_list - 1).bit_length())
            self.data = [self.e] * self.n
        else:
            self.original_size = len(length_or_list)
            self.n = 1 << ((self.original_size - 1).bit_length())
            self.data = [self.e] * self.n + length_or_list + \
                [self.e] * (self.n - self.original_size)
            for i in range(self.n-1, 0, -1):
                self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def replace(self, index, value):
        index += self.n
        self.data[index] = value
        index //= 2
        while index > 0:
            self.data[index] = self.func(
                self.data[2*index], self.data[2*index+1])
            index //= 2

    def folded(self, l, r):
        left_folded = self.e
        right_folded = self.e
        l += self.n
        r += self.n
        while l < r:
            if l % 2:
                left_folded = self.func(left_folded, self.data[l])
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.func(self.data[r], right_folded)
            l //= 2
            r //= 2
        return self.func(left_folded, right_folded)

    def all_folded(self):
        return self.data[1]

    def __getitem__(self, index):
        return self.data[self.n + index]

    def max_right(self, l, f):
        
        if l >= self.original_size:
            return self.original_size
        l += self.n
        left_folded = self.e
        while True:
            
            while l % 2 == 0:
                l //= 2
            if not f(self.func(left_folded, self.data[l])):
                while l < self.n:
                    l *= 2
                    if f(self.func(left_folded, self.data[l])):
                        left_folded = self.func(left_folded, self.data[l])
                        l += 1
                return l - self.n
            left_folded = self.func(left_folded, self.data[l])
            l += 1
            if l == l & -l:
                break
        return self.original_size

    
    def min_left(self, r, f):
        
        if r == 0:
            return 0
        r += self.n
        right_folded = self.e
        while True:
            r //= r & -r
            if not f(self.func(self.data[r], right_folded)):
                while r < self.n:
                    r = 2 * r + 1
                    if f(self.func(self.data[r], right_folded)):
                        right_folded = self.func(self.data[r], right_folded)
                        r -= 1
                return r + 1 - self.n
            if r == r & -r:
                break
        return 0


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


def main():
    N = int(input())
    S = input()
    S = list(map(lambda c: 2**(ord(c) - ord('a')), list(S)))
    Q = int(input())
    seg = SegmentTree(S, orr, 0)
    for _ in range(Q):
        num, x, y = input().split()
        if num == '1':
            seg.replace(int(x)-1, 2**(ord(y) - ord('a')))
        else:
            bits = seg.folded(int(x)-1, int(y))
            print(sum(map(int, list(bin(bits))[2:])))


if __name__ == '__main__':
    main()

Solution (Python):









class SegmentTree:
    
    
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

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

    
    
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] 
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    
    
    
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

from sys import stdin
def input():
    return stdin.readline().strip()

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

    forest = [SegmentTree(n, f=max, default=0) for _ in range(26)]
    for ind, si in enumerate(s):
        forest[ord(si) - 97].update(ind, 1)

    q = int(input())
    ans = []
    for _ in range(q):
        typ, l, r = input().split()
        l = int(l) - 1

        if typ == '1':
            forest[ord(s[l]) - 97].update(l, 0)
            s[l] = r
            forest[ord(r) - 97].update(l, 1)

        else:
            cnt = 0
            for tree in forest:
                if tree.min_index(l, 1) < int(r):
                    cnt += 1
            ans.append(cnt)

    for i in ans:
        print(i)

main()

Solution (Python):









class SegmentTree:
    
    
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

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

    
    
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] 
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    
    
    
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

from sys import stdin
def input():
    return stdin.readline().strip()

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

    forest = [SegmentTree(n, f=max, default=0) for _ in range(26)]
    for ind, si in enumerate(s):
        forest[ord(si) - 97].update(ind, 1)

    q = int(input())
    ans = []
    for _ in range(q):
        typ, l, r = input().split()
        l = int(l) - 1

        if typ == '1':
            forest[ord(s[l]) - 97].update(l, 0)
            s[l] = r
            forest[ord(r) - 97].update(l, 1)

        else:
            cnt = 0
            for tree in forest:
                if tree.query(l, int(r)) == 1:
                    cnt += 1
            ans.append(cnt)

    for i in ans:
        print(i)

main()

Solution (Python):



from bisect import bisect_left, bisect_right


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

al = 'abcdefghijklmnopqrstuvwxyz'
dicq = {i:[] for i in al}
for i, si in enumerate(s):
    dicq[si].append(i)

def q1(iq, cq):
    
    dicq[s[iq]].pop(bisect_left(dicq[s[iq]], iq))   
    s[iq] = cq
    dicq[cq].insert(bisect_left(dicq[cq], iq), iq)   

def q2(l, r):
    ret = 0
    for ai in al:
        if len(dicq[ai])==0: continue
        li = bisect_left(dicq[ai], l)
        ri = bisect_right(dicq[ai], r)
        if li != ri:
            ret += 1
        elif li == len(dicq[ai]): continue
        elif dicq[ai][li] == l:
            ret += 1
    
    print(ret)

for i in range(q):
    fg, x, y = input().split()
    if fg == '1':
        q1(int(x)-1, y)
    else:
        q2(int(x)-1, int(y)-1)

Solution (Python):
n = int(input())
s = list(input())
BITs = [[0]*(n+1) for _ in range(26)]

def c_idx(c):
    return ord(c) - 97

def query(pos):
    ret = [0]*26
    for i in range(26):
        tmp = 0
        p = pos
        while p > 0:
            tmp += BITs[i][p]
            p -= p & (-p)
        ret[i] = tmp
    return ret

def update(pos, a, x):
    while pos <= n:
        BITs[a][pos] += x
        pos += pos & (-pos)

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


q = int(input())
for _ in range(q):
    a, b, c = input().split()
    b = int(b)
    if a == "1":
        if s[b-1] == c:
            continue
        update(b, c_idx(s[b-1]), -1)
        update(b, c_idx(c), 1)
        s[b-1] = c
    else:
        c = int(c)
        count1 = query(c)
        count2 = query(b-1)
        ans = 0
        for i in range(26):
            if count1[i] - count2[i] > 0:
                ans += 1
        print(ans)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
import bisect



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




ide_ele = set()



class SegTree:
    """
    init(init_val, segfunc, ide_ele): 配列init_valで初期化、構築
    update(k, x): k番目の値をxに更新
    query(l, r): 区間[l, r)をsegfuncしたものを返す
    """

    def __init__(self, init_val, segfunc, ide_ele):
        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に更新
        :param k: index(0-index)
        :param 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したものを得る
        :param l: 0-index
        :param r: 0-index
        :return:
        """
        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 = I()
    S_ = S()
    S_list = []
    Q = I()
    for s in S_:
        val = set()
        val.add(s)
        S_list.append(val)


    segtree = SegTree(S_list, segfunc, ide_ele)
    for i in range(Q):
        query = LS()
        if query[0] == '1':
            i_q = int(query[1]) - 1
            c_q = query[2]
            segtree.update(i_q, {c_q})
        if query[0] == '2':
            l_q = int(query[1]) - 1
            r_q = int(query[2])
            ans = len(segtree.query(l_q, r_q))
            print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
class SegTree:
    """ segment tree with point modification and range product. """
    
    def __init__(self, N, data_f = min, data_unit=1<<30):
        self.N = N
        self.data_f = data_f
        self.data_unit = data_unit
        self.data = [self.data_unit] * (N + N)

    def build(self, raw_data):
        data = self.data
        f = self.data_f
        N = self.N
        data[N:] = raw_data[:]
        for i in range(N - 1, 0, -1):
            data[i] = f(data[i << 1], data[i << 1 | 1])

    def set_val(self, i, x):
        data = self.data
        f = self.data_f
        i += self.N
        data[i] = x
        while i > 1:
            data[i >> 1] = f(data[i], data[i ^ 1])
            i >>= 1

    def fold(self, L, R):
        """ compute for [L, R) """
        vL = vR = self.data_unit
        data = self.data
        f = self.data_f
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                vL = f(vL, data[L])
                L += 1
            if R & 1:
                R -= 1
                vR = f(data[R], vR)
            L >>= 1
            R >>= 1
        return f(vL, vR)
      
N=int(input())
S=input()
seg = SegTree(N,set.union,set())
S = [set([ord(S[i])-97]) for i in range(N)]
seg.build(S)
Q=int(input())
for i in range(Q):
  *q, = input().split()
  if q[0] == '1':
    i, c = q[1:]
    seg.set_val(int(i)-1,set([ord(c)-97]))
  else:
    l,r = map(int,q[1:])
    print(len(seg.fold(l-1,r)))

Solution (Python):
class SegTree:
    """ segment tree with point modification and range product. """
    
    def __init__(self, N, data_f = min, data_unit=1<<30):
        self.N = N
        self.data_f = data_f
        self.data_unit = data_unit
        self.data = [self.data_unit] * (N + N)

    def build(self, raw_data):
        data = self.data
        f = self.data_f
        N = self.N
        data[N:] = raw_data[:]
        for i in range(N - 1, 0, -1):
            data[i] = f(data[i << 1], data[i << 1 | 1])

    def set_val(self, i, x):
        data = self.data
        f = self.data_f
        i += self.N
        data[i] = x
        while i > 1:
            data[i >> 1] = f(data[i], data[i ^ 1])
            i >>= 1

    def fold(self, L, R):
        """ compute for [L, R) """
        vL = vR = self.data_unit
        data = self.data
        f = self.data_f
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                vL = f(vL, data[L])
                L += 1
            if R & 1:
                R -= 1
                vR = f(data[R], vR)
            L >>= 1
            R >>= 1
        return f(vL, vR)
      
N=int(input())
S=input()
data = [[0]*N for _ in range(26)]
di = {}
for i in range(N):
  data[ord(S[i])-97][i] = 1
  di[i] = S[i]

seg = [SegTree(N,max,0) for _ in range(26)]
for i in range(26):
  seg[i].build(data[i])
Q=int(input())
for i in range(Q):
  *q, = input().split()
  if q[0] == '1':
    i, c = q[1:]
    i = int(i)-1
    c_old = di[i]
    di[i] = c
    seg[ord(c_old)-97].set_val(i,0)
    seg[ord(c)-97].set_val(i,1)
  else:
    l,r = map(int,q[1:])
    ans=0
    for i in range(26):
      ans += seg[i].fold(l-1,r)
    print(ans)

Solution (Python):
class SegTree:
    """ segment tree with point modification and range product. """
    
    def __init__(self, N, data_f = min, data_unit=1<<30):
        self.N = N
        self.data_f = data_f
        self.data_unit = data_unit
        self.data = [self.data_unit] * (N + N)

    def build(self, raw_data):
        data = self.data
        f = self.data_f
        N = self.N
        data[N:] = raw_data[:]
        for i in range(N - 1, 0, -1):
            data[i] = f(data[i << 1], data[i << 1 | 1])

    def set_val(self, i, x):
        data = self.data
        f = self.data_f
        i += self.N
        data[i] = x
        while i > 1:
            data[i >> 1] = f(data[i], data[i ^ 1])
            i >>= 1

    def fold(self, L, R):
        """ compute for [L, R) """
        vL = vR = self.data_unit
        data = self.data
        f = self.data_f
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                vL = f(vL, data[L])
                L += 1
            if R & 1:
                R -= 1
                vR = f(data[R], vR)
            L >>= 1
            R >>= 1
        return f(vL, vR)
      
N=int(input())
S=input()
seg = SegTree(N,set.union,set())
S = [set(S[i]) for i in range(N)]
seg.build(S)
Q=int(input())
for i in range(Q):
  *q, = input().split()
  if q[0] == '1':
    i, c = q[1:]
    seg.set_val(int(i)-1,set(c))
  else:
    l,r = map(int,q[1:])
    print(len(seg.fold(l-1,r)))