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:
from collections import deque

class SegmentTree():
    def __init__(self,n,ide_ele,merge_func):
        self.n=n
        self.ide_ele=ide_ele
        self.merge_func=merge_func
        self.val=[0 for i in range(1<<n)]
        self.merge=[0 for i in range(1<<n)]
        self.parent=[-1 for i in range(1<<n)]
        deq=deque([1<<(n-1)])
        while deq:
            v=deq.popleft()
            if not v&1:
                gap=(v&-v)//2
                self.parent[v-gap]=v
                deq.append(v-gap)
                self.parent[v+gap]=v
                deq.append(v+gap)


    def update(self,id,x):
        self.val[id]=x
        pos=id+1
        while pos!=-1:
            if pos&1:
                self.merge[pos-1]=self.val[pos-1]
            else:
                gap=(pos&-pos)//2
                self.merge[pos-1]=self.merge_func(self.val[pos-1],self.merge[pos+gap-1],self.merge[pos-gap-1])
            pos=self.parent[pos]

    def cnt(self,k):
        lsb=(k)&(-k)
        return (lsb<<1)-1

    def lower_kth_merge(self,nd,k):
        res=self.ide_ele
        id=nd
        if k==-1:
            return res
        while True:
            if not id%2:
                gap=((id)&(-id))//2
                l=id-gap
                r=id+gap
                cnt=self.cnt(l)
                if cnt<k:
                    k-=cnt+1
                    res=self.merge_func(res,self.val[id-1],self.merge[l-1])
                    id=r
                elif cnt==k:
                    res=self.merge_func(res,self.val[id-1],self.merge[l-1])
                    return res
                else:
                    id=l
            else:
                res=self.merge_func(res,self.val[id-1])
                return res

    def upper_kth_merge(self,nd,k):
        res=self.ide_ele
        id=nd
        if k==-1:
            return res
        while True:
            if not id%2:
                gap=((id)&(-id))//2
                l=id-gap
                r=id+gap
                cnt=self.cnt(r)
                if cnt<k:
                    k-=cnt+1
                    res=self.merge_func(res,self.val[id-1],self.merge[r-1])
                    id=l
                elif cnt==k:
                    res=self.merge_func(res,self.val[id-1],self.merge[r-1])
                    return res
                else:
                    id=r
            else:
                res=self.merge_func(res,self.val[id-1])
                return res

    def query(self,l,r):
        id=1<<(self.n-1)
        while True:
            if id-1<l:
                id+=((id)&(-id))//2
            elif id-1>r:
                id-=((id)&(-id))//2
            else:
                res=self.val[id-1]
                if id%2:
                    return res
                gap=((id)&(-id))//2
                L,R=id-gap,id+gap
                #print(l,r,id,L,R)
                left=self.upper_kth_merge(L,id-1-l-1)
                right=self.lower_kth_merge(R,r-id)
                return self.merge_func(res,left,right)

ide_ele=0

def seg_func(*args):
    res=ide_ele
    for val in args:
        res|=val
    return res

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

import sys

input=sys.stdin.readline

N=int(input())
S=input().rstrip()

test=SegmentTree(19,ide_ele,seg_func)
for i in range(N):
    val=ord(S[i])-97
    test.update(i,1<<val)

for _ in range(int(input())):
    t,l,r=input().split()
    t,l=int(t),int(l)
    if t==1:
        val=ord(r)-97
        test.update(l-1,1<<val)
    else:
        r=int(r)
        res=test.query(l-1,r-1)
        print(popcount(res))

Submission status: Accepted

Solution code:
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[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のべき乗
n=int(input())
S=input()
Q=int(input())

num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
alphabet={key:alphabetlist.index(key)  for key in alphabetlist}

data=[0 for i in range(0,n)]
for i in range(0,n):
    data[i]=2**(alphabet[S[i]])

init(data)

ans=[]
for i in range(0,Q):
    q,a,b=input().split()
    if q=='1':
        update(int(a)-1,2**(alphabet[b]))
    else:
        a=int(a)
        b=int(b)
        ans.append(query(a-1,b))

for i in range(len(ans)):
    x=ans[i]
    print(bin(x).count('1'))

Submission status: Accepted

Solution code:
class SegmentTree():
    def __init__(self,n,ide_ele,merge_func):
        self.n=n
        self.ide_ele=ide_ele
        self.merge_func=merge_func
        self.val=[0 for i in range(1<<n)]
        self.merge=[0 for i in range(1<<n)]

    def update(self,id,x):
        stack=[]
        pos=1<<(self.n-1)
        while pos-1!=id:
            stack.append(pos)
            if pos-1>id:
                pos-=((pos)&(-pos))//2
            else:
                pos+=((pos)&(-pos))//2

        stack.append(pos)
        self.val[pos-1]=x
        for pos in stack[::-1]:
            if pos%2:
                self.merge[pos-1]=self.val[pos-1]
            else:
                gap=((pos)&(-pos))//2
                r=pos+gap
                l=pos-gap
                self.merge[pos-1]=self.merge_func(self.val[pos-1],self.merge[r-1],self.merge[l-1])

    def cnt(self,k):
        lsb=(k)&(-k)
        return (lsb<<1)-1

    def lower_kth_merge(self,nd,k):
        res=self.ide_ele
        id=nd
        if k==-1:
            return res
        while True:
            if not id%2:
                gap=((id)&(-id))//2
                l=id-gap
                r=id+gap
                cnt=self.cnt(l)
                if cnt<k:
                    k-=cnt+1
                    res=self.merge_func(res,self.val[id-1],self.merge[l-1])
                    id=r
                elif cnt==k:
                    res=self.merge_func(res,self.val[id-1],self.merge[l-1])
                    return res
                else:
                    id=l
            else:
                res=self.merge_func(res,self.val[id-1])
                return res

    def upper_kth_merge(self,nd,k):
        res=self.ide_ele
        id=nd
        if k==-1:
            return res
        while True:
            if not id%2:
                gap=((id)&(-id))//2
                l=id-gap
                r=id+gap
                cnt=self.cnt(r)
                if cnt<k:
                    k-=cnt+1
                    res=self.merge_func(res,self.val[id-1],self.merge[r-1])
                    id=l
                elif cnt==k:
                    res=self.merge_func(res,self.val[id-1],self.merge[r-1])
                    return res
                else:
                    id=r
            else:
                res=self.merge_func(res,self.val[id-1])
                return res

    def query(self,l,r):
        id=1<<(self.n-1)
        while True:
            if id-1<l:
                id+=((id)&(-id))//2
            elif id-1>r:
                id-=((id)&(-id))//2
            else:
                res=self.val[id-1]
                if id%2:
                    return res
                gap=((id)&(-id))//2
                L,R=id-gap,id+gap
                #print(l,r,id,L,R)
                left=self.upper_kth_merge(L,id-1-l-1)
                right=self.lower_kth_merge(R,r-id)
                return self.merge_func(res,left,right)

ide_ele=0

def seg_func(*args):
    res=ide_ele
    for val in args:
        res|=val
    return res

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

import sys

input=sys.stdin.readline

N=int(input())
S=input().rstrip()

test=SegmentTree(19,ide_ele,seg_func)
for i in range(N):
    val=ord(S[i])-97
    test.update(i,1<<val)

for _ in range(int(input())):
    t,l,r=input().split()
    t,l=int(t),int(l)
    if t==1:
        val=ord(r)-97
        test.update(l-1,1<<val)
    else:
        r=int(r)
        res=test.query(l-1,r-1)
        print(popcount(res))

Submission status: Accepted

Solution code:
class SegmentTree():
    def __init__(self, size):
        self.size = 2**((size-1).bit_length())
        self.val = [0]*(self.size*2)
    
    def update(self, i, x):
        i += self.size
        self.val[i] = x
        
        while i > 0:
            i = i >> 1
            self.val[i] = self.val[2*i] + self.val[2*i+1]
    
    def query(self, l, r):
        l += self.size
        r += self.size

        l_sum = 0
        r_sum = 0

        while l < r:
            if l & 1:
                l_sum += self.val[l]
                l += 1
            l = l >> 1

            if r & 1:
                r -= 1
                r_sum += self.val[r]
            r = r >> 1

        return l_sum + r_sum

def convertAlphabetToNumber(s):
    return ord(s) - ord('a')

N = int(input())
S = input()
Q = int(input())
query = [input().split() for i in range(Q)]

for i in range(Q):
    query[i][0] = int(query[i][0])
    query[i][1] = int(query[i][1]) - 1
    if query[i][0] == 2:
        query[i][2] = int(query[i][2]) - 1

alphabet_position = [SegmentTree(N) for i in range(28)]

for i in range(N):
    num = convertAlphabetToNumber(S[i])
    alphabet_position[num].update(i, 1)

for i in range(Q):
    if query[i][0] == 1:
        for j in range(28):
            if j == convertAlphabetToNumber(query[i][2]):
                alphabet_position[j].update(query[i][1], 1)
            else:
                alphabet_position[j].update(query[i][1], 0)
    else:
        cnt = 0
        for j in range(28):
            if alphabet_position[j].query(query[i][1], query[i][2] + 1) > 0:
                cnt += 1
        print(cnt)

Submission status: Accepted

Solution code:
import sys

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


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

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

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

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

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


def resolve():
    n = int(input())
    S = list(input().rstrip())
    q = int(input())

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

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
import numpy as np

def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


# >>> binary indexed tree >>>
# 必要な要素数+1 の長さの ndarray の 1 要素目以降を使う
def bitify(arr):
    for i in range(1, len(arr)-1):
        arr[i + (i & -i)] += arr[i]
def bit_sum(bit, i):  # [bit_sum, "i8(i8[:],i8)"],
    # (0, i]
    res = 0
    while i:
        res += bit[i]
        i -= i & -i
    return res
def bit_add(bit, i, val):  # [bit_add, "void(i8[:],i8,i8)"],
    n = len(bit)
    while i < n:
        bit[i] += val
        i += i & -i
# <<< binary indexed tree <<<

numba_compile([
    [bitify, "void(i8[:])"],
    [bit_sum, "i8(i8[:],i8)"],
    [bit_add, "void(i8[:],i8,i8)"],
])


def main():
    N = int(sys.stdin.buffer.readline())
    S = np.frombuffer(sys.stdin.buffer.readline()[:-1], dtype=np.uint8).astype(np.int64) - 97
    Q = int(sys.stdin.buffer.readline())
    bits = np.zeros((26, (1<<19)+1), dtype=np.int64)
    bits[S, np.arange(1, N+1)] = 1
    for i in range(26):
        bitify(bits[i])
    Ans = []
    for t, i, c in zip(*[iter(sys.stdin.buffer.read().split())]*3):
        if t == b"1":
            i = int(i)
            c = ord(c)-97
            c_old = S[i-1]
            S[i-1] = c
            bit_add(bits[c_old], i, -1)
            bit_add(bits[c], i, 1)
        else:
            l, r = int(i), int(c)
            ans = 0
            for bit in bits:
                ans += bool(bit_sum(bit, r)-bit_sum(bit, l-1))
            Ans.append(ans)
    print("\n".join(map(str, Ans)))

main()

Submission status: Accepted

Solution code:
class SegTree:
    X_unit = set()
    X_f = lambda x,y,z:y|z

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)

N = int(input())
S = list(input())
S = [set(i) for i in S]
Q = int(input())
Tree = SegTree(N)
Tree.build(S)

for i in range(Q):
    a,b,c = input().split()
    if a == '1':
        i = int(b)-1
        c = set(c)
        Tree.set_val(i,c)
    else:
        l = int(b)-1
        r = int(c)
        print(len(Tree.fold(l,r)))

Submission status: Accepted

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT:
  def __init__(self, n):
    self.n = n
    self.bit = [0]*(n+1)
    self.el = [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):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.bit[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i-1)
  def lower_bound(self,x):
    w = i = 0
    k = 1<<((self.n).bit_length())
    while k:
      if i+k <= self.n and w + self.bit[i+k] < x:
        w += self.bit[i+k]
        i += k
      k >>= 1
    return i+1

def alph_to_num(s):
  return ord(s)-ord('a')

def solve():
  N = int(input())
  S = list(map(alph_to_num,list(input())))
  Q = int(input())
  bits = [BIT(N) for _ in range(26)]
  for i in range(N):
    bits[S[i]].add(i+1,1)
  ans = []
  for _ in range(Q):
    x,y,z = input().split()
    y = int(y)
    if x=='1':
      z = alph_to_num(z)
      bits[S[y-1]].add(y,-1)
      S[y-1] = z
      bits[z].add(y,1)
    if x=='2':
      z = int(z)
      ans.append(sum([bits[i].get(y,z)>0 for i in range(26)]))
  return ans
print(*solve(),sep='\n')

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect, insort, bisect_left
n = int(input())
s = list(input())
q = int(input())
d = defaultdict(list)
for i in range(n):
    d[s[i]] += [i]
for _ in range(q):
    t, i, c = input().split()
    t, i = int(t), int(i) - 1
    if t == 1:
        if s[i] == c:
            continue
        d[s[i]].pop(bisect(d[s[i]], i) - 1)
        s[i] = c
        insort(d[c], i)
    else:
        res = 0
        c = int(c) - 1
        for j in d.values():
            if bisect(j, c) - bisect_left(j, i):
                res += 1
        print(res)

Submission status: Accepted

Solution code:
import bisect  # 配列二分法
from collections import defaultdict

N = int(input())
S = [*input()]
Q = int(input())
d = defaultdict(list)

# 各アルファベットの出現場所を記録
for i, c in enumerate(S):
    d[c] += [i]

# この時点でどのアルファベットについてもソート済み
# print(d)

for _ in range(Q):
    q, y, z = input().split()

    if q == '1':
        i = int(y) - 1  # 文字の変更位置

        if S[i] == z: continue  # 同じ文字の場合は処理終了

        # 削除 O(N)
        b = bisect.bisect(d[S[i]], i)  # 2分法で i の出現位置を(log N)で探す
        d[S[i]].pop(b - 1)  # 削除

        # 追加 O(N) かかる？
        S[i] = z
        bisect.insort(d[z], i) 

    else:
        left = int(y) - 1
        right = int(z) - 1

        count = 0
        for v in d.values():
            count += 1 if bisect.bisect(v, right) - bisect.bisect_left(v, left) > 0 else 0

        print(count)

Submission status: Accepted

Solution code:
class BinaryIndexedTree():
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
 
    def initialize(self, seq):
        for i, x in enumerate(seq[1:], 1):
            self.tree[i] += x
            j = i + (i & (-i))
            if j < self.size:
                self.tree[j] += self.tree[i]
 
    def __repr__(self):
        return self.tree.__repr__()
 
    def get_sum(self, i):
        s = 0
        while i:
            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
 
    def find_kth_element(self, k):
        x, sx = 0, 0
        dx = (1 << self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= self.size:
                continue
            y = x + dx
            sy = sx + self.tree[y]
            if sy < k:
                x, sx = y, sy
        return x + 1



n = int(input())
s = ["!"]+list(input())
q = int(input())
bit = [BinaryIndexedTree(n+1) for i in range(26)]

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

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

Submission status: Accepted

Solution code:

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

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

    def sumup(self, i):
        # Sum a[1]~a[i]
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & -i
        return res

    def query(self, i, j):
        # Sum a[i]~a[j]
        return self.sumup(j) - self.sumup(i - 1)


N = int(input())
S = list(input())
Q = int(input())
X = [input().split() for _ in range(Q)]

MAX = 5 * 10 ** 5 + 2
d = dict()
for c in range(ord("a"), ord("z") + 1):
    s = chr(c)
    d[s] = BIT(MAX)

for i, v in enumerate(S):
    d[v].add(i + 1, 1)

for q, *x in X:
    if q == "1":
        i = int(x[0])
        c = x[1]

        # Delete index
        d[S[i - 1]].add(i, -1)

        # Add index
        d[c].add(i, 1)
        S[i - 1] = c
    else:
        l, r = map(int, x)

        ans = 0
        for c in range(ord("a"), ord("z") + 1):
            ans += int(d[chr(c)].query(l, r) > 0)
        print(ans)

Submission status: Accepted

Solution code:
class BIT:
  def __init__(self,n):
    self.s = [0]*(n+1)
    self.n = n
  
  def add(self,val,idx):
    while idx < self.n+1:
      self.s[idx] = self.s[idx] + val
      idx += idx&(-idx)
    return
  
  def get(self,idx):
    res = 0
    while idx > 0:
      res = res + self.s[idx]
      idx -= idx&(-idx)
    return res
 
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
 
n = int(input())
S = [ord(s) - ord('a') for s in input()[:-1]]
 
bits = [BIT(n) for i in range(26)]
 
for i,s in enumerate(S):
  bits[s].add(1,i+1)
 
Q = int(input())
ans = []
for _ in range(Q):  
  flag,x,y = input().split()

  if flag == "1":
    i = int(x)
    c = ord(y) - ord('a')
    bits[S[i-1]].add(-1,i)
    bits[c].add(1,i)
    S[i-1] = c
  else:
    l = int(x)
    r = int(y)
    res = 0
    for i in range(26):
      res += (bits[i].get(r) > bits[i].get(l-1))
    ans.append(str(res))

print("\n".join(ans))

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


def main():
    n = int(ipt())
    s = input()
    q = int(ipt())
    alp = "abcdefghijklmnopqrstuvwxyz"
    sn = [2**(alp.find(i)) for i in s]

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

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

    ST = SegTree(sn,segfunc,0)
    for i in range(q):
        nm = tuple(input().split())
        if nm[0] == "1":
            ST.update(int(nm[1])-1,2**(alp.find(nm[2])))
        else:
            print(popcnt(ST.query(int(nm[1])-1,int(nm[2]))))


    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy

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


def update(k, cs):
    ls = s[k]
    if ls == cs:
        return
    k += num-1
    seg[cs][k] = 1
    seg[ls][k] = 0
    while k:
        k = (k-1)//2
        seg[ls][k] = seg[ls][k*2+1] | seg[ls][k*2+2]
        seg[cs][k] = seg[cs][k*2+1] | seg[cs][k*2+2]


def query(pp, qq): # pからq-1までの最大値
    pp += num-1
    qq += num-2
    total = 0
    for j in range(26):
        p = copy.deepcopy(pp)
        q = copy.deepcopy(qq)
        res = 0
        while q - p > 1:
            if res == 1:
                break
            if p&1 == 0:
                res = res | seg[j][p]
            if q&1 == 1:
                res = res | seg[j][q]
                q -= 1
            p = p//2
            q = (q-1)//2
        if q - p > 1:
            total += res
            continue
        if p == q:
            res = res | seg[j][p]
        else:
            res = res | seg[j][p] | seg[j][q]
        total += res
    return total


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

for i in range(n):
    s[i] = ord(s[i]) - 97
#num:n以上の最小の2のべき乗
num = 2**(n-1).bit_length()
seg = [[0]*(2*num) for i in range(26)]
init(s)
for i in range(q):
    cq = list(input().split())
    if cq[0] == '1':
        cn, cs = int(cq[1]) - 1, ord(cq[2]) - 97
        update(cn, cs)
        s[cn] = cs
    if cq[0] == '2':
        p, q = int(cq[1]) - 1, int(cq[2])
        print(query(p, q))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()


class SegTree:
    X_unit = 0

    def __init__(self, N, X_f=min):
        self.N = N
        self.X = [self.X_unit] * (N + N)
        self.X_f = X_f

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)


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


def main():
    N = int(input())
    S = input()
    S = list(map(lambda c: 2**(ord(c) - ord('a')), list(S)))
    Q = int(input())
    seg = SegTree(N, orr)
    seg.build(S)
    for _ in range(Q):
        num, x, y = input().split()
        if num == '1':
            seg.set_val(int(x)-1, 2**(ord(y) - ord('a')))
        else:
            bits=seg.fold(int(x)-1, int(y))
            print(sum(map(int, list(bin(bits))[2:])))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def solve():
    ordA = ord('a')

    N = int(input())
    Ss = input().rstrip()
    Q = int(input())
    querys = [tuple(input().split()) for _ in range(Q)]

    idEle = 0
    def _binOpe(x, y):
        return x | y
    def makeSegTree(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [idEle] * (2*numPow2)
        return data, numPow2
    def setInit(As):
        for iST, A in enumerate(As, numPow2):
            data[iST] = A
        for iST in reversed(range(1, numPow2)):
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def _update1(iA, A):
        iST = iA + numPow2
        data[iST] = A
    def update(iA, A):
        _update1(iA, A)
        iST = iA + numPow2
        while iST > 1:
            iST >>= 1
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def getValue(iSt, iEn):
        L = iSt + numPow2
        R = iEn + numPow2
        ans = idEle
        while L < R:
            if L & 1:
                ans = _binOpe(ans, data[L])
                L += 1
            if R & 1:
                R -= 1
                ans = _binOpe(ans, data[R])
            L >>= 1
            R >>= 1
        return ans

    data, numPow2 = makeSegTree(N)
    As = [(1<<(ord(S)-ordA)) for S in Ss]
    setInit(As)

    anss = []
    for tp, *vs in querys:
        if tp == '1':
            i, c = vs
            i = int(i)
            update(i-1, 1<<(ord(c)-ordA))
        else:
            L, R = vs
            L, R = int(L), int(R)
            v = getValue(L-1, R)
            anss.append(bin(v).count('1'))

    print('\n'.join(map(str, anss)))


solve()