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:
"""SegTree, bitで集合を管理する

Returns:
    [type]: [description]
"""
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)

from operator import or_


class SegTree:
    """ノードで集合をもつ
    """
    def __init__(self, N, segfunc, ide, initial_list=None):

        self.ide = ide
        self.segfunc = segfunc

        # 簡単のために要素数を2のべき乗にしておく
        _n = N
        self.n = 1
        while (self.n < _n):
            self.n = self.n * 2

        self.tree = [self.ide for _ in range(2 * self.n - 1)]

        if initial_list is not None:
            for i, v in enumerate(initial_list):
                self.update(i, v)

    def update(self, i, x):
        i = i + self.n - 1
        self.tree[i] = x

        # 親を更新
        while (i > 0):
            i = (i - 1) // 2
            l = self.tree[i * 2 + 1]
            r = self.tree[i * 2 + 2]
            self.tree[i] = self.segfunc(l, r)

    def query(
        self,
        l,
        r,  # exclusive
    ):
        l += (self.n - 1)
        r += (self.n - 1)
        res = self.ide
        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])
                r -= 1

            l = l // 2
            r = r // 2

        return res


def resolve():
    N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    Q = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ

    # N, D = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # h_list = [int(x) for x in sys.stdin.readline().split()]  # 複数int

    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    # v_list = [int(sys.stdin.readline().split()[0]) for _ in range(N)]
    grid = [[x for x in sys.stdin.readline().split()]
            for _ in range(Q)]  # int grid

    seg = SegTree(N, or_, 0, [1 << ord(c) - 97 for c in S])

    for _type, a, b in grid:
        if _type == '1':
            a = int(a) - 1
            bit = 1 << (ord(b) - 97)
            seg.update(a, bit)

        else:
            a = int(a) - 1
            b = int(b) - 1
            ret = seg.query(a, b + 1)
            print(bin(ret)[2:].count('1'))


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7"""
        output = """3
1
5"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7"""
        output = """3
1
5"""
        self.assertIO(input, output)

Submission status: Wrong Answer

Solution code:
import collections

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

print(S)

Query = []
for i in range(Q):
    Query.append(input().split())
    Query[i][0] = int(Query[i][0])
    Query[i][1] = int(Query[i][1]) - 1
    if Query[i][0] is 2:
        Query[i][2] = int(Query[i][2])

for Q_temp in Query:
    if Q_temp[0] is 1:
        S[Q_temp[1]] = Q_temp[2]
    else:
        output = collections.Counter(S[Q_temp[1]:Q_temp[2]])
        print(len(output))

Submission status: Wrong Answer

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

class BIT:
  # [1,n]に値が入ってる1-indexであることに注意
  def __init__(self,size):
    self.data = [0]*(size+1)
    self.size = size
  
  # [1,n]までの総和
  def sum(self,n):
    res = 0
    while n > 0:
      res += self.data[n]
      n -= n & -n
    return res
  
  def add(self,k,x):
    while k < self.size + 1:
      self.data[k] += x
      k += k & -k

n = int(input())
bits = [BIT(n) for i in range(30)]
S = input()
for i,si in enumerate(S):
  k = ord(si)-ord("a")
  bits[k].add(i+1,1)
Q = int(input())
for _ in range(Q):
  typo,a,b = input().split()
  if typo == "1":
    k = ord(b)-ord("a")
    bits[k].add(int(a),1)
  else:
    out = 0
    for bit in bits:
      if bit.sum(int(b))-bit.sum(int(a)-1) > 0:
        out += 1
    print(out)

Submission status: Wrong Answer

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

class BIT:
  # [1,n]に値が入ってる1-indexであることに注意
  def __init__(self,size):
    self.data = [0]*(size+1)
    self.size = size
  
  # [1,n]までの総和
  def sum(self,n):
    res = 0
    while n > 0:
      res += self.data[n]
      n -= n & -n
    return res
  
  def add(self,k,x):
    while k < self.size + 1:
      self.data[k] += x
      k += k & -k

n = int(input())
bits = [BIT(n) for i in range(30)]
S = input()
for i,si in enumerate(S):
  k = ord(si)-ord("a")
  bits[k].add(i+1,1)
Q = int(input())
for _ in range(Q):
  typo,a,b = input().split()
  if typo == "1":
    k = ord(b)-ord("a")
    bits[k].add(int(a),1)
  else:
    out = 0
    for bit in bits:
      if bit.sum(int(b))-bit.sum(int(a)) > 0:
        out += 1
    print(out)

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline


class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [[0] * (n + 1) for _ in range(26)]

    def build_tree(self, s):
        for idx, i in enumerate(s[1:], 1):
            for j in range(26):
                tmp = idx - (idx & (-idx))
                if tmp == 0:
                    self.tree[j][idx] = bit.bit_query(j, idx - 1)
                else:
                    self.tree[j][idx] = self.tree[j][tmp + 1]
                if j == i:
                    self.tree[j][idx] += 1

    def bit_query(self, character, idx):
        if idx == 0:
            return 0
        sum_of_query = 0
        while idx > 0:
            sum_of_query += self.tree[character][idx]
            idx -= idx & (-idx)
        return sum_of_query

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


N = int(input())
S = [i - 97 for i in map(ord, list(input()))]
S = [-1] + S
Q, *query = map(str, read().split())
bit = BIT(N)
bit.build_tree(S)
for a, b, c in zip(*[iter(query)] * 3):
    b = int(b)
    if a == '1':
        c = ord(c) - 97
        if S[b] == c:
            continue
        bit.update(c, b, 1)
        bit.update(S[b], b, -1)
        S[b] = c
    else:
        c = int(c)
        print(sum(1 for i in range(26) if bit.bit_query(i, c) - bit.bit_query(i, b - 1) > 0))

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import heapq
import bisect
n=i1()
s=list(input())
q=i1()
t=[[] for i in range(26)]
for i in range(n):
  heapq.heappush(t[ord(s[i])-ord("a")],i)
while q:
 [ty,i,c]=[j for j in input().split()]
 ty=int(ty)
 i=int(i)
 if ty==1:
   t[ord(s[i-1])-ord("a")].remove(i-1)
   s[i-1]=c
   heapq.heappush(t[ord(c)-ord("a")],i-1)
 else:
   c=int(c)
   x=0
   for j in range(26):
     y=bisect.bisect_left(t[j],i-1)
     if 0<=y<=len(t[j])-1 and t[j][bisect.bisect_left(t[j],i-1)]<=c-1:
        x+=1
   print(x)
 q-=1

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import math
import sys
sys.setrecursionlimit(10**6)

n=i1()
s=input()
q=i1()

n=2**(int(math.log2(n))+1)

t=[set([]) for i in range(2*n-1)]

def ud(i,x):
  i+=n-1
  t[i]=x
  while i:
    i=(i-1)//2
    t[i]=t[i*2+1] | t[i*2+2]

def qr(a,b,k,l,r):
  if r<=a or b<=l:
     if b==l:
         return t[k]
     return set([])
  elif a<=l and r<=b:
     return t[k]
  else:
     return qr(a,b,k*2+1,l,(l+r)//2) | qr(a,b,k*2+2,(l+r)//2,r)

for i in range(len(s)):
  ud(i,set([s[i]]))

while q:
 [ty,i,c]=[i for i in input().split()]
 ty=int(ty)
 i=int(i)
 if ty==1:
   ud(i-1,set([c]))
 else:
   c=int(c)
   if i==c:
     print(1)
   else:
     print(len(qr(i-1,c-1,0,0,n)))
   
 q-=1

Submission status: Wrong Answer

Solution code:
def main():
    import numpy as np
    from functools import reduce
    import sys
    buf = sys.stdin.buffer

    class SegmentTree:
        def __init__(self, target, no_effect):
            target_size = len(target)
            leaves_size = 1
            while leaves_size < target_size:
                leaves_size *= 2
            self.tree_size = leaves_size * 2 - 1
            self.tree = np.array([no_effect] * self.tree_size, dtype=np.int64)
            self.no_effect = no_effect
            self.initialize_tree(target)

        @classmethod
        def initialize_func(cls, value):
            return 1 << (ord(value) - 97)

        @classmethod
        def merge_func(cls, a, b):
            return a | b

        def merge_child_data(self, node):
            child1 = node * 2 + 1
            child2 = node * 2 + 2
            merged = self.merge_func(*self.tree[[child1, child2]])
            return merged

        def initialize_tree(self, target):
            initial_leaf = self.tree_size // 2
            leaves = np.arange(initial_leaf, initial_leaf+len(target), dtype=np.int64)
            self.tree[leaves] = np.array([self.initialize_func(chr) for chr in target], dtype=np.int64)

            self.tree[np.arange(initial_leaf-1, -1, -1)] = np.array([self.merge_child_data(parent) for parent in range(initial_leaf-1, -1, -1)], dtype=np.int64)

        def update(self, new_value, index):
            leaf = self.tree_size//2 + index
            new_data = self.initialize_func(new_value)
            if self.tree[leaf] == new_data:
                return
            self.tree[leaf] = new_data

            parent = (leaf-1) // 2
            while parent >= 0:
                new_data = self.merge_child_data(parent)
                if self.tree[parent] == new_data:
                    break
                self.tree[parent] = new_data
                parent = (parent-1) // 2

        def resolve_query(self, _from, to):
            def gen(_from, to):
                left, right = _from + self.tree_size//2, to + self.tree_size//2
                while left <= right:
                    yield left
                    yield right
                    left //= 2
                    right = right//2 - 1
            
            indexes = [index for index in gen(_from, to)]
            result = reduce(self.merge_func, self.tree[indexes])
            
            return bin(result).count('1')

    n, S, _, *queries = buf.read().split()
    S = S.decode()
    seg_tree = SegmentTree(target=S, no_effect=0)

    for type, a, b in zip(*[iter(queries)]*3):
        if type == b'1':
            index, new = int(a)-1, b
            seg_tree.update(new, index)

        elif type == b'2':
            _from, to = int(a)-1, int(b)-1
            print(seg_tree.resolve_query(_from, to))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import numpy as np
    from functools import reduce
    import sys
    buf = sys.stdin.buffer

    class SegmentTree:
        def __init__(self, target, no_effect):
            target_size = len(target)
            leaves_size = 1
            while leaves_size < target_size:
                leaves_size *= 2
            self.tree_size = leaves_size * 2 - 1
            self.tree = np.array([no_effect] * self.tree_size, dtype=np.int64)
            self.no_effect = no_effect
            self.initialize_tree(target)

        @classmethod
        def initialize_func(cls, value):
            return 1 << (ord(value) - 97)

        @classmethod
        def merge_func(cls, a, b):
            return a | b

        def merge_child_data(self, node):
            child1 = node * 2 + 1
            child2 = node * 2 + 2
            merged = self.merge_func(*self.tree[[child1, child2]])
            return merged

        def initialize_tree(self, target):
            initial_leaf = self.tree_size // 2
            leaves = np.arange(initial_leaf, initial_leaf+len(target))
            self.tree[leaves] = np.array([self.initialize_func(chr) for chr in target])

            self.tree[np.arange(initial_leaf-1, -1, -1)] = np.array([self.merge_child_data(parent) for parent in np.arange(initial_leaf-1, -1, -1)])

        def update(self, new_value, index):
            leaf = self.tree_size//2 + index
            new_data = self.initialize_func(new_value)
            if self.tree[leaf] == new_data:
                return
            self.tree[leaf] = new_data

            parent = (leaf-1) // 2
            while parent >= 0:
                new_data = self.merge_child_data(parent)
                if self.tree[parent] == new_data:
                    break
                self.tree[parent] = new_data
                parent = (parent-1) // 2

        def resolve_query(self, _from, to):
            def gen(_from, to):
                left, right = _from + self.tree_size//2, to + self.tree_size//2
                while left <= right:
                    yield left
                    yield right
                    left //= 2
                    right = right//2 - 1
            
            indexes = np.array([index for index in gen(_from, to)])
            result = reduce(self.merge_func, self.tree[indexes])
            
            return bin(result).count('1')

    n, S, _, *queries = buf.read().split()
    S = S.decode()
    seg_tree = SegmentTree(target=S, no_effect=0)

    for type, a, b in zip(*[iter(queries)]*3):
        if type == b'1':
            index, new = int(a)-1, b
            seg_tree.update(new, index)

        elif type == b'2':
            _from, to = int(a)-1, int(b)-1
            print(seg_tree.resolve_query(_from, to))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# どの文字を持っているかを二進数で1000101010...と表す
# or で足していく
class SegmentTree:
  arr=None
  tree=None
  n=0
  # 結果に影響を与えないdefault value
  DEF=0

  def __init__(self,arr):
  #  print("arr",arr)
    self.arr=arr
    size=len(arr)
    # n階層目は2**(n-1)要素
    self.n=1
    while self.n<size:
      self.n*=2
    self.tree=[self.DEF]*(2*self.n-1)
    # 親=(n-1)//2
    # 子=2*n+1,2*n+2
    # 最下階層の要素を埋めていく
    for i in range(size):
    #  print(arr[i])
      self.tree[i+self.n-1]=arr[i]
    for i in range(self.n-2,-1,-1):
      self.tree[i]=self.__choose__(self.tree[2*i+1],self.tree[2*i+2])
    
    
  # 区間からの代表値の選び方を定義する（最小値を選ぶ場合はminなど）
  def __choose__(self,a,b):
    #print("a",a,"b",b)
    return a | b
  
  # 添字xをvalで更新する
  def update(self,x,val):
    x+=len(self.arr)-1
    
    self.tree[x]=val
    while x>0:
      x=(x-1)//2
      self.tree[x]=self.__choose__(self.tree[2*x+1],self.tree[2*x+2])
      
  # 対象区間[a,b)の値を求めるクエリ (bは含まないので注意)
  # k:自分がいるノードのindex
  # [l,r):検査する区間
  def get_val(self,a,b,k=0,l=0,r=-1):
    # 最初に呼び出されたときは対象区間が[0,N)
    if r<0:
      r=self.n
      
    # 要求区間と対象区間が交わらない
    if r<=a or b<=l:
      return self.DEF
    
    # 要求区間が対象区間を完全に満たす->対象区間を計算に使用する
    if a<=l and r<=b:
      return self.tree[k]
    
    # 要求区間が対象区間の一部を満たす->子を探索
    ll=self.get_val(a,b,2*k+1,l,(l+r)//2)
    rr=self.get_val(a,b,2*k+2,(l+r)//2,r)
    
    return self.__choose__(ll,rr)
    
  def show(self):
    print(list(map(bin,self.tree)))
    print(self.tree)
    
base=ord("a")
ALPHA="abcdefghijklmnopqrstuvwxyz"
def change_alpha_to_num(c):
  if c not in ALPHA:
    return 0
  # print("c",c,"ord(c)",ord(c),"base",base)
  return 1<<(ord(c)-base)

import sys
readline=sys.stdin.readline

N=int(readline())
S=readline()
Sarr=list(map(change_alpha_to_num,list(S)))
ST=SegmentTree(Sarr)
# ST.show()
Q=int(readline())
for i in range(Q):
  q=list(readline().split())
  if q[0]=="1":
    #print("q",q)
    i,c=int(q[1])-1,q[2]
    ST.update(i,change_alpha_to_num(c))
  elif q[0]=="2":
    l,r=int(q[1])-1,int(q[2])-1
    print(bin(ST.get_val(l,r+1))[2:].count("1"))

Submission status: Wrong Answer

Solution code:
# a~zのSegmentTreeを持つ
class SegmentTree:
  arr=None
  tree=None
  n=0
  # 結果に影響を与えないdefault value
  DEF=0
  def __init__(self,arr):
    self.arr=arr
    size=len(arr)
    # n階層目は2**(n-1)要素
    self.n=1
    while self.n<size:
      self.n*=2
    self.tree=[self.DEF]*(2*self.n-1)
    # 親=(n-1)//2
    # 子=2*n+1,2*n+2
    # 最下階層の要素を埋めていく
    for i in range(size):
      self.tree[i+self.n-1]=arr[i]
    for i in range(self.n-2,-1,-1):
      self.tree[i]=self.__choose__(self.tree[2*i+1],self.tree[2*i+2])
    
  # 区間からの代表値の選び方を定義する（最小値を選ぶ場合はminなど）
  def __choose__(self,a,b):
    return a|b
  
  # 添字xをvalで更新する
  def update(self,x,val):
    x+=len(self.arr)-1
    
    self.tree[x]=val
    while x>0:
      x=(x-1)//2
      self.tree[x]=self.__choose__(self.tree[2*x+1],self.tree[2*x+2])
      
  # 対象区間[a,b)の値を求めるクエリ (bは含まないので注意)
  # k:自分がいるノードのindex
  # [l,r):検査する区間
  def get_val(self,a,b,k=0,l=0,r=-1):
    # 最初に呼び出されたときは対象区間が[0,N)
    if r<0:
      r=self.n
      
    # 要求区間と対象区間が交わらない
    if r<=a or b<=l:
      return self.DEF
    
    # 要求区間が対象区間を完全に満たす->対象区間を計算に使用する
    if a<=l and r<=b:
      return self.tree[k]
    
    # 要求区間が対象区間の一部を満たす->子を探索
    ll=self.get_val(a,b,2*k+1,l,(l+r)//2)
    rr=self.get_val(a,b,2*k+2,(l+r)//2,r)
    
    return self.__choose__(ll,rr)
    
  def show(self):
    print(self.tree)
    
import sys
readline=sys.stdin.readline

N=int(readline())
S=readline()

#print(S)
dic={}
for i in range(ord("a"),ord("z")+1):
  target=chr(i)
#   print("target",target)
#  print("target",target)
  f=lambda x:(x==target)*1
  chrs=list(map(f,list(S)))
#  print("target",target,"chrs",chrs)
  dic[target]=SegmentTree(chrs)
  


Q=int(readline())
for _ in range(Q):
  q=list(readline().split())
  if q[0]=="1":
    i,c=int(q[1])-1,q[2]
    cur=""
    for s in range(ord("a"),ord("z")+1):
      tar=chr(s)
      if dic[tar].get_val(i,i+1)==1:
        cur=tar
        break
    if cur!="":
      dic[cur].update(i,0)
    dic[c].update(i,1)
  elif q[0]=="2":
#    print("q",q)
    l,r=int(q[1])-1,int(q[2])-1
    ans=0
    for c in range(ord("a"),ord("z")+1):
      tar=chr(c)
      ans+=dic[tar].get_val(l,r+1)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


class SegmentTree:
    def __init__(self, A):
        self.n = 2**(len(A)-1).bit_length()
        self.identity = set()
        self.seg = [self.identity] * (2 * self.n)
        
        for i, a in enumerate(A):
            self.seg[self.n-1+i] = set(a)
        for i in range(self.n-2,-1,-1):
            self.seg[i] = self.seg[2*i+1] | self.seg[2*i+2]

            
    def update(self, k, a):
        k += self.n - 1
        self.seg[k] = set(a)
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.seg[k*2+1] | self.seg[k*2+2]

            
    def query(self, a, b):
        if b == a:
        	return 1
        a += self.n - 1
        b += self.n - 2
        res = self.identity
        while b - a > 1:
            if a & 1 == 0:
                res = res | self.seg[a]
            if b & 1 == 1:
                res = res | self.seg[b]
                b -= 1
            a = a // 2
            b = (b - 1) // 2
        if a == b:
            res = res | self.seg[a]
        else:
            res = res | self.seg[a] | self.seg[b]
        
        return len(res)


def main():
    N = int(readline())
    s = readline().strip()
    seg = SegmentTree(list(s))
    print(seg.seg)

    Q = int(readline())
    for _ in range(Q):
        q, a, b = map(str, readline().split())
        if q == "1":
            seg.update(int(a)-1, b)
        else:
            print(seg.query(int(a)-1, int(b)))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# SegmentTreeで、a～zについて要素の個数を管理
# setで持つ
class SegmentTree:
  arr=None
  tree=None
  n=0
  # 結果に影響を与えないdefault value
  DEF=set("Z")
  def __init__(self,arr):
    self.arr=arr
    size=len(arr)
    # n階層目は2**(n-1)要素
    self.n=1
    while self.n<size:
      self.n*=2
    self.tree=[self.DEF]*(2*self.n-1)
    # 親=(n-1)//2
    # 子=2*n+1,2*n+2
    # 最下階層の要素を埋めていく
    for i in range(size):
      self.tree[i+self.n-1]=set(arr[i])
    for i in range(self.n-2,-1,-1):
      self.tree[i]=self.__choose__(self.tree[2*i+1],self.tree[2*i+2])
    
  # 区間からの代表値の選び方を定義する（最小値を選ぶ場合はminなど）
  def __choose__(self,a,b):
    # print("a",a,"b",b)
    return a|b
  
  # 添字xをvalで更新する
  def update(self,x,val):
    x+=len(self.arr)-1
    
    self.tree[x]=set(val)
    while x>0:
      x=(x-1)//2
      self.tree[x]=self.__choose__(self.tree[2*x+1],self.tree[2*x+2])
      
  # 対象区間[a,b)の値を求めるクエリ (bは含まないので注意)
  # k:自分がいるノードのindex
  # [l,r):検査する区間
  def get_val(self,a,b,k=0,l=0,r=-1):
    # 最初に呼び出されたときは対象区間が[0,N)
    if r<0:
      r=self.n
      
    # 要求区間と対象区間が交わらない
    if r<=a or b<=l:
      return self.DEF
    
    # 要求区間が対象区間を完全に満たす->対象区間を計算に使用する
    if a<=l and r<=b:
      return self.tree[k]
    
    # 要求区間が対象区間の一部を満たす->子を探索
    ll=self.get_val(a,b,2*k+1,l,(l+r)//2)
    rr=self.get_val(a,b,2*k+2,(l+r)//2,r)
    
    return self.__choose__(ll,rr)
    
  def show(self):
    print(self.tree)
    
import sys
readline=sys.stdin.readline

N=int(readline())
S=readline().rstrip()
ST=SegmentTree(list(S))
Q=int(readline())
for i in range(Q):
  q=list(readline().split())
  if q[0]=="1":
    i,c=int(q[1]),q[2]
    ST.update(i,c)
  elif q[0]=="2":
    L,R=int(q[1])-1,int(q[2])-1
    print(len(ST.get_val(L,R+1)-set("Z")))

Submission status: Wrong Answer

Solution code:
#13:19
n = int(input())
s = input()
t = []
for i in range(n):
  t.append(ord(s[i])-ord('a'))
q = int(input())
scale = 19
seg = [[0 for _ in range(2**(scale+1))] for _ in range(26)]
for i in range(n):
  tmp = int(i) + 2 ** scale
  x = t[i]
  while tmp != 0:
    seg[x][tmp] += 1
    tmp //= 2
#print(seg)
for _ in range(q):
  d,a,b = input().split()
  if d == '1':
    b = ord(b) - ord('a')
    tmp = int(a) - 1
    c = t[tmp]
    tmp += 2**scale
    while tmp != 0:
      seg[c][tmp] -= 1
      tmp //= 2
    tmp = int(a) - 1
    t[tmp] = b
    tmp += 2**scale
    while tmp != 0:
      seg[b][tmp] += 1
      tmp //= 2
  else:
    a = int(a) - 2
    b = int(b) - 1
    ans = 0
    for d in range(26):
      l = 0
      r = 0
      if a == -1:
        l = 0
      else:
        tmp = a + 2**scale
        l += seg[d][tmp]
        while tmp != 1:
          if tmp % 2 == 1:
            l += seg[d][tmp-1]
          tmp //= 2
      tmp = b + 2**scale
      r += seg[d][tmp]
      tmp = tmp // 2
      while tmp != 1:
        if tmp % 2 == 1:
          r += seg[d][tmp-1]
        tmp //= 2
      if r > l:
        ans += 1
      #print(d,r,l)
    print(ans)
#print(t)

Submission status: Wrong Answer

Solution code:

class SegmentTree:
    def __init__(self, base_array,n , default_value = 0, segfunc = lambda a, b: a + b): #元配列、大きさ、デフォルト値
        self._num = 2 ** (n - 1).bit_length()
        self._seg = [default_value] * 2 * self._num
        self._segfunc = segfunc
        self._ide_ele = default_value
        for i in range(n):
            self._seg[i + self._num - 1] = base_array[i]
        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] = self._segfunc(self._seg[k * 2 + 1], self._seg[k * 2 + 2])


    def query(self, p, q):
        if q <= p:
            return self._ide_ele
        p += self._num - 1
        q += self._num - 2
        res = self._ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = self._segfunc(res, self._seg[p])
            if q & 1 == 1:
                res = self._segfunc(res, self._seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self._segfunc(res, self._seg[p])
        else:
            res = self._segfunc(self._segfunc(res, self._seg[p]), self._seg[q])
        return res

def main():
    N = int(input())
    S = [c for c in input()]
    M = int(input())

    A = [0 for i in range(N)]

    for i, c in enumerate(S):
        A[i] = 1 << ord(c) - ord('a')

    print(A)

    st = SegmentTree(A, N, 0, lambda a, b: a | b)

    for i in range(M):
        p, a, b = input().split()
        a  = int(a) - 1
        b = int(b) - 1 if p == '2' else b
        if p == '1':
            st.update(a, 1 << ord(b) - ord('a'))

        if p == '2':
            s = st.query(a, b + 1)
            print(bin(s).count('1'))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def solve(N, S, Q, queries):
    def update(i, c):
        values[i] = c
        s = (i // sN) * sN
        for v in values[s:s+sN]:
            buckets[i//sN] |= 1 << v

    def count(l, r):
        res = 0
        for i in range(sN):
            ll = i * sN
            rr = ll + sN
            if r <= ll or rr <= l:
                continue
            if l <= ll and rr <= r:
                res |= buckets[i]
            else:
                for i in range(max(l, ll), min(r, rr)):
                    res |= 1 << values[i]
        return sum(b == '1' for b in bin(res))
        
    sN = math.ceil(N ** 0.5)
    values = [ord(c)-ord('a') for c in S]
    buckets = [0] * sN
    for i, v in enumerate(values):
        buckets[i//sN] |= 1 << v
    for t, x, y in queries:
        if t == 1:
            update(int(x)-1, ord(y)-ord('a'))
        else:
            yield count(int(x)-1, int(y))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))
    S = next(tokens)
    Q = int(next(tokens))
    queries = [(int(next(tokens)), next(tokens), next(tokens)) for _ in range(Q)]
    for result in solve(N, S, Q, queries):
        print(result)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

class SegmentTree:
    def __init__(self, base_array,n , default_value = 0, segfunc = lambda a, b: a + b): #元配列、大きさ、デフォルト値
        self._num = 2 ** (n - 1).bit_length()
        self._seg = [default_value] * 2 * self._num
        self._segfunc = segfunc
        self._ide_ele = default_value
        for i in range(n):
            self._seg[i + self._num - 1] = base_array[i]
        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] = self._segfunc(self._seg[k * 2 + 1], self._seg[k * 2 + 2])


    def query(self, p, q):
        if q <= p:
            return self._ide_ele
        p += self._num - 1
        q += self._num - 2
        res = self._ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = self._segfunc(res, self._seg[p])
            if q & 1 == 1:
                res = self._segfunc(res, self._seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self._segfunc(res, self._seg[p])
        else:
            res = self._segfunc(self._segfunc(res, self._seg[p]), self._seg[q])
        return res

def main():
    N = int(input())
    S = [c for c in input()]
    M = int(input())
    dic = {c: i for i, c in enumerate('abcdefghijklmnopqrstuvwxyz')}
    Arrays = [[0 for j in range(N)] for i in range(26)]

    for i, c in enumerate(S):
        Arrays[dic[c]][i] = 1

    segs = []
    for i in range(26):
        segs.append(SegmentTree(Arrays[i], N))

    for i in range(M):
        p, a, b = input().split()
        a  = int(a) - 1
        b = int(b) - 1 if p == '2' else b
        if p == '1':
            before = S[a]
            segs[dic[before]].update(a, 0)
            segs[dic[b]].update(a, 1)

        if p == '2':
            s = 0
            for j in range(26):
                if segs[j].query(a, b + 1) > 0:
                    s += 1
            print(s)


if __name__ == '__main__':
    main()