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: Wrong Answer

Solution code:
class BalancingTree:
    """平衡二分木のクラス
    Pivotを使った実装.
    0以上2^n - 2以下の整数を扱う
    """
    def __init__(self, n):
        """
        2の指数nで初期化
        """
        self.N = n
        self.root = self.node(1<<n, 1<<n)

    def debug(self):
        """デバッグ用の関数"""
        def debug_info(nd_):
            return (nd_.value - 1, nd_.pivot - 1, nd_.left.value - 1 if nd_.left else -1, nd_.right.value - 1 if nd_.right else -1)

        def debug_node(nd):
            re = []
            if nd.left:
                re += debug_node(nd.left)
            if nd.value: re.append(debug_info(nd))
            if nd.right:
                re += debug_node(nd.right)
            return re
        print("Debug - root =", self.root.value - 1, debug_node(self.root)[:50])

    def append(self, v):
        """
        v を追加（その時点で v はない前提）
        """
        v += 1
        nd = self.root
        while True:
            if v == nd.value:
                # v がすでに存在する場合に何か処理が必要ならここに書く
                return 0
            else:
                mi, ma = min(v, nd.value), max(v, nd.value)
                if mi < nd.pivot:
                    nd.value = ma
                    if nd.left:
                        nd = nd.left
                        v = mi
                    else:
                        p = nd.pivot
                        nd.left = self.node(mi, p - (p&-p)//2)
                        break
                else:
                    nd.value = mi
                    if nd.right:
                        nd = nd.right
                        v = ma
                    else:
                        p = nd.pivot
                        nd.right = self.node(ma, p + (p&-p)//2)
                        break

    def leftmost(self, nd):
        if nd.left: return self.leftmost(nd.left)
        return nd

    def rightmost(self, nd):
        if nd.right: return self.rightmost(nd.right)
        return nd

    def find_l(self, v):
        """
        vより真に小さいやつの中での最大値（なければ-1）
        """
        v += 1
        nd = self.root
        prev = 0
        if nd.value < v: prev = nd.value
        while True:
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                prev = nd.value
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def find_r(self, v):
        """
        vより真に大きいやつの中での最小値（なければRoot）
        """
        v += 1
        nd = self.root
        prev = 0
        if nd.value > v: prev = nd.value
        while True:
            if v < nd.value:
                prev = nd.value
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    @property
    def max(self):
        """最大値の属性"""
        return self.find_l((1<<self.N)-1)

    @property
    def min(self):
        """最小値の属性"""
        return self.find_r(-1)

    def delete(self, v, nd = None, prev = None):
        """
        値がvのノードがあれば削除（なければ何もしない）
        """
        v += 1
        if not nd: nd = self.root
        if not prev: prev = nd
        while v != nd.value:
            prev = nd
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return
        if (not nd.left) and (not nd.right):
            if nd.value < prev.value:
                prev.left = None
            else:
                prev.right = None
        elif not nd.left:
            if nd.value < prev.value:
                prev.left = nd.right
            else:
                prev.right = nd.right
        elif not nd.right:
            if nd.value < prev.value:
                prev.left = nd.left
            else:
                prev.right = nd.left
        else:
            nd.value = self.leftmost(nd.right).value
            self.delete(nd.value - 1, nd.right, nd)

    def __contains__(self, v: int) -> bool:
        return self.find_r(v - 1) == v

    class node:
        """ノードをあらわすクラス
        v: 値
        p: ピボット値
        で初期化
        """
        def __init__(self, v, p):
            self.value = v
            self.pivot = p
            self.left = None
            self.right = None

Trees = [BalancingTree(50) for _ in range(26)]
N = int(input())
S = input()
Q = int(input())
alphabets = list("abcdefghijklmnopqrstuvwxyz")
c2n = {c: i for i, c in enumerate(alphabets)}
for i in range(N):
    Trees[c2n[S[i]]].append(i+1)

for _ in range(Q):
    tmp = list(input().split())
    if tmp[0] == "1":
        _, i, c = tmp
        i = int(i)
        bef = S[i-1]
        if bef == c:
            continue
        Trees[c2n[bef]].delete(i)
        Trees[c2n[c]].append(i)
    else:
        _, l, r = tmp
        l = int(l)
        r = int(r)
        ans = 0
        for char in range(26):
            res = Trees[char].find_r(l-1)
            if l <= res <= r:
                ans += 1
        print(ans)

Submission status: Wrong Answer

Solution code:
class BalancingTree:
    """平衡二分木のクラス
    Pivotを使った実装.
    0以上2^n - 2以下の整数を扱う
    """
    def __init__(self, n):
        """
        2の指数nで初期化
        """
        self.N = n
        self.root = self.node(1<<n, 1<<n)

    def debug(self):
        """デバッグ用の関数"""
        def debug_info(nd_):
            return (nd_.value - 1, nd_.pivot - 1, nd_.left.value - 1 if nd_.left else -1, nd_.right.value - 1 if nd_.right else -1)

        def debug_node(nd):
            re = []
            if nd.left:
                re += debug_node(nd.left)
            if nd.value: re.append(debug_info(nd))
            if nd.right:
                re += debug_node(nd.right)
            return re
        print("Debug - root =", self.root.value - 1, debug_node(self.root)[:50])

    def append(self, v):
        """
        v を追加（その時点で v はない前提）
        """
        v += 1
        nd = self.root
        while True:
            if v == nd.value:
                # v がすでに存在する場合に何か処理が必要ならここに書く
                return 0
            else:
                mi, ma = min(v, nd.value), max(v, nd.value)
                if mi < nd.pivot:
                    nd.value = ma
                    if nd.left:
                        nd = nd.left
                        v = mi
                    else:
                        p = nd.pivot
                        nd.left = self.node(mi, p - (p&-p)//2)
                        break
                else:
                    nd.value = mi
                    if nd.right:
                        nd = nd.right
                        v = ma
                    else:
                        p = nd.pivot
                        nd.right = self.node(ma, p + (p&-p)//2)
                        break

    def leftmost(self, nd):
        if nd.left: return self.leftmost(nd.left)
        return nd

    def rightmost(self, nd):
        if nd.right: return self.rightmost(nd.right)
        return nd

    def find_l(self, v):
        """
        vより真に小さいやつの中での最大値（なければ-1）
        """
        v += 1
        nd = self.root
        prev = 0
        if nd.value < v: prev = nd.value
        while True:
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                prev = nd.value
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def find_r(self, v):
        """
        vより真に大きいやつの中での最小値（なければRoot）
        """
        v += 1
        nd = self.root
        prev = 0
        if nd.value > v: prev = nd.value
        while True:
            if v < nd.value:
                prev = nd.value
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    @property
    def max(self):
        """最大値の属性"""
        return self.find_l((1<<self.N)-1)

    @property
    def min(self):
        """最小値の属性"""
        return self.find_r(-1)

    def delete(self, v, nd = None, prev = None):
        """
        値がvのノードがあれば削除（なければ何もしない）
        """
        v += 1
        if not nd: nd = self.root
        if not prev: prev = nd
        while v != nd.value:
            prev = nd
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return
        if (not nd.left) and (not nd.right):
            if nd.value < prev.value:
                prev.left = None
            else:
                prev.right = None
        elif not nd.left:
            if nd.value < prev.value:
                prev.left = nd.right
            else:
                prev.right = nd.right
        elif not nd.right:
            if nd.value < prev.value:
                prev.left = nd.left
            else:
                prev.right = nd.left
        else:
            nd.value = self.leftmost(nd.right).value
            self.delete(nd.value - 1, nd.right, nd)

    def __contains__(self, v: int) -> bool:
        return self.find_r(v - 1) == v

    class node:
        """ノードをあらわすクラス
        v: 値
        p: ピボット値
        で初期化
        """
        def __init__(self, v, p):
            self.value = v
            self.pivot = p
            self.left = None
            self.right = None

Trees = [BalancingTree(40) for _ in range(26)]
N = int(input())
S = input()
Q = int(input())
alphabets = list("abcdefghijklmnopqrstuvwxyz")
c2n = {c: i for i, c in enumerate(alphabets)}
for i in range(N):
    Trees[c2n[S[i]]].append(i+1)

for _ in range(Q):
    tmp = list(input().split())
    if tmp[0] == "1":
        _, i, c = tmp
        i = int(i)
        bef = S[i-1]
        if bef == c:
            continue
        Trees[c2n[bef]].delete(i)
        Trees[c2n[c]].append(i)
    else:
        _, l, r = tmp
        l = int(l)
        r = int(r)
        ans = 0
        for char in range(26):
            res = Trees[char].find_r(l-1)
            if res <= r:
                ans += 1
        print(ans)

Submission status: Wrong Answer

Solution code:
class BalancingTree:
    """平衡二分木のクラス
    Pivotを使った実装.
    0以上2^n - 2以下の整数を扱う
    """
    def __init__(self, n):
        """
        2の指数nで初期化
        """
        self.N = n
        self.root = self.node(1<<n, 1<<n)

    def debug(self):
        """デバッグ用の関数"""
        def debug_info(nd_):
            return (nd_.value - 1, nd_.pivot - 1, nd_.left.value - 1 if nd_.left else -1, nd_.right.value - 1 if nd_.right else -1)

        def debug_node(nd):
            re = []
            if nd.left:
                re += debug_node(nd.left)
            if nd.value: re.append(debug_info(nd))
            if nd.right:
                re += debug_node(nd.right)
            return re
        print("Debug - root =", self.root.value - 1, debug_node(self.root)[:50])

    def append(self, v):
        """
        v を追加（その時点で v はない前提）
        """
        v += 1
        nd = self.root
        while True:
            if v == nd.value:
                # v がすでに存在する場合に何か処理が必要ならここに書く
                return 0
            else:
                mi, ma = min(v, nd.value), max(v, nd.value)
                if mi < nd.pivot:
                    nd.value = ma
                    if nd.left:
                        nd = nd.left
                        v = mi
                    else:
                        p = nd.pivot
                        nd.left = self.node(mi, p - (p&-p)//2)
                        break
                else:
                    nd.value = mi
                    if nd.right:
                        nd = nd.right
                        v = ma
                    else:
                        p = nd.pivot
                        nd.right = self.node(ma, p + (p&-p)//2)
                        break

    def leftmost(self, nd):
        if nd.left: return self.leftmost(nd.left)
        return nd

    def rightmost(self, nd):
        if nd.right: return self.rightmost(nd.right)
        return nd

    def find_l(self, v):
        """
        vより真に小さいやつの中での最大値（なければ-1）
        """
        v += 1
        nd = self.root
        prev = 0
        if nd.value < v: prev = nd.value
        while True:
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                prev = nd.value
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def find_r(self, v):
        """
        vより真に大きいやつの中での最小値（なければRoot）
        """
        v += 1
        nd = self.root
        prev = 0
        if nd.value > v: prev = nd.value
        while True:
            if v < nd.value:
                prev = nd.value
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    @property
    def max(self):
        """最大値の属性"""
        return self.find_l((1<<self.N)-1)

    @property
    def min(self):
        """最小値の属性"""
        return self.find_r(-1)

    def delete(self, v, nd = None, prev = None):
        """
        値がvのノードがあれば削除（なければ何もしない）
        """
        v += 1
        if not nd: nd = self.root
        if not prev: prev = nd
        while v != nd.value:
            prev = nd
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return
        if (not nd.left) and (not nd.right):
            if nd.value < prev.value:
                prev.left = None
            else:
                prev.right = None
        elif not nd.left:
            if nd.value < prev.value:
                prev.left = nd.right
            else:
                prev.right = nd.right
        elif not nd.right:
            if nd.value < prev.value:
                prev.left = nd.left
            else:
                prev.right = nd.left
        else:
            nd.value = self.leftmost(nd.right).value
            self.delete(nd.value - 1, nd.right, nd)

    def __contains__(self, v: int) -> bool:
        return self.find_r(v - 1) == v

    class node:
        """ノードをあらわすクラス
        v: 値
        p: ピボット値
        で初期化
        """
        def __init__(self, v, p):
            self.value = v
            self.pivot = p
            self.left = None
            self.right = None

Trees = [BalancingTree(32) for _ in range(26)]
N = int(input())
S = input()
Q = int(input())
alphabets = list("abcdefghijklmnopqrstuvwxyz")
c2n = {c: i for i, c in enumerate(alphabets)}
for i in range(N):
    Trees[c2n[S[i]]].append(i+1)

for _ in range(Q):
    tmp = list(input().split())
    if tmp[0] == "1":
        _, i, c = tmp
        i = int(i)
        bef = S[i-1]
        if bef == c:
            continue
        Trees[c2n[bef]].delete(i)
        Trees[c2n[c]].append(i)
    else:
        _, l, r = tmp
        l = int(l)
        r = int(r)
        ans = 0
        for char in range(26):
            res = Trees[char].find_r(l-1)
            if res <= r:
                ans += 1
        print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
S = input()
Q = int(input())
charcum = [[0]*(N+1) for _ in range(26)]
alphabets = list("abcdefghijklmnopqrstuvwxyz")
c2n = {c: i for i, c in enumerate(alphabets)}
n2c = {i: c for c, i in c2n.items()}

for char in alphabets:
    num = c2n[char]
    for i in range(1, N+1):
        charcum[num][i] = charcum[num][i-1] + int(S[i-1]==char)

# delta = [[0]*(N+1) for _ in range(26)]
change = {char: [] for char in range(26)}
for _ in range(Q):
    tmp = list(input().split())
    if tmp[0] == "1":
        _, i, c = tmp
        i = int(i)
        bef = S[i-1]
        if bef == c:
            continue
        change[c2n[bef]].append((i, -1))
        change[c2n[c]].append((i, 1))
        # delta[c2n[bef]][i] -= 1
        # delta[c2n[c]][i] += 1
    else:
        _, l, r = tmp
        l = int(l)
        r = int(r)
        ans = 0
        for char in range(26):
            cum_l = charcum[char][l-1]
            cum_r = charcum[char][r]
            for idx, d_cum in change[char]:
                if idx <= l-1:
                    cum_l += d_cum
                    cum_r += d_cum
                elif l <= idx <= r:
                    cum_r += d_cum
            if cum_r - cum_l > 0:
                ans += 1
        print(ans)

Submission status: Wrong Answer

Solution code:
class SegmentTree:
    def __init__(self,n,ele=0):
        self.ide_ele = ele
        self.num =2**(n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num

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

    def init(self,init_val):
        for i in range(len(init_val)):
            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,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
      
N,S,Q=int(input()),input(),int(input())
d={'a': 1, 'b': 2, 'c': 4, 'd': 8, 'e': 16, 'f': 32, 'g': 64, 'h': 128, 'i': 256, 'j': 512, 'k': 1024, 'l': 2048, 'm': 4096, 'n': 8192, 'o': 16384, 'p': 32768, 'q': 65536, 'r': 131072, 's': 262144, 't': 524288, 'u': 1048576, 'v': 2097152, 'w': 4194304, 'x': 8388608, 'y': 16777216, 'z': 33554432}

initial=[d[c] for c in list(S)]

ST=SegmentTree(N)
ST.init(initial)

for _ in range(Q):
    typ,a,b=input().split()
    if typ=='1':
        i,c=int(a),d[b]
        ST.update(i,c)
    else:
        l,r=int(a)-1,int(b)
        x=bin(ST.query(l,r))[2:]
        print(sum(map(int,list(x))))

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())
S = list(input())
Q = int(input())

bit_tree = [[0] * (N+1) for _ in range(26)]
def BIT_add(i, tree):
    while i <= N:
        tree[i] += 1
        i += i&(-i)

def BIT_sub(i, tree):
    while i <= N:
        tree[i] -= 1
        i += i&(-i)

def BIT_sum(i, tree):
    s = 0
    while i:
        s += tree[i]
        i -= i&(-i)
    return s

for i in range(N):
    x = ord(S[i]) - ord('a')
    BIT_add(i + 1, bit_tree[x])
x = BIT_sum(N, bit_tree[1])

for q in range(Q):
    line = list(input().split())
    if line[0] == '1':
        i, c = line[1:]
        i = int(i) - 1
        old_c = ord(S[i]) - ord('a')
        new_c = ord(c) - ord('a')
        BIT_sub(i, bit_tree[old_c])
        BIT_add(i, bit_tree[new_c])
        S[i] = c
    else:
        l, r = map(int, line[1:])
        now = 0
        for i in range(26):
            cnt = BIT_sum(r, bit_tree[i]) - BIT_sum(l - 1, bit_tree[i])
            if cnt > 0:
                now += 1
        print(now)

Submission status: Wrong Answer

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

def myord(x):
    return ord(x)-ord('a')

L=[[0]*26]

for i in range(N):
    L.append([l for l in L[i]])
    L[i+1][myord(S[i])]+=1

QL1=[]
QL2=[]
for _ in range(Q):
    a,b,c=input().split()
    if a=='1':
        b=int(b)
        if S[b-1]!=c:
            QL1.append([0]*(b-1)+[1]*(N-b+2))
            QL2.append((myord(S[b-1]),myord(c)))
            S[b-1]=c
    else:
        b,c=int(b),int(c)
        for i in range(len(QL1)):
            if QL1[i][b-1]:
                QL1[i][b-1]=0
                d,e=QL2[i]
                L[b-1][d]-=1
                L[b-1][e]+=1
            if QL1[i][c]:
                QL1[i][c]=0
                d,e=QL2[i]
                L[c][d]-=1
                L[c][e]+=1
        s=0
        for i in range(26):
            if L[c][i]>L[b-1][i]:
                s+=1
        print(s)

Submission status: Wrong Answer

Solution code:
class SegTree:
    """ segment tree with point modification and range product. """
    # # https://yukicoder.me/submissions/452850
    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]
    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)

Submission status: Wrong Answer

Solution code:
import random as r
class Skip_Node:
  def __init__(self,value):
    self.value=value
    self.height=1
    while r.random()<0.5:
      self.height+=1
    self.pointer=[None for i in range(self.height)]

class Skip_List:
  def __init__(self):
    self.max_height=1
    self.pointer=[None]
  
  def insert(self,value):
    node=Skip_Node(value)
    t=self.pointer[-1]
    bt=self
    for i in range(min(self.max_height,node.height)-1,-1,-1):
      while t!=None and (t==self or t.value<value):
        bt,t=t,t.pointer[i]
      bt.pointer[i]=node
      node.pointer[i]=t
      t=bt
    for i in range(self.max_height,node.height):
      self.pointer.append(node)
    self.max_height=max(self.max_height,node.height)
  
  def find(self,value):
    t=self
    for i in range(self.max_height-1,-1,-1):
      while t.pointer[i]!=None and t.pointer[i].value<value:
        t=t.pointer[i]
    return t.pointer[0].value if t.pointer[0] else None
  
  def erase(self,value):
    t=self
    for i in range(self.max_height-1,-1,-1):
      while t.pointer[i]!=None and t.pointer[i].value<value:
        t=t.pointer[i]
      if t.pointer[i]!=None and t.pointer[i].value==value:
        t.pointer[i]=t.pointer[i].pointer[i]
    
n=int(input())
s=list(input())
ls=len(s)
toa="abcdefghijklmnopqrstuvwxyz"
ato={}
for i in range(26):
  ato[toa[i]]=i
l=[Skip_List() for i in range(26)]
for i in range(ls):
  l[ato[s[i]]].insert(i)

q=int(input())
for i in range(q):
  t,a,b=input().split()
  if t=="1":
    a=int(a)-1
    l[ato[s[a]]].erase(a)
    s[a]=b
    l[ato[b]].insert(a)
  else:
    c=0
    a=int(a)-1
    b=int(b)
    for i in range(26):
      f=l[i].find(a)
      if f!=None and f<b:
        c+=1
    print(c)

Submission status: Wrong Answer

Solution code:
import random as r
class Skip_Node:
  def __init__(self,value):
    self.value=value
    self.height=1
    while r.random()<0.5:
      self.height+=1
    self.pointer=[None for i in range(self.height)]

class Skip_List:
  def __init__(self):
    self.max_height=1
    self.pointer=[None]
  
  def insert(self,value):
    node=Skip_Node(value)
    t=self.pointer[-1]
    bt=self
    for i in range(min(self.max_height,node.height)-1,-1,-1):
      while t!=None and t.value<value:
        bt,t=t,t.pointer[i]
      bt.pointer[i]=node
      node.pointer[i]=t
      t=bt
    for i in range(self.max_height,node.height):
      self.pointer.append(node)
  
  def find(self,value):
    t=self
    for i in range(self.max_height-1,-1,-1):
      while t.pointer[i]!=None and t.pointer[i].value<value:
        t=t.pointer[i]
    return t.pointer[0].value if t.pointer[0] else None
  
  def erase(self,value):
    t=self
    for i in range(self.max_height-1,-1,-1):
      while t.pointer[i]!=None and t.pointer[i].value<value:
        t=t.pointer[i]
      if t.pointer[i]!=None and t.pointer[i].value==value:
        t.pointer[i]=t.pointer[i].pointer[i]
    
n=int(input())
s=list(input())
ls=len(s)
toa="abcdefghijklmnopqrstuvwxyz"
ato={}
for i in range(26):
  ato[toa[i]]=i
l=[Skip_List() for i in range(26)]
for i in range(ls):
  l[ato[s[i]]].insert(i)

q=int(input())
for i in range(q):
  t,a,b=input().split()
  if t=="1":
    a=int(a)-1
    l[ato[s[a]]].erase(a)
    s[a]=b
    l[ato[b]].insert(a)
  else:
    c=0
    a=int(a)-1
    b=int(b)
    for i in range(26):
      f=l[i].find(a)
      if f!=None and f<b:
        c+=1
    print(c)

Submission status: Wrong Answer

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

class SegmentTree():
    def __init__(self,A,n,ide_ele):
        self.ide_ele=ide_ele
        self.num =2**(n-1).bit_length()
        self.seg = [self.ide_ele]*2*self.num
        #set_val
        for i in range(n):
            self.seg[i+self.num-1]=A[i]
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=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] = 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 = segfunc(res,self.seg[p])
            if q&1 == 1:
                res = segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res,self.seg[p])
        else:
            res = segfunc(segfunc(res,self.seg[p]),self.seg[q])
        return res

N = int(input())
S = list(input())
Q = int(input())
al=[chr(ord('a') + i) for i in range(26)]
Strs = [[0]*N for i in range(26)]
Trees = []
for i in range(26):
    for j in range(N):
        if S[j]==al[i]:
            Strs[i][j]=1
    ST = SegmentTree(Strs[i],N,0)
    Trees.append(ST)

for i in range(Q):
    Bin, X, Y = list(input().split(" "))
    if int(Bin)==1:
        iq,cq = int(X)-1,Y
        alind = ord(cq) - ord('a')
        Trees[alind].update(iq,1)
    else:
        lq,rq = int(X)-1,int(Y)-1
        cnt = 0
        for j in range(26):
            cnt += 1*(Trees[j].query(lq,rq+1)>0)
        print(cnt)

Submission status: Wrong Answer

Solution code:
class SegmentTree: #1-indexed
    def __init__(self,list,a,f=lambda x,y:x+y,inf=0):
        self.height=(len(list)-1).bit_length()+1 #木の高さ
        self.id=inf #単位元
        self.tree=[self.id]*(2**self.height) #木を単位元で初期化
        self.f=f
        for i in range(len(list)):
            if list[i]==a:
                self.tree[2**(self.height-1)+i]=1
        for i in range(2**(self.height-1)-1,0,-1):
            self.tree[i]=self.f(self.tree[2*i],self.tree[2*i+1])
        
    def update(self,i,x): #i番目の要素をxに変更(0-indexed)
        i+=2**(self.height-1)
        self.tree[i]=x
        while i>1:
            i//=2
            self.tree[i]=self.f(self.tree[2*i],self.tree[2*i+1])
    
    def query(self,l,r): #0-indexed
        l+=2**(self.height-1)
        r+=2**(self.height-1)
        lf,rf=self.id,self.id
        while l<r:
            if l&1:
                lf=self.f(lf,self.tree[l])
                l+=1
            if r&1:
                r-=1
                rf=self.f(self.tree[r],rf)
            l//=2
            r//=2
        return self.f(lf,rf)
n=int(input())
s=input()
q=int(input())
l=[]
for i in range(26):
    l.append(SegmentTree(s,chr(97+i),f=lambda x,y:x or y))
for _ in range(q):
    a,b,c=input().split()
    if a=="1":
        b=int(b)-1
        l[ord(s[b])-97].update(b,0)
        l[ord(c)-97].update(b,1)
    else:
        b,c=int(b)-1,int(c)
        count=0
        for i in range(26):
            if l[i].query(b,c):
                count+=1
        print(count)