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:
n=int(input())
s=[*input()]
q=int(input())
# BIT
B={chr(97+i):[0]*(n+1) for i in range(26)}
def bsum(c,i):
  s=0
  while i:
    s+=B[c][i]
    i-=i&-i
  return s
def badd(c,i,x):
  while i<=n:
    B[c][i]+=x
    i+=i&-i
for i,c in enumerate(s):
  badd(c,i+1,1)
for _ in range(q):
  x,y,z=input().split()
  y=int(y)
  if x=='1':
    badd(z,y,1)
    badd(s[y-1],y,-1)
  else:
    z=int(z)
    a=0
    for i in range(26):
      if bsum(chr(97+i),z)-bsum(chr(97+i),y-1): a+=1
    print(a)

Submission status: Wrong Answer

Solution code:
class segtree:

  def __init__(self, n,operator,identity):
    nb = bin(n)[2:]
    bc = sum([int(digit) for digit in nb])
    if bc == 1:
      self.num_end_leaves = 2**(len(nb)-1)
    else:
      self.num_end_leaves = 2**(len(nb))

    self.array = [identity for i in range(self.num_end_leaves * 2)]
    self.identity = identity
    self.operator =operator

  def update(self,x,val):
    actual_x = x+self.num_end_leaves
    self.array[actual_x] = val
    while actual_x > 0 :
      actual_x = actual_x//2
      self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])

  def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
    width_of_floor = self.num_end_leaves//(2**depth)
    leaf_right = leaf_left+width_of_floor-1

    if leaf_left > q_right or leaf_right < q_left:
      return  self.identity

    elif leaf_left >= q_left and leaf_right <= q_right:
      return self.array[arr_ind]

    else:
      val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
      val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
      return self.operator(val_l,val_r)
    
N = int(input())
S = '0'+input()
lst = ['0']
dic1 = {chr(ord('a')+i):[] for i in range(26)}
for i in range(1,N+1):
  dic1[S[i]].append(i)
  lst.append(S[i])
  
dic2 = {chr(ord('a')+i):[0] for i in range(26)}
dic3 = {}
for i in range(26):
  s = chr(ord('a')+i)
  k = 0
  for j in dic1[s]:
    dic2[s] += [j]*(j-k)
    k = j
  dic2[s] += [float('inf')]*(N-k+1)
  dic3[s] = segtree(N+2, min, float('inf'))
  for j in range(1,N+1):
    dic3[s].update(j, dic2[s][j])

Q = int(input())
for _ in range(Q):
  f,a,b = input().split()
  a = int(a)
  if f == '1':
    if lst[a] == b:
      continue
    dic3[lst[a]].update(a, dic3[lst[a]].get(a+1,N+1))
    dic3[b].update(a, a)
    lst[a] = b
  if f == '2':
    b = int(b)
    rlt = 0
    for i in range(26):
      s = chr(ord('a')+i)
      if dic3[s].get(a,N+1) <= b:
        rlt += 1
    print(rlt)

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())
S = '0'+input()

lst = ['0']
dic1 = {chr(ord('a')+i):[] for i in range(26)}
dic2 = {chr(ord('a')+i):set() for i in range(26)}

for i in range(1,N+1):
  heapq.heappush(dic1[S[i]], i)
  dic2[S[i]].add(i)
  lst.append(S[i])

Q = int(input())

for _ in range(Q):
  f, a, b = input().split()
  if f == '1':
    a = int(a)
    if lst[a] == b:
      continue   
    dic2[lst[a]].remove(a)
    while dic1[lst[a]]:
      if dic1[lst[a]][0] not in dic2[lst[a]]:
        heapq.heappop(dic1[lst[a]])
      else:
        break
    dic2[b].add(a)
    heapq.heappush(dic1[b], a)
    lst[a] = b
  if f == '2':
    rlt = 0
    a = int(a)
    b = int(b)
    for i in range(26):
      s = chr(ord('a')+i)
      if len(dic1[s]) == 0:
        continue
      tmp = []
      while dic1[s]:
        if dic1[s][0] < a:
          m = heapq.heappop(dic1[s])
          if m in dic2[s]:
            tmp.append(m)
        else:
          if dic1[s][0] <= b:
            rlt += 1
          break
      for t in tmp:
        heapq.heappush(dic1[s],t)

    print(rlt)

Submission status: Wrong Answer

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
S = [set([a]) for a in LS2()]


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

unit = set([])

class SegTree:  # モノイドに対して適用可能、Nが2冪でなくても良い
    def __init__(self,N,seg_func,unit):
        self.N = N
        self.func = seg_func
        self.unit = unit
        self.tree = [self.unit]*(2*self.N)
    def build(self,init_value):  # 初期値を[N,2N)に格納
        for i in range(self.N):
            self.tree[i+self.N] = init_value[i]
        for i in range(self.N-1,0,-1):
            self.tree[i] = self.func(self.tree[i << 1],self.tree[i << 1 | 1])
    def set_val(self,i,x):  # i番目(0-index)の値をxに変更
        i += self.N
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.func(self.tree[i << 1],self.tree[i << 1 | 1])
    def fold(self,L,R):  # [L,R)の区間取得
        L += self.N
        R += self.N
        vL = self.unit
        vR = self.unit
        while L < R:
            if L & 1:
                vL = self.func(vL,self.tree[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.func(self.tree[R],vR)
            L >>= 1
            R >>= 1
        return self.func(vL,vR)


seg = SegTree(N,seg_func,unit)
seg.build(S)
print(seg.tree)

Q = I()
for i in range(Q):
    a,b,c = LS()
    if a == '1':
        b = int(b)-1
        seg.set_val(b,set([c]))
    else:
        b,c = int(b)-1,int(c)-1
        print(len(seg.fold(b,c+1)))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    def update(self, idx, x):
        while idx <= self.n:
            self.bit[idx] += x
            idx += idx & (-idx)

    def query(self, idx):
        res = 0
        while idx > 0:
            res += self.bit[idx]
            idx -= idx & (-idx)
        return res

    def sec_sum(self, left, right):
        return self.query(right) - self.query(left)

    def debug(self):
        print(*[self.sec_sum(i - 1, i) for i in range(1, self.n + 1)])


def resolve():
    n = int(input())
    S = list(input().rstrip())
    q = int(input())
    query = [list(input().split()) for _ in range(q)]

    bits = [BIT(S) for _ in range(26)]
    for i in range(n):
        bits[ord(S[i]) - ord("a")].update(i + 1, 1)

    for j in range(q):
        if query[j][0] == "1":
            _, i, c = query[j]
            i = int(i)
            bits[ord(S[i - 1]) - ord("a")].update(i, 0)
            bits[ord(c) - ord("a")].update(i, 1)
            S[i - 1] = c
        else:
            _, l, r = query[j]
            l, r = int(l) - 1, int(r)
            res = 0
            for k in range(26):
                if bits[k].sec_sum(l, r):
                    res += 1
            print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

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


class SegmentTree:

    def __init__(self, n, op, e):
        """
        :param n: 要素数
        :param op: 二項演算
        :param e: 単位減
        例) 区間最小値  SegmentTree(n, lambda a, b : a if a < b else b, 10 ** 18)
            区間和     SegmentTree(n, lambda a, b : a + b, 0)
        """
        self.n = n
        self.op = op
        self.e = e
        self.size = 1 << (self.n - 1).bit_length()      # st[self.size + i] = array[i]
        self.tree = [self.e] * (self.size << 1)

    def built(self, array):
        """arrayを初期値とするセグメント木を構築"""
        for i in range(self.n):
            self.tree[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.op(self.tree[i << 1], self.tree[(i << 1) + 1])

    def update(self, i, x):
        """i 番目の要素を x に更新"""
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.op(self.tree[i << 1], self.tree[(i << 1) + 1])

    def get_val(self, l, r):
        """[l, r)の畳み込みの結果を返す"""
        l, r = l + self.size, r + self.size
        res = self.e
        while l < r:
            if l & 1:
                res = self.op(self.tree[l], res)
                l += 1
            if r & 1:
                r -= 1
                res = self.op(self.tree[r], res)
            l, r = l >> 1, r >> 1
        return res


##################################################################################################################

def popcount(x):
    return bin(x).count("1")

N = int(input())
st = SegmentTree(N, lambda a, b: a | b, 0)
S = input().strip()
data = []
for s in S:
    print(s,ord(s),ord("a"))
    data.append(1 << (ord(s) - ord("a")))
st.built(data)
Q = int(input())
for _ in range(Q):
    q, a, b = input().split()
    if q == "1":
        st.update(int(a)-1, 1 << (ord(b) - ord("a")))
    if q == "2":
        a = int(a) - 1
        b = int(b)
        print(popcount(st.get_val(a, b)))

Submission status: Wrong Answer

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


class Bit:
    def __init__(self, n):
        self.n = n
        self.tree = [0]*(n+1)
        self.el = [0]*(n+1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def add(self, i, x):
        """ i 番目の要素に x を足す """
        self.el[i] += x
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

    def get(self, i, j=None):
        """ 部分区間和 [i, j) """
        if j is None:
            return self.el[i]
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def lower_bound(self, x, equal=False):
        """ (a0+a1+...+ai < x となる最大の i, その時の a0+a1+...+ai )
             a0+a1+...+ai <= x としたい場合は equal = True
             二分探索であるため、ai>=0 を満たす必要がある"""
        sum_ = 0
        pos = -1    # 1-indexed の時は pos = 0
        if not equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] < x:  # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] <= x: # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        return pos, sum_

    def __getitem__(self, s):
        """ [a0, a1, a2, ...] """
        return self.el[s]

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for s in self.el[:self.n]:
            yield s

    def __str__(self):
        text1 = " ".join(["element:            "] + list(map(str, self)))
        text2 = " ".join(["cumsum(1-indexed):  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))
        return "\n".join((text1, text2))

####################################################################################################

import string

N = int(input())
S = input().strip()
Q = int(input())

B = [Bit(N) for _ in range(26)]

abc = string.ascii_lowercase                                            # [a-z] をロード
abc2 = dict()
for i, s in enumerate(abc):
    abc2[s] = i

for i, s in enumerate(S):
    B[abc2[s]].add(i,1)

for _ in range(Q):
    print(B[0])
    print(B[1])
    q = list(input().split())
    if q[0] == "1":
        a = int(q[1]) - 1
        b = q[2]
        for i in range(26):
            if B[i].el[a] == 1:
                B[i].add(a,-1)
        B[abc2[b]].add(a,1)
    if q[0] == "2":
        a = int(q[1]) - 1
        b = int(q[2]) - 1
        res = 0
        for i in range(26):
            res += (B[i].get(a, b+1) > 0)
        print(res)

Submission status: Wrong Answer

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


class Bit:
    def __init__(self, n):
        self.n = n
        self.tree = [0]*(n+1)
        self.el = [0]*(n+1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def replace(self, i, x):
        """ i番目の要素を x に変更する """
        self.el[i] = x
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

    def get(self, i, j=None):
        """ 部分区間和 [i, j) """
        if j is None:
            return self.el[i]
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def lower_bound(self, x, equal=False):
        """ (a0+a1+...+ai < x となる最大の i, その時の a0+a1+...+ai )
             a0+a1+...+ai <= x としたい場合は equal = True
             二分探索であるため、ai>=0 を満たす必要がある"""
        sum_ = 0
        pos = -1    # 1-indexed の時は pos = 0
        if not equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] < x:  # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] <= x: # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        return pos, sum_

    def __getitem__(self, s):
        """ [a0, a1, a2, ...] """
        return self.el[s]

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for s in self.el[:self.n]:
            yield s

    def __str__(self):
        text1 = " ".join(["element:            "] + list(map(str, self)))
        text2 = " ".join(["cumsum(1-indexed):  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))
        return "\n".join((text1, text2))

####################################################################################################

import string

N = int(input())
S = input().strip()
Q = int(input())

B = [Bit(N) for _ in range(26)]

abc = string.ascii_lowercase                                            # [a-z] をロード
abc2 = dict()
for i, s in enumerate(abc):
    abc2[s] = i

for i, s in enumerate(S):
    B[abc2[s]].replace(i,1)

for _ in range(Q):
    q = list(input().split())
    if q[0] == "1":
        a = int(q[1]) - 1
        b = q[2]
        for i in range(26):
            B[i].replace(a,0)
        B[abc2[b]].replace(a,1)
    if q[0] == "2":
        a = int(q[1]) - 1
        b = int(q[2]) - 1
        res = 0
        for i in range(26):
            res += (B[i].get(a, b+1) > 0)
        print(res)

Submission status: Wrong Answer

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT():
    def __init__(self, n):
        self.n = n
        self.bit = [[0] * (n + 1) for _ in range(26)]

    def add(self, i, value, idx):
        i = i + 1
        while i <= self.n:
            self.bit[idx][i] += value
            i += i & -i

    def _sum(self, i , idx):
        s = 0
        while i > 0:
            s += self.bit[idx][i]
            i -= i & -i
        return s

    def sum(self, l, r, idx):
        return self._sum(r, idx) - self._sum(l, idx)

n = int(input())
s = input()
q = int(input())
bit = BIT(n)
for i in range(n):
    bit.add( i, 1, ord(s[i])-97)
for i in range(q):
    q_type, fr, to = map(str,input().split())
    if q_type == "1":
        bit.add(int(fr)-1,1,ord(to)-97)
        bit.add(int(fr)-1,-1,ord(s[int(fr)-1])-97)
    else:
        tmp = 0
        for j in range(26):
            if bit.sum(int(fr)-1,int(to),j):
                tmp += 1
        print(tmp)

Submission status: Wrong Answer

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT():
    def __init__(self, n):
        self.n = n
        self.bit = [[0] * (n + 1) for _ in range(26)]

    def add(self, i, value, idx):
        i = i + 1
        while i <= self.n:
            self.bit[idx][i] += value
            i += i & -i

    def _sum(self, i , idx):
        s = 0
        while i > 0:
            s += self.bit[idx][i]
            i -= i & -i
        return s

    def sum(self, l, r, idx):
        return self._sum(l, idx) - self._sum(r, idx)

n = int(input())
s = input()
q = int(input())
bit = BIT(n)
for i in range(n):
    bit.add( i, 1, ord(s[i])-97)
for i in range(q):
    q_type, fr, to = map(str,input().split())
    if q_type == "1":
        bit.add(int(fr)-1,1,ord(to)-97)
        bit.add(int(fr)-1,-1,ord(s[int(fr)-1])-97)
    else:
        tmp = 0
        for j in range(26):
            if bit.sum(int(fr)-1,int(to),j):
                tmp += 1
        print(tmp)

Submission status: Wrong Answer

Solution code:
N = int(input())
s = input()
S = []
for k in range(N):
  S.append(s[k])
Q = int(input())
a = ord('a')
alpha = [[0 for _ in range(26)] for _ in range(N)]
alpha[0][ord(S[0])-a] = 1
for k in range(1, N):
  alpha[k] = [] + alpha[k-1]
  alpha[k][ord(S[k])-a] += 1
 
substitute = []
for k in range(Q):
  s,t,u = map(str, input().split())
  if s == '1':
    i = int(t) -1
    c = u
    substitute.append([i, c])
 
  if s == '2':
    l = int(t) -1
    r = int(u) -1
    count = [0 for _ in range(26)]
    for item in substitute:
      if l<=item[0]<=r:
        count[ord(S[item[0]])-a] -= 1
        count[ord(item[1]) - a] += 1 
    ans = 0
    if l == 0:
      for k in range(26):
        if alpha[r][k] + count[k] > 0:
          ans += 1
    else:
      for k in range(26):
        if alpha[r][k] - alpha[l-1][k] + count[k] > 0:
          ans += 1      
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
s = input()
S = []
for k in range(N):
  S.append(s[k])
Q = int(input())
a = ord('a')
alpha = [[] for _ in range(ord('z') - a + 1)]
for k in range(N):
  alpha[ord(S[k])- a].append(k)

for k in range(Q):
  s,t,u = map(str, input().split())
  if s == '1':
    i = int(t) -1
    c = u
    if S[i] != c:
      del alpha[ord(S[i])-a][alpha[ord(S[i])-a].index(i)]
      for j in range(len(alpha[ord(c)-a])):
        if alpha[ord(c)-a][j] > i:
          alpha[ord(c)-a] = alpha[ord(c)-a][:j] + [i] + alpha[ord(c)-a][j:]
          break
      else:
        alpha[ord(c)-a].append(i)
      if len(alpha[ord(c)-a]) == 0:
        alpha[ord(c)-a].append(i)
      S[i] = c

  if s == '2':
    l = int(t) -1
    r = int(u) -1
    ans = 0
    for j in range(len(alpha)):
      if len(alpha[j]) == 1:
        if l <= alpha[j][0] <= r:
          ans += 1
      elif len(alpha[j]) > 1:
        if r < alpha[j][0] or alpha[j][-1] < l:
          break
        else:
          ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
s = input()
S = []
for k in range(N):
  S.append(s[k])
Q = int(input())
a = ord('a')
alpha = [[] for _ in range(ord('z') - a + 1)]
for k in range(N):
  alpha[ord(S[k])- a].append(k)

for k in range(Q):
  s,t,u = map(str, input().split())
  if s == '1':
    i = int(t) -1
    c = u
    if S[i-1] != c:
      del alpha[ord(S[i])-a][alpha[ord(S[i])-a].index(i)]
      for j in range(len(alpha[ord(c)-a])):
        if alpha[ord(c)-a][j] > i:
          alpha[ord(c)-a] = alpha[ord(c)-a][:j] + [i] + alpha[ord(c)-a][j:]
          break
      else:
        alpha[ord(c)-a].append(i)
      if len(alpha[ord(c)-a]) == 0:
        alpha[ord(c)-a].append(i)
      S[i] = c
  if s == '2':
    l = int(t) -1
    r = int(u) -1
    ans = 0
    for j in range(len(alpha)):
      if len(alpha[j]) == 1:
        if l <= alpha[j][0] <= r:
          ans += 1
      elif len(alpha[j]) > 1:
        if r < alpha[j][0] or alpha[j][-1] < l:
          break
        else:
          ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
from collections import Counter, deque
from random import random
class Node:
        def __init__(self,value:int=-1):
            self.left = None
            self.right = None
            self.value = value
            self.priority = random()
            self.count_partial = 1
            self.sum_partial = value
class Treap:
    
    #Node [left, right, key, value, priority, num_partial, sum_partial]
    def __init__(self):
        self.root = None

    def update(self, node):
        if node.left is None:
            left_count = 0
            left_sum = 0
        else:
            left_count = node.left.count_partial
            left_sum = node.left.sum_partial
        if node.right is None:
            right_count = 0
            right_sum = 0
        else:
            right_count = node.right.count_partial
            right_sum = node.right.sum_partial

        node.count_partial = left_count + right_count + 1
        node.sum_partial = left_sum + right_sum + node.value
        return node

    def merge(self, left :Node, right:Node):
        if left is None or right is None:
            return left if right is None else right

        if left.priority > right.priority:
            left.right = self.merge(left.right,right)
            return self.update(left)
        else:
            right.left = self.merge(left,right.left)
            return self.update(right)


    def node_size(self, node:Node):
        return 0 if node is None else node.count_partial
    
    def node_key(self, node:None):
        return -1 if node is None else node.key

    #指定された場所のノードは右の木に含まれる

    def split(self, node:Node, key:int, level=0):
        if node is None:
            return (None,None)

        if key <= self.node_size(node.left):
            left,right = self.split(node.left, key,level+1)
            node.left = right
            return left, self.update(node)
        else:
            left,right = self.split(node.right, key - self.node_size(node.left) - 1,level+1)
            node.right = left
            return self.update(node),right 
    def split(self, node:None, value):
        if node is None:
            return None,None
        if value <= node.value:
            left,right = self.split(node.left, value)
            node.left = right
            return left, self.update(node)
        else:
            left,right = self.split(node.right, value)
            node.right = left
            return self.update(node),right

    
    def insert(self, pos:int,value:int =-1):
        value = value if value > 0 else pos
        left, right = self.split(self.root, pos)
        new_node = Node(value)
        self.root = self.merge(self.merge(left,new_node),right)
    
    def erase(self, pos:int):
        middle,right = self.split(self.root, pos+1)
        left,middle = self.split(middle, pos)
        self.root = self.merge(left,right)

        

    def printTree(self, node=None, level=0):
        node = self.root if node is None else node
        if node is None:
            print('level=',level,'root is None')
            return
        else:
            print('level=',level,'v=',node.value,'c=',node.count_partial, 'p=',node.priority)
        if node.left is not None:
            self.printTree(node.left,level+1)
        
        if node.right is not None:
            self.printTree(node.right,level+1)
        
    

    def search(self, pos):
        #return self.search_recursively(pos,self.root)
        v = self.root
        while v:
            left_count = self.node_size(v.left)
            if pos < left_count:
                v = v.left
            elif pos == left_count:
                return v.value
            else:
                v = v.right
                pos -= left_count + 1
        return -1

    def search2(self, value):
        v = self.root
        upper = 10**18
        while v:

            if value == v.value:
                return value

            elif value < v.value:
                upper = v.value
                v = v.left
            else:
                v = v.right
        return upper

    def search_recursively(self, pos, node):
        if node is None:
            return -1
        num_left = 0 if node.left is None else node.left.count_partial
        if num_left + 1 == pos:
            return node.value
        if pos <= num_left:
            return self.search_recursively(pos, node.left)
        else:
            return self.search_recursively(pos - num_left - 1, node.right)
        


    
                










def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    S = list(input())


    trees = []
    for i in range(26):
        trees.append(Treap())
    

    for i,c in enumerate(S):
        trees[ord(c)-ord('a')].insert(i)
    
    Q = int(input())
    out = []
    for _ in range(Q):
        q1,q2,q3 = input().split()
        if int(q1) == 1:
            iq = int(q2)-1
            before = S[iq]
            after = q3
            S[iq] = after
            trees[ord(before)-ord('a')].erase(iq)
            trees[ord(after)-ord('a')].insert(iq)

        else:
            l,r = int(q2)-1,int(q3)-1
            count = 0
            for i in range(26):
                if trees[i].search2(l) <= r:
                    print(l,r,trees[i].search2(l))
                    count += 1
            out.append(count)
    print('\n'.join(map(str,out)))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# return the maximal range b, e such that l <= ary[b:e] <= r
def max_range(ary, l, r):
    glb = greatest_lower_bound(ary, l-1) + 1
    lub = least_upper_bound(ary, r+1)
    return glb, lub


# return greatest i such that ary[i] <= q or -1
# if not exists
def greatest_lower_bound(ary, q):
    b, e = -1, len(ary) - 1
    while b < e:
        m = e - (e - b) // 2
        if ary[m] > q:
            e = m - 1
        else:
            b = m
    return b

# return smallest i such that ary[i] >= q or len(ary)
# if not exists
def least_upper_bound(ary, q):
    b, e = 0, len(ary)
    while b < e:
        m = b + (e - b) // 2
        if ary[m] < q:
            b = m + 1
        else:
            e = m
    return e


def is_sorted(ary):
    return all(ary[i] <= ary[i+1] for i in range(len(ary) - 1))

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

    ai = ord('a')
    # locs[i] = set(p1, p2, ...)
    # the i'th letter of the alphabet occurs at s[p1], s[p2], ...
    locs = [[] for _ in range(26)]

    for i, c in enumerate(s):
        ci = ord(c) - ai
        locs[ci].append(i)

    for ci in range(26):
        locs[ci].sort()

    for _ in range(q):
        t, v1, v2 = input().split()
        if t == '1':
            i = int(v1) - 1
            c_old = ord(s[i]) - ai
            c_new = ord(v2) - ai
            old_ind = greatest_lower_bound(locs[c_old], i)
            new_ind = greatest_lower_bound(locs[c_new], i)
            old_val = locs[c_old].pop(old_ind)
            assert old_val == i
            locs[c_new].insert(new_ind + 1, i)
            # assert is_sorted(locs[c_new])

        elif t == '2':
            l, r = int(v1), int(v2)
            # count number of different characters of each letter in s[l:r+1]
            num_dif_chars = 0
            for ci in range(26):
                lb, ub = max_range(locs[ci], l, r)
                # print('ranges', locs[ci], locs[ci][lb:ub], l, r)
                if lb < ub:
                    num_dif_chars += 1

            print(num_dif_chars)