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,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()

    R = 2**(N.bit_length())
    st = [0] * (R*2)

    def update(i,s):
        x = 2 ** (ord(s) - ord('a'))
        i += R-1
        st[i] = x
        while i > 0:
            i = (i-1) // 2
            st[i] = st[i*2+1] | st[i*2+2]

    def query(l,r):
        l += R-1
        r += R-2
        ret = 0

        while l+1 < r:
            if l % 2 == 0:
                ret |= st[l]
            if r % 2 == 1:
                ret |= st[r]
                r -= 1
            l = l // 2
            r = (r-1) // 2
        if l == r:
            ret |= st[l]
        else:
            ret |= st[l] | st[r]

        return ret

    for i,s in enumerate(sys.stdin.readline().rstrip()):
        update(i+1,s)
    Q = NI()
    for _ in range(Q):
        c,a,b = sys.stdin.readline().split()
        if c == '1':
            update(int(a),b)
        else:
            ret = query(int(a),int(b)+1)
            cnt = 0
            b = 1
            for i in range(26):
                cnt += (b & ret) > 0
                b <<= 1
            print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()

    R = 2**(N.bit_length())
    st = [0] * (R*2)

    def update(i,s):
        x = 2 ** (ord(s) - ord('a'))
        i += R-1
        st[i] = x
        while i > 0:
            i = (i-1) // 2
            st[i] = st[i*2+1] | st[i*2+2]

    def query(a,b,n,l,r):
        ret = 0
        if a <= l and r <= b: return st[n]
        if a < r and b > l:
            vl = query(a,b,n*2+1,l,(l+r)//2)
            vr = query(a,b,n*2+2,(l+r)//2,r)
            ret = vl | vr
        return ret

    for i,s in enumerate(sys.stdin.readline().rstrip()):
        update(i+1,s)
    Q = NI()
    for _ in range(Q):
        c,a,b = sys.stdin.readline().split()
        if c == '1':
            update(int(a),b)
        else:
            ret = query(int(a),int(b)+1,0,0,R)
            cnt = 0
            b = 1
            for i in range(26):
                cnt += (b & ret) > 0
                b <<= 1
            print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_right
from bisect import bisect_left

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

ind_list = [[] for _ in range(26)]

for i, x in enumerate(s):
    ind_list[ord(x)-97].append(i)

for _ in range(q):
    _type, val1, val2 = input().split()
    if _type == '1':
        i = int(val1)-1
        c = val2
        if s[i] == c:
            continue
        ind_list[ord(s[i])-97].remove(i)
        p = bisect_right(ind_list[ord(c)-97], i)
        ind_list[ord(c)-97].insert(p, i)
        s[i] = c
    elif _type == '2':
        l = int(val1)-1
        r = int(val2)-1
        ans = 0
        for i in range(26):
            if bisect_right(ind_list[i], r) - bisect_left(ind_list[i], l) > 0:
                ans += 1
        print(ans)
    else:
        print('Exception caught!')
        exit()

Submission status: Accepted

Solution code:
import bisect
N=input()
S=list(input())
alphabet=[[] for _ in range(26)]
for i,s in enumerate(S):
    alphabet[ord(s)-ord('a')].append(i)
Q=int(input())
for _ in range(Q):
    Type,A,B=input().split()
    if Type=="1":
        A=int(A)
        s=S[A-1]
        if s==B:
            continue
        o=ord(s)-ord("a")
        alphabet[o].pop(bisect.bisect_left(alphabet[o],A-1))
        index=bisect.bisect(alphabet[ord(B)-ord("a")],A-1)
        alphabet[ord(B)-ord("a")].insert(index,A-1)
        S[A-1]=B
    else:
        A=int(A)
        B=int(B)
        ans=0
        for i in range(26):
            indexL=bisect.bisect_left(alphabet[i],A-1)
            #indexR=bisect.bisect_right(alphabet[i],B-1)
            #ans+=(indexL!=indexR)
            if indexL==len(alphabet[i]):
                continue
            ans+=(alphabet[i][indexL]<=B-1)
        print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

n = int(input())
s = list(input())
q = int(input())
query = [input() for _ in range(q)]

p = [[] for _ in range(26)]

for i, x in enumerate(s):
    p[ord(x) - ord('a')].append(i)

for x in query:
    a, b, c = x.split()
    #print(c)
    if a == '1':
        b = int(b) - 1
        if s[b] == c:
            continue
        d = ord(s[b]) - ord('a')
        e = ord(c) - ord('a')
        temp = bisect_left(p[d], b)
        p[d].pop(temp)
        temp = bisect_left(p[e], b)
        p[e].insert(temp, b)
        s[b] = c
    else:
        b = int(b) - 1
        c = int(c) - 1
        #print(b, c)
        ans = 0
        for i in range(26):
            L = bisect_left(p[i], b)
            if L >= len(p[i]):
                continue
            if p[i][L] <= c:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
n = int(input())
S = list(input())
q = int(input())

import sys
input = sys.stdin.readline

alp = "abcdefghijklmnopqrstuvwxyz"
appr = {a:[] for a in alp}

import bisect

for i, a in enumerate(S):
  appr[a].append(i+1)
#print(appr)
for i in range(q):
  inputs = input().split()
  if inputs[0] == '1':
    c = int(inputs[1])
    a = inputs[2]
    if S[c-1]==a:
      continue
    else:
      old = S[c-1]
      S[c-1] = a
      del_idx = bisect.bisect_left(appr[old], c)
      del appr[old][del_idx]
      in_idx = bisect.bisect_left(appr[a], c)
      appr[a].insert(in_idx, c)
  else:
    l, r = map(int, inputs[1:])
    res = 0
    for a in appr:
      l_idx = bisect.bisect_left(appr[a], l)
      if l_idx<len(appr[a]):
        if appr[a][l_idx]<=r:
          res += 1
    print(res)
    
#print(appr)

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N = I()
S = list(ST())
Q = I()
bits=[[0]*(N+1) for _ in range(26)]

def ctoi(c): #アルファベットを0-25の数字に変換
    return ord(c)-97

def query(pos): #各文字について1-pos番目までの文字数をカウント
    ret = [0]*26
    for i in range(26):
        tmp = 0
        p = pos
        while p>0:
            tmp += bits[i][p]
            bit_len = p&(-p) #p&(-p)は1のたつ最小桁であり、今の区間の長さをあらわす
            p -= bit_len #つぎに足すべき塊の番号は、今の値から区間の長さを引くとでる
        ret[i] = tmp #アルファベットiの1-posまでの出現回数
    return ret

def update(pos, a, x): #a番目のアルファベットについてpos番目の要素の値を更新
    while pos <= N:
        bits[a][pos] += x
        pos += pos&(-pos)

for i in range(N):
    update(i+1, ctoi(S[i]),1)
for _ in range(Q):
    q = LST()
    if q[0]=='1':
        i = int(q[1])
        c = q[2]
        if S[i-1]==c:
            continue
        update(i, ctoi(S[i-1]), -1) #S[i-1]のi番目に1が立っているが、これを下ろして削除を表現
        #O(logN)で削除が完了
        update(i, ctoi(c), 1)
        S[i-1] = c
    else:
        ans = 0
        l = int(q[1])
        r = int(q[2])
        r_sum = query(r)
        l_sum = query(l-1)
        for i in range(26):
            if r_sum[i]-l_sum[i] > 0:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * n

    def sum(self, i):
        res = 0
        while i >= 0:
            res += self.data[i]
            i = (i & (i + 1)) - 1
        return res

    def add(self, i, val):
        while i < self.n:
            self.data[i] += val
            i |= i + 1


N = int(input())
bit = BIT(N + 1)
for i, c in enumerate(input()):
    ind = ord(c) - ord("a")
    bit.add(i + 1, 1 << (ind * 20))
Q = int(input())
for _ in range(Q):
    parts = input().split()
    if parts[0] == "1":
        ind = int(parts[1])
        nval = 1 << ((ord(parts[2]) - ord("a")) * 20)
        val = bit.sum(ind) - bit.sum(ind - 1)
        bit.add(ind, nval - val)
    else:
        l, r = map(int, parts[1:])
        val = bit.sum(r) - bit.sum(l - 1)
        mask = (1 << 20) - 1
        ans = 0
        while val:
            if val & mask:
                ans += 1
            val >>= 20
        print(ans)

Submission status: Accepted

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

class SegmentTree:
    def __init__(self,l):
        nb = bin(len(l))[2:]
        b = sum([int(d) for d in nb])
        if b == 1:
            self.end_leaves = pow(2,len(nb)-1)
        else:
            self.end_leaves = pow(2,len(nb))
        self.tree = [set() for _ in range(self.end_leaves*2)]
        
        for i in range(len(l)):
            self.tree[self.end_leaves+i].add(l[i])
            
    def union(self,a):
        if a >= self.end_leaves // 2:
            self.tree[a] = self.tree[a*2] | self.tree[a*2+1]
            return self.tree[a]
        else:
            self.tree[a] = self.union(a*2) | self.union(a*2+1)
            return self.tree[a]
    def update(self,a,s):
        x = a + self.end_leaves
        if s not in self.tree[x]:
            self.tree[x] = set(s)
            while x > 1:
                x //= 2
                self.tree[x] = self.tree[x*2] | self.tree[x*2+1]
    def query(self,l,r):
        x = l + self.end_leaves
        y = r + self.end_leaves
        tl = set()
        tr = set()
        while y - x > 1:
            if x % 2 == 1:
                tl = tl | self.tree[x]
                x += 1
            if y % 2 == 0:
                tr = self.tree[y] | tr
                y -= 1
            x >>= 1
            y >>= 1
        if y - x == 0:
            print(len(tl|tr|self.tree[x]))
        else:
            print(len(tl|tr|self.tree[x]|self.tree[y]))
            
            

N = int(input())
S = list(input())
st = SegmentTree(S)
st.union(1)
Q = int(input())
for i in range(Q):
    q = input().split()
    if q[0] == '1':
        st.update(int(q[1])-1,q[2])
    else:
        st.query(int(q[1])-1,int(q[2])-1)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
s = list(input())
alp = 'abcdefghijklmnopqrstuvwxyz'
cnt = {c: [] for c in alp}

for i, c in enumerate(s):
    cnt[c].append(i)

q = int(input())
for _ in range(q):
    t, x, y = input().split()
    ans = 0
    if t == '1':
        i, c = int(x) - 1, y
        if s[i] == c:
            continue
        a = bisect.bisect_left(cnt[s[i]], i)
        cnt[s[i]].pop(a)
        s[i] = c
        b = bisect.bisect_left(cnt[c], i)
        cnt[c].insert(b, i)
    else:
        l, r = int(x) - 1, int(y) - 1
        for c in alp:
            a = bisect.bisect_left(cnt[c], l)
            if a < len(cnt[c]) and cnt[c][a] <= r:
                ans += 1

        print(ans)

Submission status: Accepted

Solution code:
class SegmentTree(object):
    def __init__(self, sequence, function, identity):
        N = len(sequence)
        self.length = (1 << (N - 1)).bit_length()
        self.function = function
        self.data = [identity] * (self.length << 1)
        self.identity = identity
        # set values
        for i in range(N):
            self.data[i + self.length - 1] = sequence[i]
        # build
        for i in range(self.length - 2, -1, -1) :
            self.data[i] = self.function(self.data[(i << 1) + 1], self.data[(i << 1) + 2])

    def update(self, idx, x):
        idx += self.length - 1
        self.data[idx] = x
        while idx:
            idx = (idx - 1) >> 1
            self.data[idx] = self.function(self.data[(idx << 1) + 1], self.data[(idx << 1) + 2])

    def query(self, p, q):
        if q <= p:
            return self.identity
        p += self.length - 1
        q += self.length - 2
        res = self.identity
        while q - p > 1:
            if not p & 1:
                res = self.function(res, self.data[p])
            if q & 1:
                res = self.function(res, self.data[q])
                q -= 1
            p >>= 1
            q = (q - 1) >> 1
        return self.function(res, self.data[p]) if p == q else self.function(self.function(res, self.data[p]), self.data[q])

def popcount(n):
  n = (n & 0x5555555555555555) + ((n & 0xAAAAAAAAAAAAAAAA) >> 1)
  n = (n & 0x3333333333333333) + ((n & 0xCCCCCCCCCCCCCCCC) >> 2)
  n = (n & 0x0F0F0F0F0F0F0F0F) + ((n & 0xF0F0F0F0F0F0F0F0) >> 4)
  n = (n & 0x00FF00FF00FF00FF) + ((n & 0xFF00FF00FF00FF00) >> 8)
  n = (n & 0x0000FFFF0000FFFF) + ((n & 0xFFFF0000FFFF0000) >> 16)
  n = (n & 0x00000000FFFFFFFF) + ((n & 0xFFFFFFFF00000000) >> 32)
  return n

N = int(input())
S = input()
atoi = {chr(ord("a") + d): 1 << d for d in range(26)}
data = [atoi[c] for c in (S)]
seg_tree = SegmentTree(data, lambda a, b: a | b, 0)
Q = int(input())
for _ in range(Q):
    q, a, b = input().split()
    if q == "1":
        idx = int(a) - 1
        seg_tree.update(idx, atoi[b])
    else:
        print(popcount(seg_tree.query(int(a) - 1, int(b))))

Submission status: Accepted

Solution code:
class SegmentTree(object):
    def __init__(self, sequence, function, identify):
        N = len(sequence)
        self.length = (1 << (N - 1)).bit_length()
        self.function = function
        self.data = [identify] * (self.length << 1)
        self.identify = identify
        # set values
        for i in range(N):
            self.data[i + self.length - 1] = sequence[i]
        # build
        for i in range(self.length - 2, -1, -1) :
            self.data[i] = self.function(self.data[(i << 1) + 1], self.data[(i << 1) + 2])

    def update(self, idx, x):
        idx += self.length - 1
        self.data[idx] = x
        while idx:
            idx = (idx - 1) >> 1
            self.data[idx] = self.function(self.data[(idx << 1) + 1], self.data[(idx << 1) + 2])

    def query(self, p, q):
        if q <= p:
            return self.identify
        p += self.length - 1
        q += self.length - 2
        res = self.identify
        while q - p > 1:
            if not p & 1:
                res = self.function(res, self.data[p])
            if q & 1:
                res = self.function(res, self.data[q])
                q -= 1
            p >>= 1
            q = (q - 1) >> 1
        return self.function(res, self.data[p]) if p == q else self.function(self.function(res, self.data[p]), self.data[q])

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


N = int(input())
S = input()
atoi = {chr(ord("a") + d): 1 << d for d in range(26)}
data = [atoi[c] for c in (S)]
seg_tree = SegmentTree(data, lambda a, b: a | b, 0)
Q = int(input())
for _ in range(Q):
    q, a, b = input().split()
    if q == "1":
        idx = int(a) - 1
        seg_tree.update(idx, atoi[b])
    else:
        print(popcount(seg_tree.query(int(a) - 1, int(b))))

Submission status: Accepted

Solution code:
import bisect

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

alphabet="abcdefghijklmnopqrstuvwxyz"
bag={l:[] for l in alphabet}
for i in range(N):
    bag[S[i]].append(i+1)
#print(bag)

for i in range(Q):
    Type,a,b=input().split()
    if Type=='1':
        a=int(a)
        if S[a-1]!=b:
            bag[S[a-1]].remove(a)
            S[a-1]=b
            bisect.insort(bag[b],a)
    else:
        cnt=0
        a,b=int(a),int(b)
        for l in alphabet:
            bl=len(bag[l])
            if bl>0:
                left=bisect.bisect_left(bag[l],a)
                if left!=bl and bag[l][left]<=b:
                        cnt+=1
        print(cnt)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc157/tasks/abc157_e

from string import ascii_lowercase
from bisect import bisect_left, insort
from collections import defaultdict

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

locs = {c: [] for c in ascii_lowercase}
for i in range(N):
    locs[S[i]].append(i + 1)

for _ in range(Q):
    qt, l, r = input().split()
    l = int(l)
    if int(qt) == 1:
        if S[l - 1] != r:
            locs[S[l - 1]].remove(l)
            S[l - 1] = r
            insort(locs[r], l)
    else:
        count = 0
        r = int(r)
        for ch in ascii_lowercase:
            if len(locs[ch]) > 0:
                left = bisect_left(locs[ch], l)
                if left != len(locs[ch]):
                    if locs[ch][left] <= r:
                        count += 1

        print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

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


alphabet = "abcdefghijklmnopqrstuvwxyz"

bag = { l:[] for l in alphabet}

for i in range(N):
  bag[S[i]].append(i+1)


import bisect

for _ in range(Q):
  t,a,b = input().split()
  a = int(a)
  if int(t) == 1:
    if S[a-1]!=b:
      bag[S[a-1]].remove(a)
      S[a-1] = b
      bisect.insort(bag[b],a)
  else:
    count = 0
    b = int(b)
    for l in alphabet:
      if len(bag[l])>0:
        left = bisect.bisect_left(bag[l],a)
        if left != len(bag[l]):
          if bag[l][left] <= b:
            count += 1
    print(count)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

class SegmentTree():
    def __init__(self, init_val, N):
        """
        Parameters
        ----------
        init_val:int
            identity element
        N:int
            the number of nodes
        """
        self.init_val=init_val
        # Range Minimum Query
        self.N0 = 2**(N-1).bit_length() #Nを超える最小の2のべき乗
        # 0-indexedで管理(N0-1からはじまる)
        self.data = [self.init_val] * (2 * self.N0)

    def _segfunc(self, left, right):
        res= left | right
        return res

    def update(self,k, x):
        """
        Parameters
        ----------
        k:int
            target index(0-index)
        x:any
            target value
        """
        k += self.N0-1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = self._segfunc(self.data[2*k+1], self.data[2*k+2])

    def query(self, l, r):
        """
        Parameters
        ----------
        l,r:int
            target range [l,r)

        Return
        ----------
        res:any
            val
        """
        L = l + self.N0
        R = r + self.N0
        s = self.init_val
        while L < R:
            if R & 1:
                R -= 1
                s = self._segfunc(s, self.data[R-1])
    
            if L & 1:
                s = self._segfunc(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

def chartobit(c):
    return 1<<(ord(c)-97)
n=inp()
s=[chartobit(i) for i in list(input()) if i!="\n"]
st = SegmentTree(0, n)
for i in range(n):
    st.update(i,s[i])
q = inp()
ans = []
for i in range(q):
    mode, first, second = input().split()
    if mode == "1":
        # if second in st.data[int(first) - 1 + st.N0 - 1]:
        #     continue
        st.update(int(first) - 1, chartobit(second))
    else:
        ans.append((st.query(int(first) - 1, int(second))))
for i in ans:
    print(sum(map(int,bin(i)[2:])))

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

class SegmentTree():
    def __init__(self, init_val, N):
        """
        Parameters
        ----------
        init_val:int
            identity element
        N:int
            the number of nodes
        """
        self.init_val=init_val
        # Range Minimum Query
        self.N0 = 2**(N-1).bit_length()
        # 0-indexedで管理
        self.data = [self.init_val] * (2 * self.N0)

    def _segfunc(self, left, right):
        res= left | right
        return res

    def update(self,k, x):
        """
        Parameters
        ----------
        k:int
            target index(0-index)
        x:any
            target value
        """
        k += self.N0-1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = self._segfunc(self.data[2*k+1], self.data[2*k+2])

    def query(self, l, r):
        """
        Parameters
        ----------
        l,r:int
            target range [l,r)

        Return
        ----------
        res:any
            val
        """
        L = l + self.N0
        R = r + self.N0
        s = self.init_val
        while L < R:
            if R & 1:
                R -= 1
                s = self._segfunc(s, self.data[R-1])
    
            if L & 1:
                s = self._segfunc(s,self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

n=inp()
s=input()
st = SegmentTree(0,n)
for i in range(n):
    st.update(i,1<<(int.from_bytes(s[i].encode(),'little')-int.from_bytes('a'.encode(),'little')))
q = inp()
ans = []
for i in range(q):
    mode, first, second = input().split()
    if mode == "1":
        st.update(int(first)-1,1<<(int.from_bytes(second.encode(),'little')-int.from_bytes('a'.encode(),'little')))
    else:
        ans.append(bin(st.query(int(first) - 1, int(second))).count("1"))
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

class SegmentTree():
    def __init__(self, init_val, N):
        """
        Parameters
        ----------
        init_val:int
            identity element
        N:int
            the number of nodes
        """
        self.init_val=init_val
        # Range Minimum Query
        self.N0 = 2**(N-1).bit_length() #Nを超える最小の2のべき乗
        # 0-indexedで管理(N0-1からはじまる)
        self.data = [self.init_val] * (2 * self.N0)

    def _segfunc(self, left, right):
        res= left | right
        return res

    def update(self,k, x):
        """
        Parameters
        ----------
        k:int
            target index(0-index)
        x:any
            target value
        """
        k += self.N0-1
        self.data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.data[k] = self._segfunc(self.data[2*k+1], self.data[2*k+2])

    def query(self, l, r):
        """
        Parameters
        ----------
        l,r:int
            target range [l,r)

        Return
        ----------
        res:any
            val
        """
        L = l + self.N0
        R = r + self.N0
        s = self.init_val
        while L < R:
            if R & 1:
                R -= 1
                s = self._segfunc(s, self.data[R-1])
    
            if L & 1:
                s = self._segfunc(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
def chartobit(c):
    return 1<<(ord(c)-97)
def main():
    n=inp()
    s=[chartobit(i) for i in list(input()) if i!="\n"]
    st = SegmentTree(0, n)
    for i in range(n):
        st.update(i,s[i])
    q = inp()
    ans = []
    for i in range(q):
        mode, first, second = input().split()
        if mode == "1":
            # if second in st.data[int(first) - 1 + st.N0 - 1]:
            #     continue
            st.update(int(first) - 1, chartobit(second))
        else:
            ans.append((st.query(int(first) - 1, int(second))))
    for i in ans:
        print(sum(map(int,bin(i)[2:])))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect_right,insort

n = int(input())
s = list("-" + str(input()))
lis = [[] for i in range(26)]
for i in range(1,n+1):
    num = ord(s[i])-ord("a")
    lis[num].append(i)

q = int(input())
for turn in range(q):
    query = list(map(str,input().split()))
    if query[0] == "1":
        a = int(query[1])
        if s[a] == query[2]:
            continue
        num = ord(s[a])-ord("a")
        lis[num].pop(bisect_left(lis[num],a))
        next = ord(query[2])-ord("a")
        insort(lis[next],a)
        s[a] = query[2]
    else:
        a,b = int(query[1]),int(query[2])
        ans = 0
        for alphabet in range(26):
            if bisect_right(lis[alphabet],b)-bisect_left(lis[alphabet],a) >= 1:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
n=int(input())
from bisect import bisect_left,bisect_right
s=list(input())
q=int(input())
D={chr(ord("a")+i):[] for i in range(26)}
for i ,j in enumerate(s):
    D[j].append(i)
ans=0
for i in range(q):
    x=list(input().split())
    if x[0]=="1":
        l=int(x[1])
        l-=1
        r=x[-1]
        if r==s[l]:
            continue
        rr=bisect_left(D[r],l)
        D[s[l]].remove(l)
        D[r].insert(rr,l)
        s[l]=r
    else:
        l=int(x[1])
        r=int(x[2])
        l-=1
        r-=1
        ans=0
        for i in range(26):
            W=chr(ord("a")+i)
            ll=bisect_left(D[W],l)
            rr=bisect_right(D[W],r)
            if rr-ll>0:
                ans+=1
        print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import bisect

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    S = list(input())
    Q = int(input())

    L = [[] for x in range(26)] # i番目のリストは、アルファベットが現れるインデックスのリストを持つ。

    for idx, s in enumerate(S):
        L[ord(s)-ord("a")].append(idx)

    for _ in range(Q):
        row = input().split()
        if row[0] == '1':
            y, z = int(row[1])-1, row[2]
            if S[y] != z:
                idx_target = ord(S[y]) - ord("a")
                idx_del = bisect.bisect_left(L[idx_target], y)
                if idx_del < len(L[idx_target]):
                    L[idx_target].pop(idx_del)
                bisect.insort(L[ord(z) - ord("a")], y)
                S[y] = z

        elif row[0] == '2':
            y, z = int(row[1]) - 1, int(row[2]) - 1
            answer = 0
            for idx_alphabet in range(26):
                left = bisect.bisect_left(L[idx_alphabet], y)
                if left < len(L[idx_alphabet]) and y <= L[idx_alphabet][left] <= z:
                    answer += 1
            print(answer)

    # Failed to predict input format
    pass

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import log2, ceil


class SegTree:
    #####単位元######
    ide_ele = 0

    def __init__(self, init_val):
        n = len(init_val)
        self.num = 2**ceil(log2(n))
        self.seg = [self.ide_ele] * (2 * self.num - 1)

        for i in range(n):
            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])

    #####segfunc######
    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, a, b, k, l, r):
        if r <= a or b <= l:
            return self.ide_ele
        if a <= l and r <= b:
            return self.seg[k]
        else:
            vl = self.query(a, b, k*2+1, l, (l+r)//2)
            vr = self.query(a, b, k*2+2, (l+r)//2, r)
            return self.segfunc(vl, vr)


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

li = [1 << (ord(s) - ord('a')) for s in S]
seg_tree = SegTree(li)
ans = []
for _ in range(Q):
    i, l, r = input().split()
    i = int(i)
    l = int(l)
    if i == 1:
        seg_tree.update(l-1, 1 << (ord(r) - ord('a')))
    else:
        r = int(r)
        num = seg_tree.query(l-1, r, 0, 0, seg_tree.num)
        ans.append(bin(num).count('1'))

for a in ans:
    print(a)