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:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    #print(r)

def solve():
    K = iip(False)
    S = input()
    S = [ord(i) for i in S]
    Q = iip(False)

    posit = {}
    for i in range(ord("a"), ord("z")+1):
        posit[i] = []

    query = []
    for i in range(Q):
        query.append(input().split())

    for i, j in enumerate(S, 1):
        posit[j].append(i)

    result = []
    for d in range(ord("a"), ord("z")+1):
        #print(chr(d), posit[d])
        pass


    for q in query:
        if q[0] == "1":
            p = int(q[1])
            before = S[p-1]
            after = ord(q[2])
            if before == after:
                continue
            S[p-1] = after

            idx = bisect_left(posit[before], p)

            posit[before].pop(idx)
            insort_left(posit[after], p)

        else:
            l = int(q[1])
            r = int(q[2])

            ret = 0
            for i in range(ord("a"), ord("z")+1):
                ll = bisect_left(posit[i], l)

                if not posit[i]:  # 文字が存在しなければcontinue
                    #print("e2")
                    continue
                if l > posit[i][-1]:  # lより小さい文字しかなければcontinue
                    continue
                if posit[i][ll] > r:  # l以上のpositionで一番小さいものがrより大きければcontinue
                    #print("e3")
                    continue

                    #print(chr(i))
                ret += 1  # いずれのcontinue条件にも引っかからなければスコアを１増やす
            result.append(ret)


    #print(S)
    #print(posit)
    split_print_space(result)

    return



#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    #print(r)

def solve():
    K = iip(False)
    S = input()
    S = [ord(i) for i in S]
    Q = iip(False)

    posit = {}
    for i in range(ord("a"), ord("z")+1):
        posit[i] = []

    query = []
    for i in range(Q):
        query.append(input().split())

    for i, j in enumerate(S, 1):
        posit[j].append(i)

    result = []
    for d in range(ord("a"), ord("z")+1):
        #print(chr(d), posit[d])
        pass


    for q in query:
        if q[0] == "1":
            p = int(q[1])
            before = S[p-1]
            after = ord(q[2])
            if before == after:
                continue
            S[p-1] = after

            idx = bisect_left(posit[before], p)

            posit[before].pop(idx)
            insort_left(posit[after], p)

        else:
            l = int(q[1])
            r = int(q[2])

            ret = 0
            for i in range(ord("a"), ord("z")+1):
                ll = bisect_left(posit[i], l)
                if posit[i]:
                    #print(chr(i), posit[i], l, r, ll)
                    pass

                #print(ll)

                if not posit[i]:
                    #print("e2")
                    continue
                if l > posit[i][-1]:
                    continue
                if not posit[i][ll] <= r:
                    #print("e3")
                    continue

                    #print(chr(i))
                ret += 1
            result.append(ret)


    #print(S)
    #print(posit)
    split_print_space(result)

    return



#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class SegTree:
    # n : 元の配列の長さ
    # init_list: 元の配列
    # segfunc : 載せる関数（演算）
    # ide_ele : segfuncの単位元
        
    def __init__(self, n, init_list ,segfunc, ide_ele):
        #　num : 2**num >= n となる最小の整数 （葉の数）
        # seg : segtreeのリスト
        self.num = 2**((n-1).bit_length())
        self.seg = [ide_ele]*(2*self.num)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        # 葉の要素をセット
        for i in range(n):
            self.seg[i+self.num-1] = init_list[i]        
        # segtreeの構築
        for i in range(self.num-2, -1, -1):
            self.seg[i] = segfunc(self.seg[2*i+1],self.seg[2*i+2])
        
        #memo: 要素iの子ノードは要素2*i+1, 2*i+2
        #    : 要素iの親ノードは要素(i-1)//2
        
    # 要素の更新 (init_list[k]=x)
    def update(self,k,x):
        k += self.num-1 #葉のノードのインデックス
        self.seg[k] = x
        #末端から頂点まで更新
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1], self.seg[2*k+2])
     
    # 区間クエリ （区間[l,r)に対する演算結果）
    def query(self, l,r):
        if r<=l:
            return self.ide_ele
        
        l += self.num-1 #葉のノードのインデックス
        r += self.num-2 #半開区間から閉区間へ
        ret = self.ide_ele
        
        while r-l>1:
            if l&1 == 0:
                ret = self.segfunc(ret,self.seg[l])
            
            if r&1 == 1:
                ret = self.segfunc(ret,self.seg[r])
                r -= 1
            # 親ノードへ遷移
            l = l//2
            r = (r-1)//2
        if r==l:
            ret = self.segfunc(ret, self.seg[r])
        else:
            ret = self.segfunc(ret, self.seg[l])
            ret = self.segfunc(ret, self.seg[r])
        
        return ret
            
def segfunc(x,y):
    return max(x,y)

def segfunc2(x,y):
    return min(x,y)

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

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

def main():
    N = int(input())
    S = list(input())
    Q = int(input())
    Segtree = [SegTree(N,[0] * N,segfunc,0) for _ in range(26)]
    for i, c in enumerate(S):
        Segtree[ctoi(c)].update(i,1)

    for _ in range(Q):
        q, *query = map(str, input().split())
        if q == '1':
            i, c = query
            i = int(i) - 1
            if c == S[i]:
                continue
            Segtree[ctoi(c)].update(i, 1)
            Segtree[ctoi(S[i])].update(i,0)
            S[i] = c
        else:
            l, r = query
            l = int(l) - 1
            r = int(r)
            ans = 0
            for j in range(26):
                if Segtree[j].query(l,r):
                    ans += 1
                    
            print(ans)



    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# simpleバージョン
class BinaryIndexedTree:
    def __init__(self,size):
        self.N = size
        self.bit = [0]*(size+1)
    def add(self,x,w): # 0-indexed
        x += 1
        while x <= self.N:
            self.bit[x] += w
            x += (x & -x)
    def _sum(self,x): # 1-indexed
        ret = 0
        while x > 0:
            ret += self.bit[x]
            x -= (x & -x)
        return ret
    def sum(self,l,r): # [l,r)
        return self._sum(r) - self._sum(l)
    def __str__(self): # for debug
        arr = [self.sum(i,i+1) for i in range(self.N)]
        return str(arr)


class BIT:
    """ 区間加算BIT(区間加算・区間合計取得) """
 
    def __init__(self, N):
        # 添字0が使えないので、内部的には全て1-indexedとして扱う
        N += 1
        self.N = N
        self.data0 = [0] * N
        self.data1 = [0] * N
 
    def _add(self, data, k, x):
        k += 1
        while k < self.N:
            data[k] += x
            k += k & -k
 
    def _get(self, data, k):
        k += 1
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s
 
    def add(self, l, r, x):
        """ 区間[l,r)に値xを追加 """
 
        self._add(self.data0, l, -x*(l-1))
        self._add(self.data0, r, x*(r-1))
        self._add(self.data1, l, x)
        self._add(self.data1, r, -x)
 
    def query(self, l, r):
        """ 区間[l,r)の和を取得 """
 
        return self._get(self.data1, r-1) * (r-1) + self._get(self.data0, r-1) \
             - self._get(self.data1, l-1) * (l-1) - self._get(self.data0, l-1)

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

def main():
    N = int(input())
    S = input()
    Q = int(input())
    query = [input().split() for i in range(Q)]
    bits = [BIT(N) for i in range(26)]
    s = []
    for i, c in enumerate(S):
        bits[ctoi(c)].add(i,i+1,1)
        s.append(c)

    for a, b, c in query:
        if a == '1':
            i = int(b) - 1
            bits[ctoi(s[i])].add(i,i+1,-1)
            bits[ctoi(c)].add(i,i+1,1)
            s[i] = c
        else:
            l = int(b) - 1
            r = int(c)
            a = 0
            for i in range(26):
                if bits[i].query(l,r):
                    a += 1
            print(a)




if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

# from helper import elapsed_time
from bisect import bisect_left, insort_left


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

# a-zまでの26文字に対して、s文字列の各文字に該当するindexを格納しておく
d = {i: [] for i in range(26)}
for i, c in enumerate(s):
    d[ord(c) - ord("a")].append(i)


# @elapsed_time
def convert(d: dict, s: list, q1: int, q2: str):
    if s[q1] == q2:
        return d, s

    didx_before = ord(s[q1]) - ord("a")
    didx_after = ord(q2) - ord("a")

    idx = bisect_left(d[didx_before], q1)
    d[didx_before].pop(idx)
    s[q1] = q2
    insort_left(d[didx_after], q1)

    return d, s


# @elapsed_time
def calc(d: dict, q1: int, q2: int):
    ans = 0
    for i in range(26):
        idx = bisect_left(d[i], q1)
        if d[i] and q1 <= d[i][-1] and d[i][idx] < q2 + 1:
            ans += 1

    return ans


for _ in range(Q):
    q, q1, q2 = input().split()
    q = int(q)
    if q == 1:
        d, s = convert(d, s, int(q1) - 1, q2)
    if q == 2:
        print(calc(d, int(q1) - 1, int(q2) - 1))

Submission status: Accepted

Solution code:
n = int(input())
S = input()
s = []
for i in range(n):
    s.append(S[i])
q = int(input())
BIT = []
for i in range(26):
    B = [0]*(n+1) #1-indexed
    BIT.append(B)

def sum_of_1_to_i(i, LIST):
    z = 0
    while i > 0:
        z += LIST[i]
        i -= i & (-i)
    return z

def update(i, j, LIST):
    while i <= n:
        LIST[i] += j
        i += i & (-i)

for i in range(n):
    k = ord(s[i])-97
    update(i+1, 1, BIT[k])

ans = []

for i in range(q):
    a,b,c = input().split()
    a = int(a)
    b = int(b)
    if a == 1:
        temp = s[b-1]
        if temp == c:
            None
        else:
            update(b, -1, BIT[ord(temp)-97])
            update(b, 1, BIT[ord(c)-97])
            s[b-1] = c
    else:
        c = int(c)
        cur = 0
        for j in range(26):
            if sum_of_1_to_i(c, BIT[j])-sum_of_1_to_i(b-1, BIT[j]) != 0:
                cur += 1
        ans.append(cur)
for i in range(len(ans)):
    print(ans[i])

Submission status: Accepted

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

class SegmentTree():
    def segfunc(self, x, y):
        return max(x, y)
        
    def __init__(self, ide_ele, n, l, target):
        # n以上の最小の2のべき乗、一番下の段はここからスタートになる
        self.ide_ele = ide_ele
        self.num =2**(n-1).bit_length()
        self.tree = [ide_ele]*self.num*2
        # 一番下の段
        for i in range(n):
            if l[i] == target:
                self.tree[i+self.num-1] = 1
        # 
        for i in range(self.num-2, -1, -1):
            self.tree[i] = self.segfunc(self.tree[2*i+1], self.tree[2*i+2])
    
    def update(self, k, add):
        k += self.num-1
        if add:
            self.tree[k] = 1
        else:
            self.tree[k] = 0
        while k:
            k = (k-1)//2
            self.tree[k] = self.segfunc(self.tree[k*2+1], self.tree[k*2+2])
    
    def query(self, p, q):
        if q<=p:
            return self.ide_ele

        # [p, q)
        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.tree[p])
            if q&1 == 1: #右なのに左端
                res = self.segfunc(res, self.tree[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p==q:
            res = self.segfunc(res, self.tree[p])
        else:
            res = self.segfunc(self.segfunc(res, self.tree[p]), self.tree[q])
        return res

    # 閉区間になってる
    def rec_query(self, p, q, k, l, r):
        #q -= 1 [)の場合
        #print(p, q, k, l, r)
        if r < p or q < l: # out of range
            return self.ide_ele
        if p <= l and r <= q:
            return self.tree[k]
        else:
            vl = self.rec_query(p, q, k*2+1, l, (l+r)//2)
            vr = self.rec_query(p, q, k*2+2, (l+r)//2+1, r)
        #print(vl, vr)
        return self.segfunc(vl, vr)



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

result = ""

d = {}
for i in range(26):
    d[chr(ord("a")+i)] = SegmentTree(0, N, S, chr(ord("a")+i))

S = list(S)

for q in range(Q):
    case, p, q = (i for i in input().split())
    #print(case, p, q)
    p = int(p)-1
    case = int(case)
    if case==1:
        #print(p)
        d[S[p]].update(p, False)
        d[q].update(p, True)
        S[p] = q
    else:
        ans = 0
        for c in range(26):
            #print(d[chr(ord("a")+c)].tree)
            ans += d[chr(ord("a")+c)].query(p, int(q))
        result += str(ans)+"\n"

#print(S)
print(result[:-1])

Submission status: Accepted

Solution code:
from bisect import bisect_left, insort_left
N = int(input())
S = [c for c in input()]
Q = int(input())
d = {i: [] for i in range(26)}
for i, c in enumerate(S):
    d[ord(c) - ord("a")].append(i)

# print(d)
for _ in range(Q):
    q = input().split()
    if int(q[0]) == 1:
        iq, cq = int(q[1]), q[2]
        iq -= 1
        if S[iq] == cq:
            continue
        else:
            idx = bisect_left(d[ord(S[iq]) - ord("a")], iq)
            d[ord(S[iq]) - ord("a")].pop(idx)
            S[iq] = cq
            insort_left(d[ord(cq) - ord("a")], iq)
    else:
        l, r = int(q[1]), int(q[2])
        l -= 1
        ans = 0
        for i in range(26):
            idx = bisect_left(d[i], l)
            if d[i] and l <= d[i][-1] and d[i][idx] < r:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
from bisect import insort_left, bisect_left
N = int(input())
S = list(input())
Q = int(input())
Query = [input() for _ in range(Q)]
dic = {chr(i+ord("a")):[] for i in range(26)}
for i, s in enumerate(S):
    dic[s].append(i)
for q in Query:
    t,a,b = q.split()
    a = int(a)-1
    if(t == "1"):
        if(S[a]==b):
            continue
        tmp_index = bisect_left(dic[S[a]],a)
        dic[S[a]].pop(tmp_index)
        insort_left(dic[b],a)
        S[a] = b
    elif(t == "2"):
        b = int(b)-1
        cnt = 0
        for li in dic.values():
            if li and a<=li[-1] and li[bisect_left(li, a)] <= b:
                cnt += 1
        print(cnt)

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, n, init_value, segfunc, ide_ele):
        self.N0 = 2 ** (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i in range(n):
            self.data[i + self.N0 - 1] = init_value[i]
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    def update(self, _k, x):
        k = _k + self.N0 - 1
        self.data[k] = x
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    def query(self, _p, _q):
        p = _p
        q = _q
        if q <= p:
            return self.ide_ele
        
        p += self.N0 - 1
        q += self.N0 - 2
        res = self.ide_ele
        while 1 < q - p:
            if p & 1 == 0:
                res = self.segfunc(res, self.data[p])
            if q & 1 == 1:
                res = self.segfunc(res, self.data[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self.segfunc(res, self.data[p])
        else:
            res = self.segfunc(self.segfunc(res, self.data[p]), self.data[q])
        return res


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


def solve():
    N = int(input())
    S = input()
    Q = int(input())
    
    init_val = [1 << ord(S[i]) - ord('a') for i in range(N)]
    
    def segfunc(a, b):
        return a | b
    
    seg_tree = SegmentTree(N, init_val, segfunc, 0)
    
    for _ in range(Q):
        cmd, *query = input().split()
        cmd = int(cmd)
        if cmd == 1:
            i = int(query[0]) - 1
            c = query[1]
            seg_tree.update(i, 1 << ord(c) - ord('a'))
        else:
            l = int(query[0]) - 1
            r = int(query[1])
            kind = seg_tree.query(l, r)
            print(popcount(kind))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#ABC157E

n = int(input())
s = list(input())
q = int(input())
bits = [[0 for _ in range(n+1)] for _ in range(26)]
sl = []
for alp in s:
	alpord = ord(alp) - 97
	sl.append(alpord)
#print(bits) #test
#print(sl) #test
#print('クエリ開始') #test

def query(pos):
	ret = [0] * 26
	p = pos
	while p > 0:
		for i in range(26):
			ret[i] += bits[i][p]
		p -= p&(-p)
	return ret

def update(pos, a, x):
	r = pos
	while r <= n:
		bits[a][r] += x
		r += r&(-r)

for i in range(n):
	update(i+1, sl[i], 1)
#print(bits) #test

for _ in range(q):
	quer, xx, yy = map(str, input().split())
	if quer == '1':
		x = int(xx)
		y = ord(yy) - 97
		if sl[x-1] == y:
			continue
		else:
			update(x, sl[x-1], -1)
			update(x, y, 1)
			sl[x-1] = y
		#print('クエリ1でした') #test
		#print(bits) #test
		#print(sl) #test
	else:
		x = int(xx)
		y = int(yy)
		cnt1 = query(y)
		cnt2 = query(x-1)
		#print('クエリ2です') #test
		#print(cnt1) #test
		#print(cnt2) #test
		ans = 0
		for i in range(26):
			if cnt1[i] - cnt2[i] > 0:
				ans += 1
		print(ans)

Submission status: Accepted

Solution code:
from bisect import insort_left, bisect_left
n = int(input())
s = list(input())
Q = int(input())
query = [input() for _ in range(Q)]
dic = {chr(i+ord('a')):[] for i in range(26)}
for ind, c in enumerate(s):
    dic[c].append(ind)

for q in query:
    t, a, b = q.split()
    a = int(a)-1
    if t=='1':
        if s[a]==b:
            continue
        ind = bisect_left(dic[s[a]], a)
        dic[s[a]].pop(ind)
        insort_left(dic[b], a)
        s[a] = b
    else:
        b = int(b)-1
        tmp = 0
        for li in dic.values():
            if li and a<=li[-1] and li[bisect_left(li, a)] <= b:
                tmp += 1
        print(tmp)

Submission status: Accepted

Solution code:
class SegTree:
    def __init__(self, N, S):
        self.N = 2 ** ((N-1).bit_length())
        self.tree = [0 for i in range(self.N * 2 - 1)]
        for i in range(len(S)):
            self.tree[self.N - 1 + i] = 1 << (ord(S[i]) - ord("a"))

        for i in range(self.N - 2, -1, -1):
            self.tree[i] = self.tree[i*2 + 1] | self.tree[i*2 + 2]

    def update(self, index, char):
        i = self.N - 1 + index
        # アルファベットがある = bitが立っている
        self.tree[i] = 1 << (ord(char) - ord("a"))
        while i > 0:
            i = (i-1) // 2
            self.tree[i] = self.tree[i*2 + 1] | self.tree[i*2 + 2]

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

    # k : ノードの番号
    # l : ノードkの受け持つ区間
    # r : ノードkの受け持つ区間
    def query(self, a, b, k, l, r):
        if r <= a or b <= l: # 区間外
            return 0
        elif a <= l and r <= b: # 受け持ち区間は完全に含まれている
            return self.tree[k]
        else: # 一部含まれてる
            left = self.query(a, b, 2 * k + 1, l, (l+r)//2)
            right = self.query(a, b, 2 * k + 2, (l+r)//2, r)
            return left | right

def solve():
    N = int(input())
    S = list(input().strip())
    tree = SegTree(N, S)

    Q = int(input())
    for _ in range(Q):
        t_q, in_1, in_2 = input().split()
        if t_q == "1":
            i_q = int(in_1)
            c_q = in_2
            tree.update(i_q-1, c_q)
        else:
            l_q = int(in_1)
            r_q = int(in_2)
            print(bin(tree.get(l_q-1, r_q)).count("1"))

solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
N=input()
bit=[ [ 0 for _ in range(N+1) ] for __ in range(27) ] 

def add(i,a,w):
    while a<=N:
        bit[i][a]+=w
        a+=a&-a

def sum(i,a):
    ret=0
    while 0<a:
        ret+=bit[i][a]
        a-=a&-a
    return ret

S=sys.stdin.readline().strip()
S=[None]+list(S) #1-indexed
for j,x in enumerate(S):
    if j==0: continue
    i=ord(x)-96
    add(i,j,1)

Q=input()
for _ in range(Q):
    q1,q2,q3=sys.stdin.readline().split()
    if q1=="1":
        q1=int(q1)
        q2=int(q2)
        current_s=q3
        former_s=S[q2]
        former_s=ord(former_s)-96  #1-indexed
        S[q2]=current_s         #文字列で更新された1文字を置き換える
        current_s=ord(current_s)-96
        add(current_s,q2,1)
        add(former_s,q2,-1) 
    if q1=="2":
        q2=int(q2)
        q3=int(q3)
        begin,end=q2,q3
        cnt=0
        for i in range(1,27):
            if 0<sum(i,end)-sum(i,begin-1):
                cnt+=1
        print cnt

Submission status: Accepted

Solution code:
import bisect

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

def ordN(x):
  return ord(x) - ord('a')

li = [[] for _ in range(26)]
for i,s in enumerate(S):
  li[ordN(s)].append(i)

for i in range(int(input())):
  Q1, Q2, Q3 = input().split()
  if Q1 == "1":
    Q2 = int(Q2) - 1
    if S[Q2] != Q3:
      I = bisect.bisect_left(li[ordN(S[Q2])], Q2)
      li[ordN(S[Q2])].pop(I)
      bisect.insort(li[ordN(Q3)], Q2)
      S[Q2] = Q3
  else:
    Q2, Q3 = int(Q2)-1, int(Q3)-1
    count = 0
    for j in range(26):
      I = bisect.bisect_left(li[j], Q2)
      if I < len(li[j]) and li[j][I] <= Q3:
        count += 1
    print(count)

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        """
            data : BIT木データ
            el : 元配列
        """
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    
    """A1 ~ Aiまでの累積和"""
    def Sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & (-i)   #LSB(Least Significant Bit)の獲得:i&(-i)
        return s
    
    """Ai += x"""
    def Add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    
    """Ai ~ Ajまでの累積和"""
    def Get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.Sum(j) - self.Sum(i)

def ctoi(c):
    return ord(c) - 97

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

bits = [BIT(n) for _ in range(26)]
ans = []
for i in range(n):
    bits[ctoi(s[i])].Add(i+1, 1)
for _ in range(q):
    line = list(input().split())
    if line[0] == '1':
        idx = int(line[1])
        bits[ctoi(s[idx-1])].Add(idx, -1)
        s[idx-1] = line[2]
        bits[ctoi(line[2])].Add(idx, 1) 
    else:
        l,r = int(line[1]), int(line[2])
        cnt = 0
        for i in range(26):
            if bits[i].Get(l-1,r)!=0:
                cnt += 1
        ans.append(cnt)
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
def ctoi(x):
    return ord(x)-ord("a")
n = int(input())
s = list(input())
q = int(input())
bit = [[0]*(n+1) for _ in range(26)]

def update(pos,a,x):
    while pos<=n:
        bit[a][pos] += x
        pos += pos&(-pos)

def query(pos):
    ret=[0]*26
    for i in range(26):
        tmp=0
        p=pos
        while p>0:
            tmp+=bit[i][p]
            p-=p&(-p)
        ret[i]=tmp
    return ret

for i in range(n):
    update(i+1,ctoi(s[i]),1)

for _ in range(q):
    flag,a,b = input().split()
    flag=int(flag)
    a=int(a)
    if flag==1:
        if s[a-1]==b:
            continue
        else:
            update(a,ctoi(s[a-1]),-1)
            update(a,ctoi(b),1)
            s[a-1]=b
    else:
        b=int(b)
        c1 = query(b)
        c2 = query(a-1)
        ans = 0
        for i in range(26):
            if c1[i]-c2[i]>0:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
import bisect

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

def ci(x):
  return "abcdefghijklmnopqrstuvwxyz".find(x)

d=[[] for _ in range(26)]
for i,s in enumerate(S):
  d[ci(s)].append(i)

for i in range(int(input())):
  t,x,y=input().split()
  if t=="1":
    x=int(x)-1
    if S[x]!=y:
      l=bisect.bisect_left(d[ci(S[x])],x)
      d[ci(S[x])].pop(l)
      bisect.insort(d[ci(y)],x)
      S[x]=y
  else:
    x,y=int(x)-1,int(y)-1
    c=0
    for j in range(26):
      l=bisect.bisect_left(d[j],x)
      if l<len(d[j]) and d[j][l] <= y:
        c += 1
    print(c)