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
import sys

input = sys.stdin.readline
num2alpha = lambda c: chr(c + 97)
alpha2num = lambda c: ord(c) - ord("a")


class SegTreeMax:
    def __init__(self, l):
        self.N = 1
        while self.N < l:
            self.N *= 2
        self.L = [0 for _ in range(self.N * 2 - 1)]

    def update(self, k, v):
        k += self.N - 1
        self.L[k] = v
        while k > 0:
            k = (k - 1) // 2
            self.L[k] = max(self.L[k * 2 + 1], self.L[k * 2 + 2])

    def append(self, k, v):
        k += self.N - 1
        self.L[k] += 2 ** v
        while k > 0:
            k = (k - 1) // 2
            self.L[k] = self.L[k * 2 + 1] | self.L[k * 2 + 2]

    def delete(self, k, v):
        k += self.N - 1
        self.L[k] -= 2 ** v
        while k > 0:
            k = (k - 1) // 2
            self.L[k] = self.L[k * 2 + 1] | self.L[k * 2 + 2]

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

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


def main():
    N = int(input())
    Stri = input()
    L = []
    for c in Stri:
        L.append(c)
    Q = int(input())
    S = SegTreeMax(N)
    for i in range(N):
        S.append(i, alpha2num(L[i]))

    for _ in range(Q):
        a, b, c = input().split()
        if a == "1":
            i = int(b) - 1
            S.delete(i, alpha2num(L[i]))
            L[i] = c
            S.append(i, alpha2num(c))

        else:
            l = int(b) - 1
            r = int(c)
            res = S.query(l, r)
            p = 0
            for i in range(26):
                p += res & 1
                res >>= 1
            print(p)


main()

Submission status: Accepted

Solution code:
from collections import Counter
def snum(x):
    return ord(x)-ord('a')

class Bit:
    def __init__(self, n,ls):
        self.size=n
        self.tree=[[0]*26 for _ in range(n+1)]
        self.ls=['']*(n+1)

    def sum(self, i, j):
        i-=1
        res=[0]*26
        for k in range(26):
            i2=i
            j2=j
            while j2>0:
                res[k] += self.tree[j2][k]
                j2 -= j2&-j2
            while i2>0:
                res[k] -= self.tree[i2][k]
                i2 -= i2&-i2
        return 26-res.count(0)
    
    def add(self, i, x):
        self.ls[i] = x
        while i <= self.size:
            self.tree[i][snum(x)]+=1
            i += i & -i

    def change(self, i, x):
        original = self.ls[i]
        self.ls[i]=x
        while i <= self.size:
            self.tree[i][snum(original)] -= 1
            self.tree[i][snum(x)] += 1
            i += i & -i
        

n = int(input())
s = list(input())
bit=Bit(n,s)

for i in range(n):
    bit.add(i+1, s[i])

q = int(input())
for _ in range(q):
    query, a, b = input().split()
    if query=='1':
        bit.change(int(a),b)
    else:
        print(bit.sum(int(a), int(b)))

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, a):    
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        l = []
        for _a in a:
            l.append(1 << ord(_a)-97)
        self.data = [0]*(self.N-1) + l + [0]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.data[(i-1)//2] = self.data[i] | self.data[i-1]
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.data[idx] = 1 << ord(x)-97
        while idx:
            idx = (idx-1) // 2
            self.data[idx] = self.data[2*idx+1] | self.data[2*idx+2]
    
    def query(self, i, j):
        # [i, j)
        if i == j:
            return bin(self.data[self.N - 1 + i]).count('1')
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            b = 0
            while idx1 + 1 < idx2:
                if idx1&1 == 0: # idx1が偶数
                    b = b | self.data[idx1]
                if idx2&1 == 1: # idx2が奇数
                    b = b | self.data[idx2]
                    idx2 -= 1
                
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            
            if idx1 == idx2:
                b = b | self.data[idx1]
            else: # idx1 + 1 == idx2
                b = b | self.data[idx1] | self.data[idx2]
            
            return bin(b).count('1')

N = int(input())
S = list(input())
st = SegmentTree(S)

Q = int(input())
for i in range(Q):
  t, a, b = input().split()
  if t == '1':
    a = int(a)
    if S[a-1] == b:
      continue
    st.update(a-1, b)
    S[a-1] = b
  else:
    a, b = int(a), int(b)
    print(st.query(a-1, b))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
S = input()
Q = int(input())

ide_ele = 0

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

def init(init_val):
    #set_val
    for i in range(N):
        seg[i+num-1]=1<<(ord(init_val[i])-ord('a'))
    #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
    x = 1<<(ord(x)-ord('a'))
    if x == seg[k]: return
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

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

init(S)

for _ in range(Q):
    t, a, b = input().split()
    if t == '1':
        a = int(a)
        update(a-1, b)
    else:
        a, b = int(a)-1, int(b)
        print(bin(query(a,b)).count('1'))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return input().split()
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size

    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        i = 1
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i

    def __len__(self):
        return self.size

#solve
def solve():
    n = II()
    s = S()
    q = II()
    ans = [BinaryIndexedTree(n + 1) for i in range(27)]
    lis = [ord(si) - ord("a") for si in s]
    for i in range(n):
        ans[lis[i]].add(i+1, 1)
    for _ in range(q):
        t, i, c = LS()
        i = int(i)
        if t == "1":
            ans[lis[i-1]].add(i, -1)
            ans[ord(c) - ord("a")].add(i, 1)
            lis[i-1] = ord(c) - ord("a")
        else:
            l = i - 1
            r = int(c)
            res = 0
            for i in range(27):
                res += ans[i].sum(r) - ans[i].sum(l) > 0
            print(res)
    


    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


class SegTree:
    """
    今回の問題に特化したセグ木
    """

    def __init__(self, n, s):
        """
        :param n: 文字列長
        :param s: 初期文字列
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [None] * n2 + [{} for _ in range(n2)]
        lmd0 = lambda: 0

        for i, c in enumerate(s):
            x = ord(c) - 97
            i += self.offset
            self.tree[i][x] = 1
        for i in range(self.offset - 1, 0, -1):
            sti = self.tree[i] = defaultdict(lmd0, self.tree[i << 1])
            stj = self.tree[(i << 1) + 1]
            for x in stj:
                sti[x] += stj[x]
        # print(*(dict(t) for t in self.tree), sep='\n')

    def update(self, i, x):
        """
        i番目の値をxに変更
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        if x in self.tree[i]:
            return
        y, _ = self.tree[i].popitem()
        self.tree[i][x] = 1
        i >>= 1
        while i > 0:
            sti = self.tree[i]
            sti[x] += 1
            if sti[y] == 1:
                del sti[y]
            else:
                sti[y] -= 1
            i >>= 1

    def get_types(self, a, b):
        """
        [a, b)の文字種数を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = set()

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result.update(self.tree[r - 1].keys())
            if l & 1:
                result.update(self.tree[l].keys())
                l += 1
            l >>= 1
            r >>= 1

        return len(result)


n = int(input())
s = input()
st = SegTree(n, s)
q = int(input())
ans = []
for line in sys.stdin:
    i, j, k = line.rstrip().split()
    if i == '1':
        j = int(j) - 1
        k = ord(k) - 97
        st.update(j, k)
    else:
        l = int(j) - 1
        r = int(k)
        ans.append(st.get_types(l, r))
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
import bisect
n = int(sys.stdin.readline().strip())
s = list(sys.stdin.readline().strip())
alpha = "abcdefghijklmnopqrstuvwxyz"
dict = {i:[] for i in alpha}
for i, _s in enumerate(s):
    dict[_s].append(i)
q = int(sys.stdin.readline().strip())
for i in range(q):
    type, first, last = [i for i in sys.stdin.readline().split()]
    if type == "2":
        first = int(first)
        last = int(last)
        first -= 1
        last -= 1
        cnt = 0
        for ls in dict.values():
            if bisect.bisect_left(ls, first) != bisect.bisect_right(ls, last):
                cnt += 1
        print(cnt)
    else:
        first = int(first)
        first -= 1
        _s = s[first]
        if _s == last:
            continue
        del dict[_s][(bisect.bisect_left(dict[_s], first))]
        s[first] = last
        bisect.insort_left(dict[last], first)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


class SegTree:
    def __init__(self, n, s):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [None] * n2 + [{} for _ in range(n2)]
        self.lmd0 = lambda: 0

        for i, c in enumerate(s):
            x = ord(c) - 97
            i += self.offset
            self.tree[i][x] = 1
        for i in range(self.offset - 1, 0, -1):
            sti = self.tree[i] = defaultdict(self.lmd0, self.tree[i << 1])
            stj = self.tree[(i << 1) + 1]
            for x in stj:
                sti[x] += stj[x]
        # print(*(dict(t) for t in self.tree), sep='\n')

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        if x in self.tree[i]:
            return
        y, _ = self.tree[i].popitem()
        self.tree[i][x] = 1
        i >>= 1
        while i > 0:
            sti = self.tree[i]
            sti[x] += 1
            if sti[y] == 1:
                del sti[y]
            else:
                sti[y] -= 1
            i >>= 1

    def get_types(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = set()

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result.update(self.tree[r - 1].keys())
            if l & 1:
                result.update(self.tree[l].keys())
                l += 1
            l >>= 1
            r >>= 1

        return len(result)


n = int(input())
s = input()
st = SegTree(n, s)
q = int(input())
ans = []
for line in sys.stdin:
    i, j, k = line.rstrip().split()
    if i == '1':
        j = int(j) - 1
        k = ord(k) - 97
        st.update(j, k)
    else:
        l = int(j) - 1
        r = int(k)
        ans.append(st.get_types(l, r))
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
class SegmentTree:
	def __init__(self, orig, func, unit):
		_len = len(orig)
		self.func = func
		self.size = 1 << (_len - 1).bit_length()
		self.tree = [unit] * self.size + orig + [unit] * (self.size - _len)
		self.unit = unit

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

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

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

import sys
input = sys.stdin.readline
from operator import or_

def main():
	input()
	seg = SegmentTree([1 << ord(x) - 97 for x in input()[:-1]], or_, 0)
	ans = []
	for _ in range(int(input())):
		f, x, y = input().split()
		if f == "1":
			seg.update(int(x) - 1, 1 << ord(y) - 97)
		else:
			ans.append(bin(seg.find(int(x) - 1, int(y))).count("1"))
	print(*ans)

if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
class SegmentTree():
    def __init__(self,arr,func=min,ie=2**63):
        self.n = 2**(len(arr)-1).bit_length()
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2*self.n)]
        for i in range(len(arr)):
            self.tree[self.n+i-1] = arr[i]
        for i in range(self.n-1)[::-1]:
            self.tree[i] = func(self.tree[2*i+1],self.tree[2*i+2])

    def set(self,index,x):
        index += self.n-1
        self.tree[index] = x
        while index:
            index = (index-1)//2
            self.tree[index] = self.func(self.tree[2*index+1],self.tree[2*index+2])

    def query(self,left,right):
        if right <= left:
            return self.ie
        left += self.n-1
        right += self.n-2
        tmp_l = self.ie
        tmp_r = self.ie
        while right-left>1:
            if left & 1 == 0:
                tmp_l = self.func(tmp_l,self.tree[left])
            if right & 1 == 1:
                tmp_r = self.func(self.tree[right],tmp_r)
                right -= 1
            left = left//2
            right = (right-1)//2
        if left == right:
            tmp_l = self.func(tmp_l,self.tree[left])
        else:
            tmp_l = self.func(self.func(tmp_l,self.tree[left]),self.tree[right])
        return self.func(tmp_l,tmp_r)

import sys
input = sys.stdin.readline

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

A = []
for i in range(N):
    A.append(set([ord(S[i])-97]))

def func(x,y):
    return x|y
ie = set()

st = SegmentTree(A,func,ie)

ans = []

for _ in range(Q):
    q,x,y = input().split()
    q = int(q)
    if q == 1:
        st.set(int(x)-1,set([ord(y)-97]))
    else:
        ans.append(len(st.query(int(x)-1,int(y))))

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

Submission status: Accepted

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)

    if i != len(a) and a[i] == x:
        return i
    raise ValueError

# ポイント
# 文字列update
# 文字種の高速取得

# 文字種の高速取得について考えてみる
# 文字のidxを取得しておいて二分探索することで高速に取得することが可能


N = read_a_int()
S = list(read()[:-1])

from collections import defaultdict
from bisect import bisect_left, bisect_right, insort_left
char_idxs = defaultdict(lambda: [])
for i, s in enumerate(S):
    char_idxs[s].append(i)


def get_syurui(char_idxs, l, r):
    ret = 0
    for v in char_idxs.values():
        l_idx = bisect_left(v, l)
        r_idx = bisect_right(v, r)
        # print(v,l_idx,r_idx)
        if r_idx - l_idx > 0:
            ret += 1
    return ret


Q = read_a_int()
for q in range(Q):
    com, a, b = read().split()
    if int(com) == 2:
        a, b = int(a) - 1, int(b) - 1
        print(get_syurui(char_idxs, a, b))
    else:
        i = int(a) - 1
        if S[i] == b:
            continue
        # i文字目を消す
        tmp = char_idxs[S[i]]  # S[i]を更新しなきゃ
        del char_idxs[S[i]][index(tmp, i)]
        # cのidxに挿入し直す
        insort_left(char_idxs[b], i)
        # S[i]を更新しなきゃ
        S[i] = b

Submission status: Accepted

Solution code:
"""
E
"""
#treeのiに1を加える
def bit_add(I,k):
    while I<=N:
        tree[k][I]+=1
        I+=I&(-I)

def bit_no_add(I,k):
    while I<=N:
        tree[k][I]-=1
        I+=I&(-I)
        
#0からiまでの合計を帰す
def bit_sum(I,k):
    s=0
    while I>0:
        s+=tree[k][I]
        I-=I&(-I)
    return s

N=int(input())
S=["a"]+list(input())
Q=int(input())
que=[list(input().split()) for i in range(Q)]

alpa=list("abcdefghijklmnopqrstuvwxyz")
tree=[[0]*(N+1) for i in range(len(alpa))]

for i in range(1,N+1):
    j=alpa.index(S[i])
    bit_add(i, j)

for iii in range(Q):
    if que[iii][0]=="1":
        i,c=int(que[iii][1]),que[iii][2]
        j=alpa.index(S[i])
        bit_no_add(i, j)
        S[i]=c
        j=alpa.index(c)
        bit_add(i, j)
    else:
        l,r=que[iii][1],que[iii][2]
        l=int(l)
        r=int(r)
        cnt=0
        for j in range(len(alpa)):
            if bit_sum(l-1, j)==bit_sum(r, j):
                continue
            cnt+=1
        print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict

alpha = defaultdict(int)
num = 0
for i in sorted(map(chr,range(97,123))):
    alpha[i] = 1 << num
    num += 1

n = int(input())
S = tuple(alpha[i] for i in input())

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] = 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] = seg[k*2+1] | seg[k*2+2]
    
def query(p,q):
    if q<=p:
        return 0
    p += num-1
    q += num-2
    res=0
    while q-p>1:
        if p&1 == 0:
            res |= seg[p]
        if q&1 == 1:
            res |= seg[q]
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res |= seg[p]
    else:
        res |= (seg[p] | seg[q])
    cnt = 0
    i = 0
    while res:
        cnt += res & 1
        i += 1
        res >>= 1
    return cnt
#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[0 for _ in range(2*num)]

init(S)

Q = int(input())
for _ in range(Q):
    x,y,z = map(str,input().split())
    x = int(x); y = int(y)
    if x == 1:
        update(y-1, alpha[z])
    else:
        z = int(z)
        print(query(y-1,z))

Submission status: Accepted

Solution code:
import math
import collections

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

S = list(S)
def bit_add(A,a,w): #リストAのa番目にwを足す
    ind = a

    while len(A) > ind:
        A[ind] += w
        lsb = ind & (-ind)
        # print(ind)
        ind += lsb

    return

def bit_sum(A, a):  # リストAのa番目までの和を取る
    s = 0
    ind = a
    while ind != 0:
        s += A[ind]
        lsb = ind & (-ind)
        ind -= lsb

    return s
# cs = set(list(S))
li = {}
for c in "abcdefghijklmnopqrstuvwxyz":
    li[c] = [0] * (N + 1)

for i in range(1,N + 1):
    char = S[i - 1]
    bit_add(li[char],i,1)

# li → 1 スタート
# S → 0スタート
Q = int(input())
queries = [input().split() for _ in range(Q)]
for query in queries:
    a,b,c = query
    a = int(a)
    b = int(b)
    if a == 1: # 書き換え
        i = b

        c_org = S[i - 1] # 元の文字
        # li[c_org][i] -= 1
        S[i - 1] = c
        bit_add(li[c_org], i,  -1)#元の文字をbiマイナス
        bit_add(li[c], i, 1) #新たな文字をbiプラス

    if a == 2:
        ans = 0
        l = b
        r = int(c)
        for c in "abcdefghijklmnopqrstuvwxyz":
            temp = li[c]
            r_sum = bit_sum(temp,r)
            l_sum = bit_sum(temp,l - 1)
            diff = r_sum-l_sum
            if diff > 0: # ある文字
                ans += 1
        print(ans)

Submission status: Accepted

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

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

s = [ord(c)-ord('a') for c in s]

#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]=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] = seg[k*2+1] | seg[k*2+2]

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

#####単位元######
ide_ele = set()

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

init(s)
#print(seg)

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

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect_right,insort
N = int(input())
S = list(input())
Q = int(input())
D = dict()
D2 = dict()# to be removed
D3 = dict()# to be added

for i in range(97,97+26):
    D[chr(i)] = []
    D2[chr(i)] = []
    D3[chr(i)] = []
for i in range(N):
    D[S[i]].append(i+1)
for i in range(Q):
    t,l,r = input().split()
    if t == str(1):
        k = int(l)
        c = r
        if S[k-1] == c:
            continue
        if bisect_right(D[S[k-1]],k)-bisect_left(D[S[k-1]],k) == 1:
            del D[S[k-1]][bisect_left(D[S[k-1]],k)]
        insort(D[c],k)
        S[k-1] = c
        continue
    l = int(l)
    r = int(r)
    ans = 0
    for i in range(97,97+26):
        X = D[chr(i)]
        X2 = D2[chr(i)]
        X3 = D3[chr(i)]
        if bisect_right(X,r)-bisect_left(X,l) > 0:
            ans += 1
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
q=int(input())
dic=dict()
for i,j in enumerate("qwertyuioplkjhgfdsazxcvbnm"):
    dic[j]=i
No=2
while n>No:
    No*=2
tree=[set()]*(2*No)
def add(k,x):
    k+=No-1
    tree[k]=set([dic[x]])
    while k>0:
        k=(k-1)//2
        tree[k]=tree[2*k+1]|tree[2*k+2]
def query(l,r):
    L=l+No-1
    R=r+No-1
    s=set()
    while L<=R:
        if R&1:
            s|=tree[R]
            R-=2
        else:
            R-=1
        if L&1:
            L-=1
        else:
            s|=tree[L]
        L>>=1;R>>=1
    return len(s)
for i,j in enumerate(s):
    tree[i+No-1]=set([dic[j]])
for i in range(No-2,-1,-1):
    tree[i]=tree[2*i+1]|tree[2*i+2]
for i in range(q):
    a,b,c=input().split()
    a,b=int(a),int(b)
    if a==1:
        add(b-1,c)
    if a==2:
        c=int(c)
        print(query(b-1,c-1))

Submission status: Accepted

Solution code:
NN = 2020202
MOD = 10**9+7
INF = float("inf")


class BIT():
    def __init__(self, n):
        self.n = n
        self.bit = [[0]*26 for _ in range(self.n+1)]
        self.s = ["*"]*self.n

    def _sum(self, i):
        s = [0]*26
        while i > 0:
            for idx, v in enumerate(self.bit[i]):
                s[idx] += v
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目にvalを加える"""
        old = self.s[i-1]
        self.s[i - 1] = val
        # print(old, val)
        if old == val:
            return

        while i <= self.n:
            # print(i)
            self.bit[i][ord(val) - ord("a")] += 1
            if 0 <= ord(old) - ord("a") < 26:
                self.bit[i][ord(old) - ord("a")] -= 1

            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        A = self._sum(r)
        B = self._sum(l-1)
        # print(A, B)
        ans = 0
        for idx in range(26):
            if A[idx] > B[idx]:
                ans += 1

        return ans
        # return self._sum(r) - self._sum(l)


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

tree = BIT(N)
for i in range(N):
    tree.add(i+1, S[i])
# print(tree.bit)

for i in range(Q):
    if query[i][0] == "1":
        tree.add(int(query[i][1]), query[i][2])
        # print(tree.bit)
    if query[i][0] == "2":
        print(tree.get_sum(int(query[i][1]), int(query[i][2])))