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:
import sys
input = sys.stdin.readline


class SegmentTrees:
    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 = [no_effect] * self.tree_size
        self.no_effect = no_effect
        self.initialize_tree(target, no_effect)

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

    @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], self.tree[child2])
        return merged

    def initialize_tree(self, target: list, no_effect=0):
        initial_leaf = self.tree_size // 2
        leaves = range(initial_leaf, initial_leaf+len(target))
        for value, leaf in zip(target, leaves):
            self.tree[leaf] = self.initialize_func(value)

        for parent in range(initial_leaf-1, -1, -1):
            self.tree[parent] = self.merge_child_data(parent)

    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 is_in_query(left, right):
            if _from <= left and right <= to:
                return 1
            elif to < left or right < _from:
                return 0
            else:
                return -1

        node = 0
        left, right = 0, self.tree_size//2
        todo = [[node, left, right]]

        result = self.no_effect
        while todo:
            node, left, right = todo.pop()
            if is_in_query(left, right) == 1:
                data = self.tree[node]
                result = self.merge_func(result, data)

            elif is_in_query(left, right) == 0:
                continue

            else:
                child1 = node * 2 + 1
                child2 = node * 2 + 2
                center = (left+right)//2
                todo.append([child1, left, center])
                todo.append([child2, center+1, right])

        return bin(result).count('1')


n = int(input())
S = input().replace('\n', '')
seg_tree = SegmentTrees(target=S, no_effect=0)

Q = int(input())
for _ in range(Q):
    query = input().split()
    if query[0] == '1':
        index, new = int(query[1])-1, query[2]
        seg_tree.update(new, index)

    elif query[0] == '2':
        _from, to = int(query[1])-1, int(query[2])-1
        print(seg_tree.resolve_query(_from, to))

Submission status: Accepted

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

n = int(input())
s = list(str(input()))
s = [{ord(c)-ord('a')} for c in s]

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

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

def update(k, x):
    k += num - 1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[2*k+1], seg[2*k+2])

def query(p, q):
    if q <= p:
        return ide_ele
    p += num - 1
    q += num - 2
    res = ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res, seg[p])
        if q&1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(segfunc(res, seg[p]), seg[q])
    return res

# identity element
ide_ele = set()

# num: n以上の最小の2のべき乗
num = 2**(n-1).bit_length()
seg = [ide_ele]*2*num

init(s)

q = int(input())
for _ in range(q):
    t, x, y = map(str, input().split())
    if t == '1':
        i = int(x)-1
        c = {ord(y)-ord('a')}
        update(i, c)
    else:
        l = int(x)-1
        r = int(y)-1
        print(len(query(l, r+1)))

Submission status: Accepted

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

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

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

def update(k, x):
    k += num - 1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[2*k+1], seg[2*k+2])

def query(p, q):
    if q <= p:
        return ide_ele
    p += num - 1
    q += num - 2
    res = ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res, seg[p])
        if q&1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(segfunc(res, seg[p]), seg[q])
    return res

# identity element
ide_ele = set()

# num: n以上の最小の2のべき乗
num = 2**(n-1).bit_length()
seg = [ide_ele]*2*num

init(s)

q = int(input())
for _ in range(q):
    t, x, y = map(str, input().split())
    if t == '1':
        i = int(x)-1
        c = {ord(y)-ord('a')}
        update(i, c)
    else:
        l = int(x)-1
        r = int(y)-1
        print(len(query(l, r+1)))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

#Binary Indexed Tree（１点加算）
#1-indexed
class BIT:
    """
    a[1]~a[n]の数列を想定
    """

    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def add(self, index, x):
        """
        a[index]にxを加算
        """
        while index <= self.size:
            self.tree[index] += x
            index += index & (-index)
 
    def sum(self, index):
        """
        a[1]~a[index]の和
        """
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s
 
    def search(self, value):
        """
        sum(index) >= value を満たす最小のindex
        sum(n) < value のとき n+1 を返す
        """
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.tree[i + step] < value:
                i += step
                s += self.tree[i]
            step >>= 1
        return i + 1

N = I()
S = list(str(input()))
Q = I()

def calc(c):
    return ord(c)-ord('a')

bit = [BIT(N) for _ in range(26)]
for i in range(N):
    bit[calc(S[i])].add(i+1,1)

for i in range(Q):
    now = list(input().split())
    if now[0]=='1':
        iq = int(now[1])
        cq = str(now[2])
        bit[calc(S[iq-1])].add(iq,-1)
        bit[calc(cq)].add(iq,1)
        S[iq-1] = cq
    else:
        lq = int(now[1])
        rq = int(now[2])
        ans = 0
        for j in range(26):
            if lq == 1:
                if bit[j].sum(rq) >= 1:
                    ans += 1
            else:
                if bit[j].sum(rq) != bit[j].sum(lq-1):
                    ans += 1
        print(ans)

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, initial_values, f=max, zero=0):
        self.__size = len(initial_values)
        self.__n = 1 << ((self.__size - 1).bit_length())
        self.__f = f
        self.__z = zero
        self.__dat = [zero] * (2 * self.__n)
        self.__get_leaf = lambda i: self.__n + i - 1
        self.__get_parent = lambda i: (i-1)//2
        self.__get_children = lambda i: (self.__dat[2*i+1], self.__dat[2*i+2])
        self.__is_left = lambda i: i&1 == 1
        self.__is_right = lambda i: i&1 == 0
        zi = self.__get_leaf(0)
        for i, v in enumerate(initial_values):
            self.__dat[zi + i] = v
        for i in range(zi-1, -1, -1):
            self.__dat[i] = self.__f(*self.__get_children(i))
    
    def update(self, index, value):
        i = self.__get_leaf(index)
        if self.__dat[i] == value: return
        self.__dat[i] = value
        while i > 0:
            i = self.__get_parent(i)
            self.__dat[i] = self.__f(*self.__get_children(i))
    
    def query(self, from_inclusive, to_exclusive):
        if to_exclusive <= from_inclusive: return self.__z
        a, b = self.__get_leaf(from_inclusive), self.__get_leaf(to_exclusive) - 1
        ans = self.__z
        while b - a > 1:
            if self.__is_right(a): ans = self.__f(ans, self.__dat[a])
            if self.__is_left(b): ans, b = self.__f(ans, self.__dat[b]), b-1
            a, b = a//2, self.__get_parent(b)
        ans = self.__f(ans, self.__dat[a])
        if a != b: ans = self.__f(ans, self.__dat[b])
        return ans

N = int(input())
S = input()
g = lambda c: 1 << (ord(c)-ord('a'))
tree = SegmentTree([g(c) for c in S], lambda x,y:x|y)
Q = int(input())
for _ in range(Q):
    t, a, b = input().split()
    if t == '1': tree.update(int(a)-1, g(b))
    else: print(bin(tree.query(int(a)-1, int(b))).count('1'))

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, initial_values, f=max, zero=0):
        self.__size = len(initial_values)
        self.__n = 1 << ((self.__size - 1).bit_length())
        self.__f = f
        self.__z = zero
        self.__dat = [zero for _ in range(2 * self.__n)]
        self.__get_leaf = lambda i: self.__n + i - 1
        self.__get_parent = lambda i: (i-1)//2
        self.__get_children = lambda i: (self.__dat[2*i+1], self.__dat[2*i+2])
        self.__is_left = lambda i: i&1 == 1
        self.__is_right = lambda i: i&1 == 0
        zi = self.__get_leaf(0)
        for i, v in enumerate(initial_values):
            self.__dat[zi + i] = v
        for i in range(zi-1, -1, -1):
            self.__dat[i] = self.__f(*self.__get_children(i))
    
    def update(self, index, value):
        i = self.__get_leaf(index)
        if self.__dat[i] == value: return
        self.__dat[i] = value
        while i > 0:
            i = self.__get_parent(i)
            self.__dat[i] = self.__f(*self.__get_children(i))
    
    def query(self, from_inclusive, to_exclusive):
        if to_exclusive <= from_inclusive: return self.__z
        a, b = self.__get_leaf(from_inclusive), self.__get_leaf(to_exclusive) - 1
        ans = self.__z
        while b - a > 1:
            if self.__is_right(a): ans = self.__f(ans, self.__dat[a])
            if self.__is_left(b): ans, b = self.__f(ans, self.__dat[b]), b-1
            a, b = a//2, self.__get_parent(b)
        ans = self.__f(ans, self.__dat[a])
        if a != b: ans = self.__f(ans, self.__dat[b])
        return ans

N = int(input())
S = input()
g = lambda c: 1 << (ord(c)-ord('a'))
tree = SegmentTree([g(c) for c in S], lambda x,y:x|y)
Q = int(input())
for _ in range(Q):
    t, a, b = input().split()
    if t == '1': tree.update(int(a)-1, g(b))
    else: print(bin(tree.query(int(a)-1, int(b))).count('1'))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007
import operator
class SegmentTree:
    def __init__(self, size, default, op = operator.or_):
        self.size = 2**size.bit_length()
        self.dat = [default]*(self.size*2)
        self.op = op

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

    def add(self, i, x):
        i += self.size
        self.dat[i] = self.op(self.dat[i], x)
        while i > 0:
            i >>= 1
            self.dat[i] = self.op(self.dat[i], x)

    def get(self, a, b = None):
        if b is None:
            b = a + 1
        l, r = a + self.size, b + self.size
        res = None
        while l < r:
            if l & 1:
                if res is None:
                    res = self.dat[l]
                else:
                    res = self.op(res, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                if res is None:
                    res = self.dat[r]
                else:
                    res = self.op(res, self.dat[r])
            l >>= 1
            r >>= 1
        return res
def solve():
    n = I()
    S = list(input())
    m = ord("z")-ord("a")+1
    s = SegmentTree(n,0)
    for i in range(n):
        k = ord(S[i])-ord("a")
        k = 1 << k
        s.update(i,k)
    Q = I()
    for _ in range(Q):
        q = input().split()
        if q[0] == "1":
            i = int(q[1])-1
            if S[i] == q[2]:
                continue
            s.update(i,0)
            k = ord(q[2])-ord("a")
            k = 1 << k
            s.update(i,k)
            S[i] = q[2]
        else:
            l,r = q[1:]
            l = int(l)
            r = int(r)
            print(bin(s.get(l-1,r)).count("1"))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl

n = int(input())
s = list(input())
q = int(input())
l = [[] for i in range(26)]
for i in range(n):
    l[ord(s[i])-ord("a")].append(i)
for i in range(q):
    x,y,z = input().split()
    if x == "1":
        y = int(y)-1
        if s[y] == z:
            continue
        b = ord(s[y])-ord("a")
        a = ord(z)-ord("a")
        l[b].pop(bl(l[b],y))
        l[a].insert(bl(l[a],y),y)
        s[y] = z
    if x == "2":
        count = 0
        for j in l:
            index = bl(j,int(y)-1)
            if index < len(j) and j[index] < int(z):
                count += 1
        print(count)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
s = list(input())
q = int(input())
l = [[] for i in range(26)]
for i in range(n):
    l[ord(s[i])-ord("a")].append(i)


for i in range(q):
    x,y,z = input().split()
    if int(x) == 1:
        if s[int(y)-1] == z:
            continue
        index = bisect.bisect_left(l[ord(s[int(y)-1])-ord("a")],int(y)-1)
        l[ord(s[int(y)-1])-ord("a")].pop(index)
        index = bisect.bisect_left(l[ord(z)-ord("a")],int(y)-1)
        l[ord(z)-ord("a")].insert(index,int(y)-1)
        s[int(y)-1] = z
    if int(x) == 2:
        count = 0
        for j in l:
            index = bisect.bisect_left(j,int(y)-1)
            if index < len(j) and j[index] < int(z):
                count += 1
        print(count)

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7


class SegmentTree(object):

    def __init__(self, A, e, fn):  # O(N)
        """
        :param A: 区間クエリの対象となる配列
        :param e: 単位元 fn(a, e) = fn(e, a) = a
        :param fn: (a, b) -> x な関数 a, bは交換則を満たす
        """
        self.e = e
        self.fn = fn
        self.length = 2 ** (len(A) - 1).bit_length()
        self.tree = [e] * 2 * self.length
        for i in range(len(A)):
            self.tree[i + self.length - 1] = A[i]
        for i in range(self.length - 2, -1, -1):
            self.tree[i] = self.fn(self.tree[2 * i + 1], self.tree[2 * i + 2])

    # 配列のi番目をxに更新する
    def update(self, i, x):  # O(logN)
        i += self.length - 1
        self.tree[i] = x
        while i:
            i = (i - 1) // 2
            self.tree[i] = self.fn(self.tree[i * 2 + 1], self.tree[i * 2 + 2])

    # 区間[p, q)に関するクエリに答える
    def query(self, p, q):  # O(logN)
        if q <= p:
            return self.e
        p += self.length - 1
        q += self.length - 2
        res = self.e
        while q - p > 1:
            if p & 1 == 0:
                res = self.fn(res, self.tree[p])
            if q & 1 == 1:
                res = self.fn(res, self.tree[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self.fn(res, self.tree[p])
        else:
            res = self.fn(self.fn(res, self.tree[p]), self.tree[q])
        return res


N = I()
S = input()
Q = [tuple(input().split()) for _ in range(I())]

A = [2 ** (ord(c) - 97) for c in S]
seg = SegmentTree(A, 0, lambda a, b: a | b)


for t, i, c in Q:
    if t == '1':
        i = int(i) - 1
        seg.update(i, 2 ** (ord(c) - 97))
    else:
        l, r = int(i) - 1, int(c)
        bit = seg.query(l, r)
        print(bin(bit).count('1'))

Submission status: Accepted

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))


class SegmentTree(object):

    def __init__(self, A, e, fn):  # O(N)
        """
        :param A: 区間クエリの対象となる配列
        :param e: 単位元 fn(a, e) = fn(e, a) = a
        :param fn: (a, b) -> x な関数 a, bは交換則を満たす
        """
        self.e = e
        self.fn = fn
        self.length = 2 ** (len(A) - 1).bit_length()
        self.tree = [e] * 2 * self.length
        for i in range(len(A)):
            self.tree[i + self.length - 1] = A[i]
        for i in range(self.length - 2, -1, -1):
            self.tree[i] = self.fn(self.tree[2 * i + 1], self.tree[2 * i + 2])

    # 配列のi番目をxに更新する
    def update(self, i, x):  # O(logN)
        i += self.length - 1
        self.tree[i] = x
        while i:
            i = (i - 1) // 2
            self.tree[i] = self.fn(self.tree[i * 2 + 1], self.tree[i * 2 + 2])

    # 区間[p, q)に関するクエリに答える
    def query(self, p, q):  # O(logN)
        if q <= p:
            return self.e
        p += self.length - 1
        q += self.length - 2
        res = self.e
        while q - p > 1:
            if p & 1 == 0:
                res = self.fn(res, self.tree[p])
            if q & 1 == 1:
                res = self.fn(res, self.tree[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self.fn(res, self.tree[p])
        else:
            res = self.fn(self.fn(res, self.tree[p]), self.tree[q])
        return res


N = I()
S = input()
Q = [tuple(input().split()) for _ in range(I())]

A = [2 ** (ord(c) - 97) for c in S]
seg = SegmentTree(A, 0, lambda a, b: a | b)


for t, i, c in Q:
    if t == '1':
        i = int(i) - 1
        seg.update(i, 2 ** (ord(c) - 97))
    else:
        l, r = int(i) - 1, int(c)
        bit = seg.query(l, r)
        print(bin(bit).count('1'))

Submission status: Accepted

Solution code:
n = int(input())
s = list(str(input().rstrip()))
q = int(input())


class SSQ:
    def __init__(self, n, e):
        # 単位元
        self.e = e
        # num_min:n以上の最小の2のべき乗
        self.num_min = 2**(n-1).bit_length()
        self.seg_min = [self.e]*2*self.num_min

    def update(self, k, x):
        k += self.num_min-1
        self.seg_min[k] = x
        while k:
            k = (k-1)//2
            self.seg_min[k] = self.seg_min[k*2+1] or self.seg_min[k*2+2]

    def query(self, p, q):
        q += 1
        if q <= p:
            return self.e
        p += self.num_min-1
        q += self.num_min-2
        res = self.e
        while q-p > 1:
            if p & 1 == 0:
                res = res or self.seg_min[p]
            if q & 1 == 1:
                res = res or self.seg_min[q]
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = res or self.seg_min[p]
        else:
            res = res or self.seg_min[p] or self.seg_min[q]
        return res

ssqs = [SSQ(n, False) for i in range(26)]

for i in range(n):
    ssqs[ord(s[i]) - ord('a')].update(i, True)

out = []
for i in range(q):
    com, x, y = list(input().split())
    if com == '1':
        idx = int(x) - 1
        pre_alph = ord(s[idx]) - ord('a')
        ssqs[pre_alph].update(idx, False)
        s[idx] = y
        alph = ord(y) - ord('a')
        ssqs[alph].update(idx, True)
    else:
        x, y = int(x) - 1, int(y) - 1
        cnt = 0
        for i in range(26):
            cnt += 1 if ssqs[i].query(x, y) else 0
        out.append(str(cnt))
print("\n".join(out))

Submission status: Accepted

Solution code:

class SegTree(object):
    """docstring for SegTree."""
    def __init__(self, l, _n):
        n = 1
        while n<_n:
            n *= 2
        self.n = n
        self.dat = [0 for _ in range(2*n)]
        for i in range(_n):
            self.dat[i+n-1] |= 1<<l[i]
        self.init(0)

    def init(self, i):
        if i>=self.n-1:
            return self.dat[i]
        self.dat[i] = self.init(self.left(i)) | self.init(self.right(i))
        return self.dat[i]

    def par(self, i):
        return (i-1)//2

    def left(self, i):
        return 2*i+1

    def right(self, i):
        return 2*i+2

    def update(self, i, x):
        i += self.n-1
        self.dat[i] = 1<<x
        while i>0:
            i = self.par(i)
            self.dat[i] = self.dat[self.left(i)] | self.dat[self.right(i)]

    def q(self,a,b,k,l,r):
        if r<=a or b<=l:
            return 0
        if a<=l and r<=b:
            return self.dat[k]
        return self.q(a,b,self.left(k),l,(l+r)//2) | self.q(a,b,self.right(k),(l+r)//2,r)

    def query(self,a,b):
        return self.q(a,b,0,0,self.n)

n = int(input())
s = [ord(c)-ord("a") for c in input()]
q = int(input())
ql = [input().split() for _ in range(q)]

seg = SegTree(s,n)

for i in range(q):
    if ql[i][0]=="1":
        seg.update(int(ql[i][1])-1, ord(ql[i][2])-ord("a"))
    else:
        r = seg.query(int(ql[i][1])-1, int(ql[i][2]))
        print(bin(r).count("1"))

Submission status: Accepted

Solution code:
def e_simple_string_queries():
    # 参考: https://atcoder.jp/contests/abc157/submissions/10481866
    N = int(input())
    S = input()
    Q = int(input())
    Queries = [input().split() for _ in range(Q)]

    class SegmentTree(object):
        """
        Segment Tree (0-indexed)
        1. update:  k 番目の値を x に更新する
        2. query: 区間 [l, r) の値を得る
        """

        def __init__(self, n, func, identity, init_list=[]):
            """
            n: 要素数
            func: 値の操作に使う関数 (min, max, add, gcd, etc.)
            identity: func に対する単位元
            init_list: 設定されていれば、それで初期化する
            """
            self.n = n
            self.func = func
            self.identity = identity

            # n を超える最小の 2 の冪乗
            self.pow2 = 1
            while self.pow2 < n:
                self.pow2 <<= 1

            self.tree = [self.identity] * (self.pow2 << 1)

            # 初期化を指定していた場合
            if init_list:
                # 木の最下段の初期化
                for k in range(n):
                    self.tree[k + self.pow2] = init_list[k]
                # 木の根へ初期化
                for k in range(self.pow2 - 1, -1, -1):
                    self.tree[k] = self.func(self.tree[k * 2], self.tree[k * 2 + 1])

        def update(self, k, x):
            """k 番目の値を x に更新"""
            pos = k + self.pow2
            self.tree[pos] = x  # 木の葉 (元の配列に当たる) を変更
            # 木の根に向かって更新を反映
            while pos > 0:
                pos >>= 1
                self.tree[pos] = self.func(self.tree[pos * 2], self.tree[pos * 2 + 1])

        def query(self, a, b):
            """区間 [a, b) について self.func を通した値を得る"""
            left = a + self.pow2
            right = b + self.pow2
            ret = self.identity
            while left < right:
                if right & 1:
                    right -= 1
                    ret = self.func(ret, self.tree[right])
                if left & 1:
                    ret = self.func(ret, self.tree[left])
                    left += 1
                left >>= 1
                right >>= 1
            return ret

        def get(self, k):
            """k 番目の値を取得"""
            return self.tree[k + self.pow2]

        def get_all(self):
            """[0, n) の値を取得"""
            return self.tree[1]

        def __str__(self):
            return ' '.join(map(str, [self.get(k) for k in range(self.n)]))

    def popcount(n):
        """n を 2 進表記したとき、1 となっているビットの数"""
        return bin(n).count('1')

    s = [ord(ch) - 97 for ch in S]  # ord('a') => 97
    # 文字を Unicode コードポイントで持つことで、
    # セグメント木で「[l, r) に現れる文字」を管理できる
    segtree = SegmentTree(N, lambda a, b: a | b, 0, [1 << ch for ch in s])

    ans = []
    for q, s1, s2 in Queries:
        if q == '1':
            i, ch = int(s1) - 1, ord(s2) - 97
            # s[i] == ch のときに下の処理を行うと正しく動作しない
            # (ch == prev のとき xor をとると 0 になってしまう)
            if s[i] != ch:
                prev = s[i]
                s[i] = ch
                # これまでの文字列に新しい文字を追加し (bitwise-or)、
                # 古い文字を消す (bitwise-xor)
                segtree.update(i, (segtree.get(i) | 1 << ch) ^ (1 << prev))
        elif q == '2':
            left, right = int(s1) - 1, int(s2) - 1
            # 立っているビットの数が文字種数となるように管理している
            ans.append(popcount(segtree.query(left, right + 1)))
    return '\n'.join(map(str, ans))

print(e_simple_string_queries())

Submission status: Accepted

Solution code:
n = int(input())
s = input()
q = int(input())
C = [0]*n
for i, k in enumerate(s):
  C[i] = 1<<(ord(k)-ord("a"))

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

def segfunc(a,b):
  return a | b

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = 1<<x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

init(C)
for _ in range(q):
  t, a, b = input().split()
  if t == "1":
    w = ord(b) - ord("a")
    update(int(a)-1, w)
  else:
    ans = query(int(a)-1, int(b))
    print(bin(ans).count("1"))

Submission status: Accepted

Solution code:
n=int(input())+1
w = input()
data=[0]*n*2
def update(i,x):
    i+=n
    data[i]=x
    i//=2
    while i:
      data[i]=data[i*2]|data[i*2+1]
      i//=2
def query(l,r):
    l+=n
    r+=n
    s=0
    while l<r:
      if l&1 == 1:
        s|=data[l]
        l+=1
      if r&1 == 1:
        r-=1
        s|=data[r]
      l//=2
      r//=2
    return bin(s).count('1')
def word_num(a):
    return 1<<(ord(a)-97)

for i in range(n-1):
    data[i+n] = word_num(w[i])    
for i in range(n-1,0,-1):
    data[i]=data[i*2]|data[i*2 + 1]

ans=[]
q=int(input())
for i in range(q):
    a,s,t=input().split()
    if a=='1':
        s=int(s)
        update(int(s)-1,word_num(t))
    if a=='2':
        s=int(s)
        t=int(t)
        ans.append(query(int(s)-1,int(t)))
for i in range(len(ans)):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.buffer.readline
import bisect

def main():
    N = int(input())
    S = list(str(input()))
    
    pos = [[] for _ in range(26)]
    for x,s in enumerate(S):
        num = ord(s)-ord("a")
        pos[num].append(x)
    
    q = int(input())
    for _ in range(q):
        m,a,b = map(str,input().split())
        if m == "1":
            a = int(a)-1
            if S[a] == b:
                continue
            else:
                popind = bisect.bisect_left(pos[ord(S[a])-ord("a")],a)
                pos[ord(S[a])-ord("a")].pop(popind)
                bisect.insort(pos[ord(b)-ord("a")],a)
                S[a] = b
        else:
            a,b = int(a)-1,int(b)-1
            count = 0
            for i in range(26):
                l = bisect.bisect_left(pos[i],a)
                if l >= len(pos[i]):
                    continue
                if pos[i][l] <= b:
                    count += 1
            print(count)

if __name__ == "__main__":
    main()