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 bisect
from collections import defaultdict

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

alpha_dic = defaultdict(list)

for i, s in enumerate(S):
    alpha_dic[s].append(i)

for _ in range(Q):
    l, m, n = input().split()

    if l == '1':
        m = int(m) - 1
        c = S[m]

        if c == n:
            continue
        else:
            i = bisect.bisect_left(alpha_dic[c], m)
            del alpha_dic[c][i]

            bisect.insort_left(alpha_dic[n], m)
            S[m] = n
    else:
        m, n = int(m) - 1, int(n) - 1

        cnt = 0
        for _, val in alpha_dic.items():
            if not val:
                continue

            left_idx = bisect.bisect_left(val, m)
            right_idx = bisect.bisect_left(val, n)
            l = len(val)

            if left_idx > right_idx or (left_idx == right_idx and left_idx == l) or (left_idx == right_idx and val[left_idx] != m and val[right_idx] != n):
                continue

            cnt += 1

        print(cnt)

Submission status: Accepted

Solution code:
class SegTree:

    def __init__(self, N, S):
        self.N = 1
        while self.N < N:
            self.N *= 2
        self.tree = [0 for i in range(2 * self.N - 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
        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)

    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())
    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)
        elif t_q == '2':
            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:
import bisect
import math
from collections import deque

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

class Node:
    def __init__(self, val, idx=0):
        self.val = val
        self.idx = idx

    def __str__(self):
        return 'val : ' + str(self.val) + ' idx : ' + str(self.idx)

# 0-idxed SegmentTree
class SegmentTree:
    def __init__(self, N, vals, default_value=INF):
        self.N0 = pow(2, (N-1).bit_length())
        self.nodes = [Node(default_value, i+1-self.N0)
                      for i in range(2*self.N0-1)]
        for i in reversed(range(2*self.N0-1)):
            ind = i+1-self.N0
            if ind >= N:
                self.nodes[i].val = default_value
            elif ind >=0 and N > ind:
                self.nodes[i].val = vals[ind]
            else:
                self.nodes[i] = self.propagate(
                    self.nodes[i*2+1], self.nodes[i*2+2])

    def __getitem__(self, key):  # getiten : ST[i]
        return self.nodes[key+self.N0-1].val

    def __setitem__(self, i, x):  # update : ST[i] = x
        i += self.N0 - 1
        self.nodes[i].val = x
        while i > 0:
            i = (i-1)//2
            self.nodes[i] = self.propagate(self.nodes[i*2+1], self.nodes[i*2+2])

    def __str__(self):
        return '['+', '.join(map(str, [self.nodes[i+self.N0-1].val for i in range(self.N0)]))+']'

    def query(self, L, R):  #value of [L,R)
        retnode = Node(0, 0)
        L += self.N0
        R += self.N0
        while L < R:
            if R & 1:
                R -= 1
                retnode = self.propagate(retnode, self.nodes[R-1])
            if L & 1:
                retnode = self.propagate(retnode, self.nodes[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return retnode

    def propagate(self, node_x, node_y):  # return parent if x,y is child
        return Node(node_x.val | node_y.val)


def main():
    N = iRaw()
    S = sRaw()
    sgt = SegmentTree(N, [1 << (ord(s)-ord('a')) for s in S])
    Q = iRaw()
    ans =[]
    for _ in range(Q):
        t,l,r = ssRaw()
        if t=="1":
            sgt[int(l)-1] = 1 << (ord(r)-ord("a"))
        else:
            ret = sgt.query(int(l)-1, int(r))
            ans.append(str(bin(ret.val)).count("1"))
    return "\n".join(map(str, ans))

if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
import bisect
import math
from collections import deque

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29


class Node:
    def __init__(self, val, idx=0):
        self.val = val
        self.idx = idx

    def __str__(self):
        return 'val : ' + str(self.val) + ' idx : ' + str(self.idx)

# 0-idxed SegmentTree
class SegmentTree:
    def __init__(self, N, vals, default_value=INF):
        self.N0 = pow(2, (N-1).bit_length())
        self.nodes = [Node(default_value, i+1-self.N0)
                      for i in range(2*self.N0-1)]
        for i in reversed(range(2*self.N0-1)):
            ind = i+1-self.N0
            if ind >= N:
                self.nodes[i].val = default_value
            elif ind >=0 and N > ind:
                self.nodes[i].val = vals[ind]
            else:
                self.nodes[i] = self.process(
                    self.nodes[i*2+1], self.nodes[i*2+2])

    def __getitem__(self, key):  # getiten : ST[i]
        return self.nodes[key+self.N0-1].val

    def __setitem__(self, i, x):  # update : ST[i] = x
        i += self.N0 - 1
        self.nodes[i].val = x
        while i > 0:
            i = (i-1)//2
            self.nodes[i] = self.process(self.nodes[i*2+1], self.nodes[i*2+2])

    def __str__(self):
        return '['+', '.join(map(str, [self.nodes[i+self.N0-1].val for i in range(self.N0)]))+']'

    def query(self, L, R):  # [L,R)の値
        retnode = Node(0, 0)
        L += self.N0
        R += self.N0
        while L < R:
            if R & 1:
                R -= 1
                retnode = self.process(retnode, self.nodes[R-1])
            if L & 1:
                retnode = self.process(retnode, self.nodes[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return retnode

    def process(self, node_x, node_y):  # x,yが子の時，親に返る値
        return Node(node_x.val | node_y.val)


def main():
    N = iRaw()
    S = sRaw()
    sgt = SegmentTree(N, [1 << (ord(s)-ord('a')) for s in S])
    Q = iRaw()
    ans =[]
    for _ in range(Q):
        t,l,r = ssRaw()
        if t=="1":
            sgt[int(l)-1] = 1 << (ord(r)-ord("a"))
        else:
            ret = sgt.query(int(l)-1, int(r))
            ans.append(str(bin(ret.val)).count("1"))
    return "\n".join(map(str, ans))

if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
import bisect

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

pos = [[] for i in range(26)]
alp = "abcdefghijklmnopqrstuvwxyz"
atoi = {}
for i in range(26):
    atoi[alp[i]] = i
for i in range(n):
    pos[atoi[s[i]]].append(i)

for i in range(q):
    a, b, c = input().split()
    if a == "1":
        b = int(b)-1
        if c == s[b]:
            continue
        index = bisect.bisect_left(pos[atoi[s[b]]], b)
        del pos[atoi[s[b]]][index]
        bisect.insort_left(pos[atoi[c]], b)
        s[b] = c
    else:
        l, r = int(b)-1, int(c)
        ans = 0
        for i in range(26):
            cnt = bisect.bisect_left(pos[i], r) - bisect.bisect_left(pos[i], l)
            if cnt > 0:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.buffer.readline
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

import bisect
from string import ascii_lowercase
d = dict()
for i, c in enumerate(ascii_lowercase):
    d[c] = i

N = int(input())
S = list(input())
lst = [[] for _ in range(26)]
for i in range(N):
    lst[d[S[i]]].append(i)

Q = int(input())
for q in range(Q):
    a, b, c = input().split()
    if a=='1':
        i = int(b)-1
        if c == S[i]:   # 変更なし
            continue
        idx = bisect.bisect_left(lst[d[S[i]]],i)
        del lst[d[S[i]]][idx]
        bisect.insort_left(lst[d[c]],i)
        S[i] = c
    else:
        l = int(b)-1
        r = int(c)
        ans = 0
        for i in range(26):
            cnt = bisect.bisect_left(lst[i],r) - bisect.bisect_left(lst[i],l)
            if cnt:
                ans += 1
        print(ans)

Submission status: Accepted

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

N=input()
S=["None"]+list(raw_input())
Q=input()
query=[ sys.stdin.readline().split() for _ in range(Q) ]

#BIT
bit=[ [ 0 for _ in range(N+1) ] for _ in range(27) ]  #1-indexed bit[1]:aのbit, bit[2]:bのbit ...

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

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

for i,x in enumerate(S):
    if i==0: continue
    add(ord(x)-96,i,1)  #a~zのどのbit配列か,特定文字のbit配列の何番目,bitに代入する値


for q1,q2,q3 in query:
    q1=int(q1)
    q2=int(q2)
    if q1==1:
        before_q3=S[q2] #文字列Sの変更前の文字をbefore_q3に代入
        S[q2]=q3        #文字列Sの変更部分1文字を更新
        q3=ord(q3)-96                   #変更後の文字をアスキーコード10進数で表現
        before_q3=ord(before_q3)-96     #変更前の文字をアスキーコード10進数で表現
        add(q3,q2,1)                    #a~zのどのbit配列か,特定文字のbit配列の何番目,bitに代入する値
        add(before_q3,q2,-1)    #置き代えた文字は-1しなきゃいけない
    elif q1==2:
        q3=int(q3)
        cnt=0
        for i in range(1,27):
            if 0<sum(i,q3)-sum(i,q2-1):
                cnt+=1
        print cnt

Submission status: Accepted

Solution code:
#https://tjkendev.github.io/procon-library/python/range_query/rmq_segment_tree.html
# N: 処理する区間の長さ

#bit管理
#演算はor
N = int(input())
s = input()


N0 = 1
while N0<=N:
    N0*=2
INF = 0
data = [0]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = 1<<x
    while k >= 0:
        k = (k - 1) // 2
        data[k] =data[2*k+1]|data[2*k+2]
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = s|data[R-1]

        if L & 1:
            s = s|data[L-1]
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(N):
    update(i,ord(s[i])-ord("a"))
q = int(input())

for j in range(q):
    t,l,r = input().split( )
    if t=="1":
        update(int(l)-1,ord(r)-ord("a"))
        
    else:
        bit = bin(query(int(l)-1,int(r)))[2:]
        ans = 0
        for i in bit:
            ans += int(i)
        print(ans)

Submission status: Accepted

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

N=input()
S=["None"]+list(raw_input())
Q=input()
query=[ sys.stdin.readline().split() for _ in range(Q) ]

#BIT
bit=[ [ 0 for _ in range(N+1) ] for _ in range(27) ]  #中も外も1-indexed bit[1]:aのbit, bit[2]:bのbit ...

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

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

for i,x in enumerate(S):
    if i==0: continue
    add(ord(x)-96,i,1)  #a~zのどのbit配列か,特定文字のbit配列の何番目,bitに代入する値


for q1,q2,q3 in query:
    q1=int(q1)
    q2=int(q2)
    if q1==1:
        before_q3=S[q2] #文字列Sの変更前の文字をbefore_q3に代入
        S[q2]=q3        #文字列Sの変更部分1文字を更新
        q3=ord(q3)-96                   #変更後の文字をアスキーコード10進数で表現
        before_q3=ord(before_q3)-96     #変更前の文字をアスキーコード10進数で表現
        add(q3,q2,1)                    #a~zのどのbit配列か,特定文字のbit配列の何番目,bitに代入する値
        add(before_q3,q2,-1)    #置き代えた文字は-1しなきゃいけない
    elif q1==2:
        q3=int(q3)
        cnt=0
        for i in range(1,27):
            if 0<sum(i,q3)-sum(i,q2-1):
                cnt+=1
        print cnt

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
S=input()
Q=int(input())
D={}
A=["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"]
for i in range(26):
    D[A[i]]=i
n=1
while n<N:
    n*=2

seg=[0 for i in range(n*2)]
#print(seg)

for i in range(N):
    seg[n-1+i]=1<<D[S[i]]
    k=n-1+i
    while k>0:
        k=(k-1)//2
        seg[k]=(seg[k*2+1]|seg[k*2+2])
#print(list(bin(seg[0])).count("1"))

#0indexでa番目の値をbに変更
def update(a,b):
    a+=n-1
    seg[a]=1<<D[b]
    while a>0:
        a=(a-1)//2
        seg[a]=(seg[a*2+1]|seg[a*2+2])

#print(seg)

#A～B-1(0-index)までの累積和を求める
#1～2までの累積和なら(1,3,0,0,n)
#Kは接点番号？L,Rはその接点が[L,R)に対応づいていることを表す？
#外部からはquery(A,B,0,0,n)として呼び出す
def query(A,B,K,L,R):
    if K>=len(seg):
        return 0
    if R<=A or B<=L:
        return 0
    elif A<=L and R<=B:
        return seg[K]
    else:
        vl=query(A,B,K*2+1,L,(L+R)//2)
        vr=query(A,B,K*2+2,(L+R)//2,R)
        #print(vl,vr)
        return vl|vr
#print(n,len(seg))
#print("P",query(2,4,0,0,n),len(query(2,4,0,0,n)))
#update(3,"a")
#print(seg)
#print(query(2,4,0,0,n))
for i in range(Q):
    x,y,z=list(input().split())
    if x=="1":
        update(int(y)-1,z)
    else:
        print(list(bin(query(int(y)-1,int(z),0,0,n))).count("1"))

Submission status: Accepted

Solution code:
class SegmentTree(object):  # 1-indexed
    def __init__(self, size, S):
        self.len = 1 << size.bit_length()

        self.array = [0] * (2 * self.len)
        for i, s in enumerate(S):
            self.array[i + self.len] = 1 << (ord(s) - ord('a'))
        for i in range(self.len - 1, 0, -1):
            self.array[i] = self.array[i * 2] | self.array[i * 2 + 1]

    def query1(self, i, x):
        i += self.len
        self.array[i] = 1 << (ord(x) - ord('a'))
        i >>= 1
        while i > 0:
            self.array[i] = self.array[i * 2] | self.array[i * 2 + 1]
            i >>= 1

    def get(self, i):
        return self.array[i + self.len]

    def query(self, l, r, i, a, b):
        if l == a and r == b:
            return self.array[i]
        center = (a + b) // 2
        if center >= r:
            return self.query(l, r, i * 2, a, center)
        elif center <= l:
            return self.query(l, r, i * 2 + 1, center, b)
        else:
            return self.query(l, center, i * 2, a, center) | self.query(center, r, i * 2 + 1, center, b)

    def query2(self, l, r):
        ans = self.query(l - 1, r, 1, 0, self.len)
        print(bin(ans).count('1'))


N = int(input())
S = input()
tree = SegmentTree(N, S)
Q = int(input())

for _ in range(Q):
    a, b, c = map(str, input().split())
    if a == "1":
        b = int(b)
        tree.query1(b-1, c)
    else:
        b = int(b)
        c = int(c)
        tree.query2(b, c)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


class Seg():
    def __init__(self, na, default, func):
        if isinstance(na, list):
            n = len(na)
        else:
            n = na
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        if isinstance(na, list):
            self.A = [default] * (self.N) + na + [default] * (self.N-n)
            for i in range(self.N-1,0,-1):
                self.A[i] = func(self.A[i*2], self.A[i*2+1])
        else:
            self.A = [default] * (self.N*2)
        self.F = func

    def find(self, i):
        return self.A[i + self.N]

    def update(self, i, x):
        i += self.N
        self.A[i] = x
        while i > 1:
            i = i // 2
            self.A[i] = self.merge(self.A[i*2], self.A[i*2+1])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[1]

    def query(self, a, b):
        A = self.A
        l = a + self.N
        r = b + self.N
        res = self.D
        while l < r:
            if l % 2 == 1:
                res = self.merge(res, A[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = self.merge(res, A[r])
            l >>= 1
            r >>= 1

        return res

def main():
    n = I()
    s = S()
    q = I()
    qa = [LS() for _ in range(q)]
    aa = [[0]*26]
    oa = ord('a')
    for c in s:
        t = [0] * 26
        t[ord(c) - oa] = 1
        aa.append(t)

    def f(a,b):
        return [a[i]+b[i] for i in range(26)]

    seg = Seg(aa,[0]*26,f)
    r = []
    for t,a,b in qa:
        if t == '1':
            u = [0] * 26
            u[ord(b) - oa] = 1
            seg.update(int(a),u)
        else:
            c = seg.query(0,int(a))
            d = seg.query(0,int(b)+1)
            r.append(len([1 for i in range(26) if c[i] != d[i]]))

    return JA(r, '\n')


print(main())

Submission status: Accepted

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

N = int(input())
S = list(input().rstrip())
ord_a = ord("a")

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

bits = [Bit(N) for _ in range(26)]

for i in range(N):
    s = S[i]
    bits[ord(s) - ord_a].add(i + 1, 1)

Q = int(input())

for _ in range(Q):
    query = input().rstrip().split()
    if query[0] == "1":
        i, c = int(query[1]), query[2]
        bits[ord(S[i - 1]) - ord_a].add(i, -1)
        S[i - 1] = c
        bits[ord(S[i - 1]) - ord_a].add(i, 1)
    else:
        l, r = int(query[1]), int(query[2])
        res = 0
        for bit in bits:
            if l != 1:
                res += int(bit.sum(r) - bit.sum(l - 1) > 0)
            else:
                res += int(bit.sum(r) > 0)
        print(res)

Submission status: Accepted

Solution code:
from bisect import bisect_left,insort_left
n=int(input())
s=list(input())
lindex=[[] for _ in range(26)]
for i in range(n):
  lindex[ord(s[i])-97].append(i)
q=int(input())
for i in range(q):
  q1,q2,q3=input().split()
  if q1=='1':
    q2=int(q2)-1
    idx=bisect_left(lindex[ord(s[q2])-97],q2)
    if s[q2]!=q3:
      del lindex[ord(s[q2])-97][idx]
      insort_left(lindex[ord(q3)-97],q2)
      s[q2]=q3
  else:
    l=int(q2)-1
    r=int(q3)-1
    cnt=0
    for j in range(26):
      if len(lindex[j])==0:
        continue
      idx=bisect_left(lindex[j],l)
      if len(lindex[j])>idx and lindex[j][idx]<=r:
        cnt+=1
    print(cnt)

Submission status: Accepted

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()


def func(a, b):
    if a | b == 0:
        return 0
    else:
        return 1


class SegmentTree:
    """
    各ノードが半開区間に対応した完全二分木。
    子は親を半分にした区間を持つ。
    構築O(n), 区間に対する操作O(logn), 値の更新O(logn)
    区間に対する操作は最小値, 最大値, 区間に対する和など柔軟に変更して用いよう！
    """

    def __init__(self, x, init_val):  # 構築, init_valは配列の初期値
        self.init_val = init_val
        self.length = 2 ** ((len(x) - 1).bit_length())
        self.data = [init_val] * 2 * self.length
        for i in range(len(x)):
            self.data[i + self.length - 1] = x[i]
        for i in range(self.length - 2, -1, -1):
            self.data[i] = func(self.data[2 * i + 1], self.data[2 * i + 2])

    def teach_current_val(self, index):
        return self.data[index + self.length - 1]

    def replace(self, index, val):  # indexの値をvalに更新
        index += self.length - 1
        self.data[index] = val
        while index:
            index = (index - 1) // 2
            self.data[index] = func(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):  # 半開区間の最小値等を求める, 葉からさかのぼっていくイメージ。
        if right <= left:
            return self.init_val
        left += self.length - 1  # self.dataの位置に合わせる。
        right += self.length - 2  # self.dataの位置に合わせる。半開区間
        ans_ = self.init_val
        while right > left + 1:
            if left & 1 == 0:  # if left_index%2 == 0:
                ans_ = func(ans_, self.data[left])
            if right & 1 == 1:  # if right_index%2 == 1:
                ans_ = func(ans_, self.data[right])
                right -= 1
            left //= 2
            right = (right - 1) // 2
        if left == right:
            ans_ = func(ans_, self.data[left])
        else:
            ans_ = func(func(ans_, self.data[left]), self.data[right])
        return ans_


N = int(input())
S = input()
Q = int(input())
alphabets = string.ascii_lowercase
segs = []
check = dict()
for i in alphabets:
    segs.append([1 if S[l] == i else 0 for l in range(N)])
for i in range(26):
    segs[i] = SegmentTree(segs[i], 0)
for _ in range(Q):
    Query = list(map(str, input().split()))
    if Query[0] == "1":
        i, c = int(Query[1]), Query[2]
        if check.get(str(i - 1)):
            segs[ord(check[str(i - 1)]) - 97].replace(i - 1, 0)
            segs[ord(c) - 97].replace(i - 1, 1)
            check[str(i - 1)] = c
        else:
            segs[ord(S[i - 1]) - 97].replace(i - 1, 0)
            segs[ord(c) - 97].replace(i - 1, 1)
            check[str(i - 1)] = c
    else:
        l, r = map(int, (Query[1], Query[2]))
        ans = 0
        for i in segs:
            ans += i.query(l - 1, r)
        print(ans)

Submission status: Accepted

Solution code:
class BinaryIndexTree:  # 1-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def Alp(s):
    return ord(s)-ord("a")


if __name__ == "__main__":
    N = int(input())
    S = list(input())
    Q = int(input())

    bit = [BinaryIndexTree(N) for _ in range(26)]
    for i, s in enumerate(S, start=1):
        bit[Alp(s)].add(i, 1)

    ans = []
    for _ in range(Q):
        q = input().split()
        if q[0] == "1":
            i = int(q[1]) - 1
            c = q[2]

            bit[Alp(c)].add(i+1, 1)
            bit[Alp(S[i])].add(i+1, -1)
            S[i] = c
        else:
            l = int(q[1])
            r = int(q[2])
            tmp = 0
            for i in range(26):
                b = bit[i]
                if b.sum(r) - b.sum(l - 1) > 0:
                    tmp += 1
            ans.append(tmp)

    print(*ans, sep="\n")

Submission status: Accepted

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

n = int(input())
s = str(input())
A = list(s)
A = A[0:n]

A = [{ord(c)-ord('a')} for c in A]
#print(A)

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

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

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

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

# identity element
ide_ele = set()

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

init(A)

q = int(input())

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

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    S = input().rstrip()
    S = [conv(c) for c in S]
    segtree = SegmentTree(initial_values=S, f=lambda x,y:x|y)

    Q = int(input())
    for _ in range(Q):
        t, a, b = input().rstrip().split()
        if t == '1':
            a = int(a) - 1
            segtree.set_val(a, conv(b))
        else:
            a, b = int(a) - 1, int(b)
            q = segtree.query(a, b)
            print(popcount(q))

def conv(c): return 1 << (ord(c) - ord('a'))
def popcount(x):
    x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555)
    x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333)
    x = x + (x >> 4) & 0x0f0f0f0f0f0f0f0f
    x += x >> 8
    x += x >> 16
    x += x >> 32
    return x & 0x7f

class SegmentTree:
    def __init__(self, n=None, f=max, identity_factory=int, initial_values=None):
        assert(n or initial_values)
        size = n if n else len(initial_values)
        d = [identity_factory() for _ in range(2 * size + 1)]
        self.__n, self.__d, self.__f, self.__e = size, d, f, identity_factory
        if initial_values:
            for i, v in enumerate(initial_values): d[size + i] = v
            for i in range(size - 1, 0, -1): d[i] = f(d[i<<1], d[i<<1|1])

    def get_val(self, index):
        return self.__d[index + self.__n]

    def set_val(self, index, value):
        i, d, f = index + self.__n, self.__d, self.__f
        if d[i] == value: return
        d[i] = value
        while i:
            i = i >> 1
            d[i] = f(d[i<<1], d[i<<1|1])

    def modify(self, index, value):
        self.set_val(index, self.__f(self.__d[index + self.__n], value))

    def query(self, from_inclusive, to_exclusive):
        ans = self.__e()
        if to_exclusive <= from_inclusive: return ans
        l, r, d, f = from_inclusive + self.__n, to_exclusive + self.__n, self.__d, self.__f
        while l < r:
            if l & 1: ans, l = f(ans, d[l]), l+1
            if r & 1: ans, r = f(d[r-1], ans), r-1
            l, r = l >> 1, r >> 1
        return ans

    def bisect_left(self, func):
        '''func()がFalseになるもっとも左のindexを探す
        '''
        i, n, f, d, v = 1, self.__n, self.__f, self.__d, self.__e()
        while i < n:
            if func(f(v, d[i<<1])): v, i = f(v, d[i<<1]), i<<1|1
            else: i = i<<1
        return i - n


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:       
            s += self.tree[i] 
            i -= i & -i       
        return s                            
                                            
    def add(self, i, x):                  
        while i <= self.size:
            self.tree[i] += x  
            i += i & -i
x = "abcdefghijklmnopqrstuvwxyz"
N, = map(int, input().split())
d = dict()
for c in x:
    d[c] = Bit(N+1)

S = list(input().strip())
for i, c in enumerate(S):
    d[c].add(i+1, 1)

Q = int(input())
for _ in range(Q):
    t, a, b = input().split()
    if t == '1':
        i, c = int(a), b
        b = S[i-1]
        S[i-1] = c
        d[b].add(i, -1)
        d[c].add(i, 1)
    else:
        l, r = int(a), int(b)
        rr = 0
        for c in x:
            if d[c].sum(r) - d[c].sum(l-1) > 0:
                rr += 1
        print(rr)