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:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class SegTree:
    """
    セグメント木
    1.update:  i番目の値をxに更新する
    2.query: 区間[l, r)の値を得る
    """

    def __init__(self, n, func, intv, A=[]):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max, add, gcdなど)
        :param intv: 要素の初期値(単位元)
        :param A: 初期化に使うリスト(オプション)
        """
        self.n = n
        self.func = func
        self.intv = intv
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.intv] * (n2 << 1)
        # 初期化の値が決まっている場合
        if A:
            # 1段目(最下段)の初期化
            for i in range(n):
                self.tree[n2+i] = A[i]
            # 2段目以降の初期化
            for i in range(n2-1, -1, -1):
                self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 0:
            i >>= 1
            self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def query(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = self.intv
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.tree[r])
            if l & 1:
                s = self.func(s, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1
        return s

    def get(self, i):
        """ 一点取得 """
        return self.tree[i+self.n2]

    def all(self):
        """ 全区間[0, n)の取得 """
        return self.tree[1]

    def print(self):
        for i in range(self.n):
            print(self.get(i), end=' ')
        print()

def popcount(i):
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    i = (i + (i >> 4)) & 0x0f0f0f0f
    i = i + (i >> 8)
    i = i + (i >> 16)
    return i & 0x3f

N = INT()
S = [ord(c)-97 for c in input()]
st = SegTree(N, lambda a, b: a | b, 0)
for i, s in enumerate(S):
    st.update(i, st.get(i) | 1<<s)

Q = INT()
for _ in range(Q):
    q = list(input().split())
    if q[0] == '1':
        _, i, c = q
        i = int(i) - 1
        c = ord(c) - 97
        if S[i] != c:
            prev = S[i]
            S[i] = c
            st.update(i, (st.get(i) | 1<<c) ^ 1<<prev)
    else:
        _, l, r = q
        l, r = int(l) - 1, int(r) - 1
        ans = popcount(st.query(l, r+1))
        print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left, bisect_right, insort

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
S = list('-' + sr())
d = [[] for _ in range(26)]
for i in range(1, N+1):
    s = S[i]
    o = ord(s) - ord('a')
    insort(d[o], i)

Q = ir()
for _ in range(Q):
    q, a, b = sr().split()
    if q == '1':
        a = int(a)
        if S[a] == b:
            continue
        prev = ord(S[a]) - ord('a')
        d[prev].remove(a)
        next = ord(b) - ord('a')
        insort(d[next], a)
        S[a] = b
    else:
        a = int(a); b = int(b)
        ans = 0
        for alpha in range(26):
            if bisect_right(d[alpha], b) - bisect_left(d[alpha], a) >= 1:
                ans += 1
        print(ans)

# 17

Submission status: Accepted

Solution code:
from bisect import bisect_left, insort_left


def main():
    n = int(input())
    s = list(input())
    q = int(input())
    qs = [input().split() for _ in range(q)]

    abc = [[] for _ in range(26)]
    for i, e in enumerate(s):
        j = ord(e) - ord("a")
        abc[j].append(i)

    for t, e1, e2 in qs:
        if t == "1":
            i = int(e1) - 1
            c = e2

            let = s[i]

            if let == c:
                continue

            idx = ord(let) - ord("a")
            popi = bisect_left(abc[idx], i)
            abc[idx].pop(popi)

            idx = ord(c) - ord("a")
            insort_left(abc[idx], i)

            s[i] = c

        else:
            l = int(e1) - 1
            r = int(e2) - 1

            cnt = 0
            for i in range(26):
                li = bisect_left(abc[i], l)
                if li >= len(abc[i]):
                    continue
                if abc[i][li] <= r:
                    cnt += 1

            print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
q = int(input())
import sys
input = sys.stdin.readline
Q = [list(input().split()) for i in range(q)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

import string
DD = [chr(i) for i in range(ord("a"), ord("z")+1)]
D = {}
for i in range(len(DD)):
    D[DD[i]] = i
S = []
for i in range(n):
    S.append(D[s[i]])
B = [Bit(n) for i in range(26)]
for i in range(26):
    for j in range(n):
        if S[j] == i:
            B[i].add(j+1, 1)  # 合計n回

for i in range(q):
    qu = int(Q[i][0])
    if qu == 2:
        l = int(Q[i][1])
        r = int(Q[i][2])
        ans = 0
        for j in range(26):
            p = min(1, B[j].sum(r) - B[j].sum(l-1))
            # print(j,p)
            ans += p
        print(ans)
    elif qu == 1:
        iq = int(Q[i][1])-1
        c = D[Q[i][2]]
        pc = S[iq]
        B[pc].add(iq+1, -1)
        B[c].add(iq+1, 1)
        S[iq] = c

Submission status: Accepted

Solution code:
from collections import namedtuple


def _hasParents(i):
    return i > 1


def _isLeftChild(i):
    return i % 2 == 0


def _isRightChild(i):
    return i % 2 == 1


def _parentNode(i):
    return i // 2


def _leftChild(i):
    return 2 * i


def _rightChild(i):
    return 2 * i + 1


def _leftSibling(i):
    return i - 1


def _rightSibling(i):
    return i + 1


def _nextPowerOfTwo(n):
    ret = 1
    while ret < n:
        ret *= 2
    return ret


def ancestors(i):
    while _hasParents(i):
        i = _parentNode(i)
        yield i


Config = namedtuple("Config", ["mconvert", "mappend", "mempty"])


class SegmentTree:
    def __init__(self, arr, mconvert, mappend, mempty, minCapacity=1):
        def wrappedMconvert(x):
            if x is not None:
                return mconvert(x)
            else:
                return mempty()

        def wrappedMappend(x, y):
            xEmpty = x == mempty()
            if xEmpty:
                return y
            yEmpty = y == mempty()
            if yEmpty:
                return x
            if xEmpty and yEmpty:
                return mempty()
            return mappend(x, y)

        self.config = Config(
            mconvert=wrappedMconvert, mappend=wrappedMappend, mempty=mempty
        )

        # Init empty tree
        self.MAX_SIZE = _nextPowerOfTwo(max(len(arr), minCapacity))
        self.values = [None] * self.MAX_SIZE
        self.accumulations = [self.config.mempty()] * (2 * self.MAX_SIZE)
        self.numValues = 0

        # Init values
        self.values[: len(arr)] = arr
        self.numValues = len(arr)
        # Init leaf accumulations
        self.accumulations[self.MAX_SIZE : self.MAX_SIZE + len(arr)] = map(
            self.config.mconvert, arr
        )
        # Init parent accumulations
        for parent in range(self.MAX_SIZE - 1, -1, -1):
            self.accumulations[parent] = self.config.mappend(
                self.accumulations[_leftChild(parent)],
                self.accumulations[_rightChild(parent)],
            )

    def query(self, i, j):
        # Inclusive i, exclusive j
        if not (0 <= i <= j <= self.numValues):
            raise IndexError
        if i == j:
            return self.config.mempty()
        leftTotal = self.config.mempty()
        rightTotal = self.config.mempty()
        l = self.MAX_SIZE + i
        r = self.MAX_SIZE + j - 1  # make inclusive both endpoints for calculations
        while l <= r:
            if _isRightChild(l):
                leftTotal = self.config.mappend(leftTotal, self.accumulations[l])
                l = _rightSibling(l)
            l = _parentNode(l)

            if _isLeftChild(r):
                rightTotal = self.config.mappend(self.accumulations[r], rightTotal)
                r = _leftSibling(r)
            r = _parentNode(r)
        return self.config.mappend(leftTotal, rightTotal)

    def append(self, x):
        assert self.numValues + 1 <= self.MAX_SIZE
        self.numValues += 1
        self.__setitem__(self.numValues - 1, x)

    def pop(self, i=None):
        if i is not None:
            raise NotImplementedError
        if not self.numValues:
            raise IndexError
        ret = self.__getitem__(self.numValues - 1)
        self.__delitem__(self.numValues - 1)
        return ret

    def insert(self, i, x):
        raise NotImplementedError

    def __getitem__(self, index):
        if isinstance(index, slice):
            raise NotImplementedError
        if not 0 <= index < self.numValues:
            raise IndexError
        ret = self.values[index]
        assert ret is not None
        return ret

    def __setitem__(self, i, x):
        if isinstance(i, slice):
            raise NotImplementedError

        if not 0 <= i < self.numValues:
            raise IndexError
        index = self.MAX_SIZE + i
        self.values[i] = x
        self.accumulations[index] = self.config.mconvert(x)
        for parent in ancestors(index):
            self.accumulations[parent] = self.config.mappend(
                self.accumulations[_leftChild(parent)],
                self.accumulations[_rightChild(parent)],
            )
            parent = _parentNode(parent)

    def __delitem__(self, i):
        if isinstance(i, slice):
            raise NotImplementedError
        if not 0 <= i < self.numValues:
            raise IndexError
        index = self.MAX_SIZE + i
        self.values[i] = None
        self.accumulations[index] = self.config.mempty()
        for parent in ancestors(index):
            self.accumulations[parent] = self.config.mappend(
                self.accumulations[_leftChild(parent)],
                self.accumulations[_rightChild(parent)],
            )
        self.numValues -= 1

    def __len__(self):
        return self.numValues


def charToBitmask(c):
    return 1 << (ord(c) - ord("a"))


def popcount(i):
    # Python doesn't have __builtin_popcount
    # https://stackoverflow.com/a/407758
    assert 0 <= i < 0x100000000
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xFFFFFFFF) >> 24


N, = list(map(int, input().split()))
S = input()
Q, = list(map(int, input().split()))
queries = []
for i in range(Q):
    queries.append(input().split())


segTree = SegmentTree(S, charToBitmask, lambda mask1, mask2: mask1 | mask2, lambda: 0)
out = []
for query in queries:
    if query[0] == "1":
        _, i, c = query
        i = int(i) - 1
        segTree[i] = c
    elif query[0] == "2":
        _, l, r = query
        l = int(l) - 1
        r = int(r) - 1
        mask = segTree.query(l, r + 1)
        out.append(str(popcount(mask)))
print("\n".join(out))

Submission status: Accepted

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


class SegmentTree():
    def __init__(self, S):
        self.size = 19
        self.array = [set()] * (2**(self.size + 1) - 1)
        for i, c in enumerate(S):
            self.array[i + 2**self.size - 1] = {c}
        for i in range(2**self.size - 1)[::-1]:
            self.array[i] = self.array[2 * i + 1] | self.array[2 * i + 2]

    def subquery(self, l, r, k, i, j):
        # 区間[i,j)の中で区間[l,r)の文字列の集合を返す
        if j <= l or r <= i:
            return set()
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_set = self.subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_set = self.subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return l_set | r_set

    def query(self, l, r):
        # [l,r)に含まれる文字の種類数
        return len(self.subquery(l, r, 0, 0, 2**self.size))

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = {c}
        while tmp > 0:
            tmp = (tmp - 1) // 2
            self.array[tmp] = self.array[2 * tmp + 1] | self.array[2 * tmp + 2]


N = int(input())
S = [ord(_) - 97 for _ in list(input())]
Q = int(input())
tree = SegmentTree(S)
for q in range(Q):
    t, i, c = input().split()
    if t == '1':
        i = int(i) - 1
        tree.update(i, ord(c) - 97)
    else:
        l, r = int(i) - 1, int(c)
        print(tree.query(l, r))

Submission status: Accepted

Solution code:
def main():
  import sys
  input=sys.stdin.buffer.readline
  n=int(input())+1
  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:
        s|=data[l]
        l+=1
      if r&1:
        r-=1
        s|=data[r]
      l//=2
      r//=2
    return bin(s).count('1')
  for i,c in enumerate(input()[:-1],n):data[i]=2**(c-97)
  for i in range(n-1,0,-1):data[i]=data[i*2]|data[i-~i]
  s=[]
  for _ in range(int(input())):
    q,a,b=input().split()
    if q[0]>49:s+=query(int(a)-1,int(b)),
    else:update(int(a)-1,2**(b[0]-97))
  print('\n'.join(map(str,s)))
main()

Submission status: Accepted

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


class SegmentTree():
    def __init__(self, S):
        self.size = 19
        self.array = [set()] * (2**(self.size + 1) - 1)
        for i, c in enumerate(S):
            self.array[i + 2**self.size - 1] = {c}
        for i in range(2**self.size - 1)[::-1]:
            self.array[i] = self.array[2 * i + 1] | self.array[2 * i + 2]

    def subquery(self, l, r, k, i, j):
        # 区間[i,j)の中で区間[l,r)の文字列の集合を返す
        if j <= l or r <= i:
            return set()
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_set = self.subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_set = self.subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return l_set | r_set

    def query(self, l, r):
        # [l,r)に含まれる文字の種類数
        return len(self.subquery(l, r, 0, 0, 2**self.size))

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = {c}
        while tmp > 0:
            tmp = (tmp - 1) // 2
            self.array[tmp] = self.array[2 * tmp + 1] | self.array[2 * tmp + 2]


def main():
    N = int(input())
    S = [ord(_) - 97 for _ in list(input())]
    Q = int(input())
    tree = SegmentTree(S)
    for q in range(Q):
        t, i, c = input().split()
        if t == '1':
            i = int(i) - 1
            tree.update(i, ord(c) - 97)
        else:
            l, r = int(i) - 1, int(c)
            print(tree.query(l, r))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
import copy
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

n=int(input())
s=input()
q=int(input())
qlst=[list(input().split()) for i in range(q)]

lst=[0]*n

for i in range(n):
    lst[i] = pow(2,(ord(s[i])-ord("a")))

# print(lst)
#####segfunc######
# def segfunc(x,y):
#     return x|y
 
# def init(init_val): #渡されたリストでsegを初期化
#     #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): #segの要素kをxに変更(セグ木全体の更新)
#     k += num-1
#     seg[k] = x
#     while k:
#         k = (k-1)//2
#         seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
# def query(p,q): #区間[p,q)での、segfuncに準じた値を返す
#     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
 
# #####単位元######
# """
# 最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
# 　　和のセグ木 → 0　(上の単位元の説明を参照)
# 　　積のセグ木 → 1　(上の単位元の説明を参照)
# 　　gcdのセグ木 → 0　(gcdを更新しない値は0)
# """
# ide_ele = 0
 
# #num:n以上の最小の2のべき乗
# num =2**(n-1).bit_length()
# seg=[ide_ele]*2*num #単位元の配列(計算結果に影響を及ぼさない配列)を作成
 
class SegTree:
    def __init__(self, init_val, i_e):
        self.ide_ele=i_e
        self.num=2**(len(init_val)-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num

        #set_val
        for i in range(len(init_val)):
            self.seg[i+self.num-1]=init_val[i]
        #built
        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 segfunc(self, x, y):
        return x|y
    
    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

seg=SegTree(lst, 0)

def judge(u):
    res = 0
    for i in range(27):
        if u>>i & 1:
            res += 1
    return res
 
for i in range(q):
    t,x,y = qlst[i]
    if t == "1":
        seg.update(int(x)-1,pow(2,ord(y)-ord("a")))
    else:
        print(judge(seg.query(int(x)-1,int(y))))

Submission status: Accepted

Solution code:
class SegmentTree1():
    """
    1-indexed Segment Tree
    """
    def __init__(self, n_, ele_id, op_func):
        self.n = 1 << (n_ - 1).bit_length()  # size
        self.data = [ele_id] * (2 * self.n)  # binary tree (1-indexed)
        self.ele_id = ele_id  # identity element
        self.op_func = op_func  # binary operation of monoid

    def __getitem__(self, i):
        return self.data[i + self.n]

    def build(self, data_init):
        for i in range(len(data_init)):
            self.data[i + self.n] = data_init[i]  # set data in leaf
        for i in reversed(range(self.n)):
            self.data[i] = self.op_func(self.data[2 * i], self.data[2 * i + 1])

    def update(self, i, x):
        # change i-th element to x (i : 0-indexed)
        i += self.n
        self.data[i] = x
        while i > 1:
            i = i >> 1  # go to parenet-node
            self.data[i] = self.op_func(self.data[2 * i], self.data[2 * i + 1])

    def query(self, l, r):
        # query for interval [l, r) (l, r : 0-indexed)
        l += self.n
        r += self.n
        ret = self.ele_id
        while l < r:
            if l & 1:  # right child
                ret = self.op_func(ret, self.data[l])
                l += 1
            if r & 1:  # right child
                r -= 1
                ret = self.op_func(ret, self.data[r])
            # go to parent-nodes
            l = l >> 1
            r = r >> 1
        return ret


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

# construct segment tree
ele_id = 0
op_func = lambda a, b: a | b
st_bitset = SegmentTree1(n, ele_id, op_func)
st_bitset.build([1 << (ord(si) - ord('a')) for si in s])

# query
q = int(input())
for _ in range(q):
    k, a, b = input().split()
    k = int(k)
    a = int(a)
    if k == 1:
        b = ord(b) - ord('a')
        a -= 1
        # type1: update
        st_bitset.update(a, 1 << b)
    else:
        # type2: calc
        b = int(b)
        a -= 1
        cnt = bin(st_bitset.query(a, b)).count('1')
        print(cnt)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
import copy
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

n=int(input())
s=input()
q=int(input())
qlst=[list(input().split()) for i in range(q)]

lst=[0]*n

for i in range(n):
    lst[i] = pow(2,(ord(s[i])-ord("a")))

# print(lst)
#####segfunc######
def segfunc(x,y):
    return x|y
 
def init(init_val): #渡されたリストでsegを初期化
    #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): #segの要素kをxに変更(セグ木全体の更新)
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q): #区間[p,q)での、segfuncに準じた値を返す
    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
 
#####単位元######
"""
最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
　　和のセグ木 → 0　(上の単位元の説明を参照)
　　積のセグ木 → 1　(上の単位元の説明を参照)
　　gcdのセグ木 → 0　(gcdを更新しない値は0)
"""
ide_ele = 0
 
#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num #単位元の配列(計算結果に影響を及ぼさない配列)を作成
 
init(lst)
# print(seg)
def judge(u):
    res = 0
    for i in range(27):
        if u>>i & 1:
            res += 1
    return res
 
for i in range(q):
    t,x,y = qlst[i]
    if t == "1":
        update(int(x)-1,pow(2,ord(y)-ord("a")))
    else:
        print(judge(query(int(x)-1,int(y))))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.buffer.readline
n=int(input())+1
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:
      s|=data[l]
      l+=1
    if r&1:
      r-=1
      s|=data[r]
    l//=2
    r//=2
  return sum(map(int,bin(s)[2:]))
for i,c in enumerate(input()[:-1],n):data[i]=2**(c-97)
for i in range(n-1,0,-1):data[i]=data[i*2]|data[i-~i]
for _ in range(int(input())):
  q,a,b=input().split()
  if q[0]>49:print(query(int(a)-1,int(b)))
  else:update(int(a)-1,2**(b[0]-97))

Submission status: Accepted

Solution code:
import numpy as np

def popcount(n):
    return bin(n).count("1")
d = {c:(1 << (ord(c)-ord('a'))) for c in 'abcdefghijklmnopqrstuvwxyz'}

class SegmentTree:
    def __init__(self, A):
        N = len(A)
        n = (N-1).bit_length()
        self.N = 1 << n
        self.Seg = [0 for i in range(2*self.N)]
        for i in range(N):
            self.Seg[self.N+i-1] = d[A[i]]
        for i in range(0, self.N-1)[::-1]:
            self.Seg[i] = self.merge(self.Seg[i*2+1], self.Seg[i*2+2])

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

    def update(self, k, x):
        i = self.N+k-1
        self.Seg[i] = d[x]
        while i > 0:
            i = (i-1)//2
            self.Seg[i] = self.merge(self.Seg[i*2+1], self.Seg[i*2+2])

    def query(self, a, b):
        return self.query_(a, b, 0, 0, self.N)

    def query_(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.Seg[k]
        vl = self.query_(a, b, 2*k+1, l, (l+r)//2)
        vr = self.query_(a, b, 2*k+2, (l+r)//2, r)
        return self.merge(vl, vr)

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

def main():
    N = int(input())
    S = input()
    Q = int(input())
    Seg = SegmentTree(S)

    for _ in range(Q):
        q, i, c = input().split()
        if q == '1':
            i = int(i)-1
            Seg.update(i, c)
        else:
            l, r = int(i), int(c)
            print(popcount(Seg.query(l-1, r)))
main()

Submission status: Accepted

Solution code:
NN = 19
X = [0] * ((1<<NN+1)-1)
 
def popcount(x):
    x -= (x >> 1) & 0x55555555
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x += x >> 8
    x += x >> 16
    return x & 0x3f

def update(a, x):
    i = (1<<NN) - 1 + a
    X[i] = x
    while i:
        i = (i-1) // 2
        X[i] = X[2*i+1] | X[2*i+2]

def rangeor(a, b):
    l = a + (1<<NN)
    r = b + (1<<NN)
    x = 0
    while l < r:
        if l%2:
            x |= X[l-1]
            l += 1
        if r%2:
            r -= 1
            x |= X[r-1]
        l >>= 1
        r >>= 1
    return x

N = int(input())
A = [ord(a) - 97 for a in input()]
for i, a in enumerate(A):
    X[(1<<NN) + i] = 1 << a
for i in range((1<<NN)-1)[::-1]:
    X[i] = X[i*2+1] | X[i*2+2]

Q = int(input())
for _ in range(Q):
    a, b, c = input().rstrip().split()
    if a == "1":
        b = int(b)
        c = ord(c) - 97
        update(b, 1<<c)
    else:
        b, c = int(b), int(c)
        print(popcount(rangeor(b, c+1)))

Submission status: Accepted

Solution code:
import numpy as np

def count(n):
    return bin(n).count("1")

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

def update(Seg, k, x):
    k += len(Seg)//2
    Seg[k] = x
    while k > 0:
        k = (k - 1) // 2
        Seg[k] = Seg[k*2+1]|Seg[k*2+2]

d = {c:(1 << (ord(c)-97)) for c in 'abcdefghijklmnopqrstuvwxyz'}

class SegmentTree:
    def __init__(self, A):
        N = len(A)
        n = (N-1).bit_length()
        self.N = 1 << n
        self.Seg = [0 for i in range(2*self.N)]
        #for i in range(N): self.update(i, A[i])
        if True:
            for i in range(N):
                self.Seg[self.N+i-1] = d[A[i]]
            for i in range(0,self.N-2)[::-1]:
                self.Seg[i] = self.Seg[i*2+1] | self.Seg[i*2+2]

    def update(self, k, x):
        i = self.N+k-1
        self.Seg[i] = d[x]
        while i > 0:
            i = (i-1)//2
            self.Seg[i] = self.Seg[i*2+1]|self.Seg[i*2+2]
    def merge(self, x, y):
        return x | y

    def query(self, a, b):
        return self.query_(a, b, 0, 0, self.N)

    def query_(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.Seg[k]
        vl = self.query_(a, b, 2*k+1, l, (l+r)//2)
        vr = self.query_(a, b, 2*k+2, (l+r)//2, r)
        return merge(vl, vr)

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    S = input()[:-1]
    Q = int(input())
    Seg = SegmentTree(S)

    for _ in range(Q):
        q, i, c = input().split()
        if q == '1':
            i = int(i)-1
            Seg.update(i, c)
        else:
            l, r = int(i), int(c)
            print(count(Seg.query(l-1, r)))
main()

Submission status: Accepted

Solution code:
from operator import add, mul, sub, or_


class SegmentTree:
    '''
    1-indexd セグメント木
    values : 値の配列
    op : 区間に対する関数
    ie : 初期値
    '''

    def __init__(self, values, op, ie):
        self.values = values
        vlen = len(values)
        self.op = op
        self.size = 2 ** (vlen-1).bit_length()
        self.tree = [ie]*self.size + self.values + [ie]*(self.size-vlen)
        self.ie = ie

        for i in range(self.size-1, 0, -1):
            self.tree[i] = self.op(self.tree[i*2], self.tree[i*2+1])

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

    def query(self, l, r):
        l += self.size
        r += self.size
        ret = self.ie
        while l < r:
            if l & 1:
                ret = self.op(ret, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.op(ret, self.tree[r])
            l //= 2
            r //= 2
        return ret


def bit(c):
    return 1 << (ord(c)-ord('a'))


def bitcount(c):
    b = bin(c)[2:]
    return b.count("1")


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

seg = SegmentTree([bit(c) for c in s], or_, 0)
for q in range(Q):
    i, l, r = input().split()
    if i == "1":
        l = int(l)-1
        seg.update(l, bit(r))
    else:
        l = int(l)-1
        r = int(r)-1
        v = seg.query(l, r+1)
        print(bitcount(v))