Problem:


Score : 500 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters.

Process Q queries of the following two types:

Type 1: change the i_q-th character of S to c_q. (Do nothing if the i_q-th character is already c_q.)

Type 2: answer the number of different characters occurring in the substring of S between the l_q-th and r_q-th characters (inclusive).

Constraints

N, Q, i_q, l_q, and r_q are integers.

S is a string consisting of lowercase English letters.

c_q is a lowercase English letter.

1 \leq N \leq 500000

1 \leq Q \leq 20000

|S| = N

1 \leq i_q \leq N

1 \leq l_q \leq r_q \leq N

There is at least one query of type 2 in each testcase.

Input

Input is given from Standard Input in the following format:

N
S
Q
Query_1
\vdots
Query_Q

Here, Query_i in the 4-th through (Q+3)-th lines is one of the following:

1 i_q c_q

2 l_q r_q

Output

For each query of type 2, print a line containing the answer.

Sample Input 1

7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7

Sample Output 1

3
1
5

In the first query, cdbb contains three kinds of letters: b , c , and d, so we print 3.

In the second query, S is modified to abcdzbd.

In the third query, a contains one kind of letter: a, so we print 1.

In the fourth query, S is modified to abcazbd.

In the fifth query, S does not change and is still abcazbd.

In the sixth query, abcazbd contains five kinds of letters: a, b, c, d, and z, so we print 5.



Sample input:
7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7


Sample output:
3
1
5

Submission status: Accepted

Solution code:
# AC: 577 msec (Python3)
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def string_to_number(a):
    return 1 << (ord(a) - 97)

class SegmentTree:
    def __init__(self, A):
        self.n = 2**(len(A)-1).bit_length()
        self.identity = 0
        self.seg = [self.identity] * (2 * self.n)
        
        for i, a in enumerate(A):
            self.seg[self.n-1+i] = string_to_number(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] = string_to_number(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 not a & 1:
                res |= self.seg[a]
            if b & 1:
                res |= self.seg[b]
                b -= 2
            a >>= 1
            b -= 1
            b >>= 1
        if a == b:
            res |= self.seg[a]
        else:
            res |= (self.seg[a] | self.seg[b])
        
        return bin(res).count("1")


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

    Q = int(readline())
    q = map(str, read().split())
    ans = []
    for t, a, b in zip(*[iter(q)]*3):
        if t == "1":
            seg.update(int(a)-1, b)
        else:
            ans.append(seg.query(int(a)-1, int(b)))
    
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 0:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


def solve():
    import sys
    from operator import add
    N = int(input())
    S = list(input())
    Q = int(input())
    Query = sys.stdin.readlines()

    a = ord('a')
    A = [[0] * N for _ in range(26)]
    for i, s in enumerate(S):
        s = ord(s) - a
        A[s][i] = 1
    seg = [SegmentTree(A[i], add, 0) for i in range(26)]

    for i in range(Q):
        t, x, y = Query[i].split()
        t = int(t)
        x = int(x) - 1
        if t == 1 and S[x] != y:
            c = S[x]
            S[x] = y
            seg[ord(c) - a].update(x, 0)
            seg[ord(y) - a].update(x, 1)
            continue
        elif t == 2:
            y = int(y) - 1
            ans = 0
            for j in range(26):
                ans += (seg[j].get(x, y + 1)) > 0
            print(ans)


solve()

Submission status: Accepted

Solution code:
import bisect

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

#アルファベットの各文字に対してからのリストを持つ辞書
alpha={chr(i):[] for i in range(97,123)}

#alpha[c]で各文字ごとに出現場所をソートして保管
for i,c in enumerate(s):
    bisect.insort(alpha[c],i+1)

for i in range(int(input())):
    p,q,r=input().split()
    if p=='1':
        q=int(q)
        b=s[q-1]
        if b!=r:
            alpha[b].pop(bisect.bisect_left(alpha[b],q))
            bisect.insort(alpha[r],q)
            s[q-1]=r
    else:
        count=0
        for l in alpha.values():
            pos=bisect.bisect_left(l,int(q))
            if pos<len(l) and l[pos]<=int(r):
                count+=1
        print(count)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    s = input()
    Q = int(input())
    t = [input().split() for _ in range(Q)]

    d = [0] * n + [1 << ord(c) - 97 for c in s]
    for i in range(n - 1, 0, -1):
        d[i] = d[i + i] | d[i - ~i]
    for q, a, b in t:
        i, s = int(a) + n - 1, 0
        if q < "2":
            d[i] = 1 << ord(b) - 97
            while i > 1:
                i //= 2
                d[i] = d[i + i] | d[i - ~i]
        else:
            j = int(b) + n
            while i < j:
                if i & 1:
                    s |= d[i]
                    i += 1
                if j & 1:
                    j -= 1
                    s |= d[j]
                i //= 2
                j //= 2
            print(bin(s).count("1"))


main()

Submission status: Accepted

Solution code:
import bisect
n=int(input())
s=list(input())
a={chr(i):[] for i in range(97,123)}
for i,c in enumerate(s):
    bisect.insort(a[c],i+1)
for i in range(int(input())):
    p,q,r=list(map(str,input().split()))
    if p=="1":
        q=int(q)
        b=s[q-1]
        if b!=r:
            a[b].pop(bisect.bisect_left(a[b],q))
            bisect.insort(a[r],q)
            s[q-1]=r
    else:
        d=0
        for l in a.values():
            g=bisect.bisect_left(l,int(q))
            if g<len(l) and l[g]<=int(r):
                d+=1
        print(d)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
#print(n,end=' n')
data=[0]*(2*n)
def upd(i,x):
  i+=n
  data[i]=x
  while i>1:
    data[i>>1]=data[i]|data[i^1]
    i>>=1
def qry(l,r):
  l+=n
  r+=n
  res=0
  while l<r:
    if l&1:
      res|=data[l]
      l+=1
    if r&1:
      r-=1
      res|=data[r]
    l>>=1
    r>>=1
  return bin(res).count('1')

for i,c in enumerate(input()[:-1],n):
  data[i]=1<<(ord(c)-ord('a'))
for i in range(n-1,0,-1):
  data[i]=data[i<<1]|data[i<<1|1]
ans=[]
for _ in range(int(input())):
  q,a,b=input().split()
  if int(q)==1:
    upd(int(a)-1,1<<(ord(b)-ord('a')))
  else:
    ans.append(qry(int(a)-1,int(b)))
print('\n'.join(map(str,ans)))

Submission status: Accepted

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


def string_to_number(a):
    return 1 << (ord(a) - 97)

class SegmentTree:
    def __init__(self, A):
        self.n = 2**(len(A)-1).bit_length()
        self.identity = 0
        self.seg = [self.identity] * (2 * self.n)
        
        for i, a in enumerate(A):
            self.seg[self.n-1+i] = string_to_number(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] = string_to_number(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 not a & 1:
                res |= self.seg[a]
            if b & 1:
                res |= self.seg[b]
                b -= 2
            a >>= 1
            b -= 1
            b >>= 1
        if a == b:
            res |= self.seg[a]
        else:
            res |= (self.seg[a] | self.seg[b])
        
        return bin(res).count("1")


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

    Q = int(readline())
    q = map(str, read().split())
    for t, a, b in zip(*[iter(q)]*3):
        if t == "1":
            seg.update(int(a)-1, b)
        else:
            print(seg.query(int(a)-1, int(b)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#1indexed
class BIT():
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n+1)

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

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += i & -i

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

bit = [BIT(n+1) for i in range(26)]
for i in range(n):
    bit[ord(s[i])-97].add(i+1, 1)


s = list(s)
for _ in range(q):
    query, a, b = input().split()
    if query == "1":
        i = int(a)
        c = ord(b)-97
        bit[c].add(i, 1)

        bit[ord(s[i-1])-97].add(i, -1)
        s[i-1] = b
    else:
        ans = 0
        for k in range(26):
            if bit[k].sum(int(b))-bit[k].sum(int(a)-1) >= 1:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
#1indexed
class BIT():
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n+1)

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

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += i & -i

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

bit = [BIT(n+1) for i in range(26)]
for i in range(n):
    bit[ord(s[i])-97].add(i+1, 1)


s = list(s)
for _ in range(q):
    query, a, b = input().split()
    if query == "1":
        i = int(a)
        c = ord(b)-97
        bit[ord(s[i-1])-97].add(i, -1)
        bit[c].add(i, 1)
        s[i-1] = b
    else:
        ans = 0
        for k in range(26):
            if bit[k].sum(int(b))-bit[k].sum(int(a)-1) >= 1:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)
import bisect

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

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 = [ c for c in input()]
q = int(input())
qqq = list(map(lambda s: s.strip().split(), sys.stdin.readlines()))

seg = segtree(n+1, lambda a,b:a|b, 0)

for i,c in enumerate(s):
    o = ord(c) - ord("a")
    seg.update(i, 2**o)
# log(chars)

for que in qqq:
    if que[0] == "1":
        target = int(que[1])-1
        o = ord(que[2]) - ord("a")
        seg.update(target, 2**o)

    else:
        left = int(que[1])-1
        right = int(que[2])-1

        x = seg.get(left, right)
        log("x", x)
        count = 0
        while x > 0:
            if x % 2 == 1:
                count += 1
            x = x//2
        print(count)

Submission status: Accepted

Solution code:
import bisect

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

alpha_map = {chr(i):[] for i in range(97,123)}
for i,c in enumerate(s):
    bisect.insort(alpha_map[c],i+1)
    
for _ in range(q):
    x,y,z = map(str,input().split())
    if int(x) == 1:
        y = int(y)
        bef = s[y-1]
        if bef == z:
            continue
        alpha_map[bef].pop(bisect.bisect_left(alpha_map[bef],y))
        bisect.insort(alpha_map[z],y)
        s[y-1] = z
    else:
        count = 0
        for i,j in alpha_map.items():
            idx = bisect.bisect_left(j,int(y))
            if idx < len(j) and j[idx] <= int(z):
                    count += 1
        print(count)

Submission status: Accepted

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 == 0:  # 奇数のとき。l += (self.n - 1)してるから
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1 == 0:
                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: Accepted

Solution code:
"""SegTree, 遅い、、、

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

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)


class SegTree:
    """ノードで集合をもつ
    
    Returns:
        [type]: [description]
    """
    def __init__(self, s):

        N = len(s)

        self.default = 0

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

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

        for i, c in enumerate(s):
            self.update(i, c)

    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] = l | r

    def query(
        self,
        query_start,
        query_end,  # exclusive
        i_parent=0,
        parent_start=0,
        parent_end=None  # exclusive
    ):
        if parent_end is None:
            parent_end = self.n
        if (query_end <= parent_start
                or parent_end <= query_start):  # クエリとレンジが重ならない
            return self.default
        elif (query_start <= parent_start
              and parent_end <= query_end):  # クエリがレンジを完全に含む
            return self.tree[i_parent]
        else:
            return self.query(query_start, query_end, 2 * i_parent + 1,
                           parent_start, (parent_start + parent_end) // 2) | \
                self.query(query_start, query_end, 2 * i_parent + 2,
                           (parent_start + parent_end) // 2, parent_end)


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([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: Accepted

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from bisect import bisect_left
def resolve():
    N = ir()
    S = list(sr())
    a = [[] for _ in range(26)]
    for i, s in enumerate(S):
        a[ord(s)-ord('a')].append(i)
    Q = ir()
    for i in range(Q):
        x, y, z = sr().split()
        if x == '1':
            y = int(y)-1
            if S[y] == z:
                continue
            u = ord(S[y])-ord('a')
            l = bisect_left(a[u], y)
            a[u].pop(l)
            v = ord(z)-ord('a')
            l = bisect_left(a[v], y)
            a[v].insert(l, y)
            S[y] = z
        else:
            y = int(y)-1
            z = int(z)-1
            ans = 0
            for i in range(26):
                l = bisect_left(a[i], y)
                if l == len(a[i]):
                    continue
                elif a[i][l] <= z:
                    ans += 1
            print(ans)
resolve()

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, data):
        # 初期値
        self.default_value = 0
        # num: n以上の最小の2のべき乗
        self.power = 2 ** (N - 1).bit_length()
        self.node = [self.default_value] * 2 * self.power
        for i in range(N):
            self.node[i + self.power - 1] = 1 << (ord(data[i]) - 97)
        for i in range(self.power - 2, -1, -1):
            self.node[i] = self.node[2 * i + 1] | self.node[2 * i + 2]

    def update(self, k, x):
        k += self.power - 1
        self.node[k] = 1 << (ord(x) - 97)
        while k:
            k = (k - 1) // 2
            self.node[k] = self.node[k * 2 + 1] | self.node[k * 2 + 2]

    def query(self, left, right):
        if right <= left:
            return self.default_value
        left += self.power - 1
        right += self.power - 2
        ret = self.default_value
        while right - left > 1:
            if left & 1 == 0:
                ret = ret | self.node[left]
            if right & 1 == 1:
                ret = ret | self.node[right]
                right -= 1
            left = left // 2
            right = (right - 1) // 2
        if left == right:
            ret = ret | self.node[left]
        else:
            ret = (ret | self.node[left]) | self.node[right]
        return ret


N = int(input())
S = list(input().strip())
Q = int(input())
MAX_DIGIT = 26

st = SegmentTree(S)

for i in range(Q):
    q, a, b = map(str, input().split())
    if int(q) == 1:
        a = int(a) - 1
        st.update(a, b)
    if int(q) == 2:
        a = int(a) - 1
        b = int(b)
        res = st.query(a, b)
        ans = 0
        for d in range(MAX_DIGIT):
            if res >> d & 1:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
Q = int(input())

l = 2**((N-1).bit_length())
#data = [Counter([]) for i in range(2*l)]
data = [0] * (2*l)

str2bin = lambda x : 1 << (ord(x) - ord('a'))
    
for i in range(N):
    data[l+i] = str2bin(S[i])
for i in range(l-1,0,-1):
    data[i] = data[2*i] | data[2*i+1]

for cnt in range(Q):
    a,b,c = input().split()
    a = int(a)
    b = int(b)
    if a == 1:
        n = l + b - 1
        data[n] = str2bin(c)
        n //= 2
        while n > 0:
            data[n] = data[2*n] | data[2*n+1]
            n = n // 2
    else:
        c = int(c)
        i = b + l -1
        j = c + l
        res = 0
        while j-i > 0:
            if i & 1:
                res |= data[i]
                i += 1
            if j & 1:
                res |= data[j-1]
                j -= 1
            i //= 2
            j //= 2
        print(bin(res).count('1'))

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, data):
        # 単位元
        self.ide_ele = 0
        # num: n以上の最小の2のべき乗
        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] = 1 << (ord(data[i]) - 97)
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.seg[2 * i + 1] | self.seg[2 * i + 2]

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

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


N = int(input())
S = list(input().strip())
Q = int(input())
MAX_DIGIT = 26
st = SegmentTree(S)


for i in range(Q):
    q, a, b = map(str, input().split())
    if int(q) == 1:
        a = int(a) - 1
        st.update(a, b)
    if int(q) == 2:
        a = int(a) - 1
        b = int(b)
        res = st.query(a, b)
        print(str(bin(res)).count('1'))

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
class SegmentTree:
    def segfunc(self,x,y):
        #ここに評価
        po = [0 for i in range(26)]
        for i in range(26):
            po[i] = x[i]+y[i]
        return po

    #nは総数、initがlist,ide_eleが元
    def __init__(self,n,init,ide_ele):
        self.n = n
        self.ide_ele = ide_ele
        self.num = 2**(n-1).bit_length()
        self.seg = [ide_ele for i in range(2*self.num)]
        for i in range(n):
            self.seg[i+self.num-1] = init[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[2*k+1],self.seg[2*k+2])
    
    def query(self,p,q):
        if q <= p:
            return [1 if i == 0 else 0 for i in range(26)]
        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 //= 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 solver():
    n = onem()
    s = input().split()[0]
    po = onem()

    abc = [[0 for i in range(26)] for j in range(n)]

    for i in range(n):
        ppp = s[i]
        abc[i][ord(s[i]) - 97] += 1

    Se = SegmentTree(n,abc,[0 for i in range(26)])



    for i in range(po):
        a,b,c = input().split()
        a = int(a)
        b = int(b)
        if a == 1:
            ppp = [0] * 26
            ppp[ord(c) - 97] = 1
            Se.update(b-1,ppp)      
        else:
            c = int(c)
            op = Se.query(b-1,c)
            co = 0
            for i in range(26):
                if op[i] >= 1:
                    co += 1
            print(co)


if __name__ == "__main__":
    solver()

Submission status: Accepted

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 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)
for idx, i in enumerate(S[1:], 1):
    bit.update(i, idx, 1)
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))