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: Wrong Answer

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

input()
def lam(x,y):
  return x|y
seg = SegmentTree([set(x) for x in input()[:-1]],lam, set())
ans = []
for _ in range(int(input())):
  f, x, y = input().split()
  if f == "1":
    seg.update(int(x) - 1, set(y))
  else:
    ans.append(len(seg.find(int(x) - 1, int(y))))
print(*ans)

Submission status: Wrong Answer

Solution code:
from string import ascii_lowercase
import sys


def input():
    return sys.stdin.readline().strip()


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

sets = {c: set() for c in ascii_lowercase}
[sets[c].add(i) for i, c in enumerate(s, 1)]
queries = (input().split() for _ in range(q))

ans = []
for q_type, *q in queries:
    if q_type == '1':
        iq = int(q[0])
        cq = q[1]
        for c in ascii_lowercase:
            if iq in sets[cq]:
                sets[cq].remove(iq)
                break
        sets[cq].add(iq)
    else:
        l, r = map(int, q)
        indices = set(range(l, r + 1))
        print(sum([bool(indices & v) for v in sets.values()]))

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = ord("a")
    orda = lambda x: ord(x)-a
    s = list(map(orda, list(input())))
    q = int(input())
    bits = [BIT(n) for _ in range(26)]
    for i, si in enumerate(s, 1):
        bits[si].add(i, 1)
    for _ in range(q):
        t, i, c = input().split()
        i = int(i)
        if t == "1":
            bits[s[i-1]].add(i, -1)
            bits[ord(c)-a].add(i, 1)
        else:
            c = int(c)
            cnt = 0
            for bit in bits:
                is_in = bit.sum_(c) - bit.sum_(i-1)
                if is_in:
                    cnt += 1
            print(cnt)


class BIT:
    __slots__ = ["length", "data"]
    def __init__(self, length):
        self.data = [0]*(length+1)
        self.length = length
    
    def add(self, i, x):
        while i < self.length+1:
            self.data[i] += x
            i += i&-i
    
    def sum_(self, i):
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i&-i
        return x



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = ord("a")
    orda = lambda x: ord(x)-a
    s = list(map(orda, list(input())))
    q = int(input())
    bits = [BIT(n) for _ in range(26)]
    for i, si in enumerate(s):
        bits[si].add(i, 1)
    for _ in range(q):
        t, i, c = input().split()
        i = int(i)-1
        if t == "1":
            bits[s[i]].add(i, -1)
            bits[ord(c)-a].add(i, 1)
        else:
            c = int(c)-1
            cnt = 0
            for bit in bits:
                is_in = bit.sum_(c) - bit.sum_(i-1)
                if is_in:
                    cnt += 1
            print(cnt)


class BIT:
    __slots__ = ["length", "data"]
    def __init__(self, length):
        self.data = [0]*(length+1)
        self.length = length
    
    def add(self, i, x):
        i += 1
        while i < self.length+1:
            self.data[i] += x
            i += i&-i
    
    def sum_(self, i):
        x = 0
        i += 1
        while i > 0:
            x += self.data[i]
            i -= i&-i
        return x



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = ord("a")
    orda = lambda x: ord(x)-a
    s = list(map(orda, list(input())))
    q = int(input())
    init_list = [[0]*n for _ in range(26)]
    for i, si in enumerate(s):
        init_list[si][i] = 1
    bits = [BIT(i, n) for i in init_list]
    for _ in range(q):
        t, i, c = input().split()
        i = int(i)-1
        if t == "1":
            bits[s[i]].add(i, -1)
            bits[ord(c)-a].add(i, 1)
        else:
            c = int(c)-1
            cnt = 0
            for bit in bits:
                is_in = bit.sum_(c) - bit.sum_(i-1)
                if is_in:
                    cnt += 1
            print(cnt)


class BIT:
    __slots__ = ["length", "data"]
    def __init__(self, array, length):
        self.data = [0]*(length+1)
        self.length = length
        for i, val in enumerate(array):
            self.add(i, val)
    
    def add(self, i, x):
        i += 1
        while i < self.length+1:
            self.data[i] += x
            i += i&-i
    
    def sum_(self, i):
        x = 0
        i += 1
        while i > 0:
            x += self.data[i]
            i -= i&-i
        return x



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

from math import ceil

class Segtree:
    def __init__(self, begin, size, s):
        self.begin = begin
        self.size = size
        self.counter = [0 for i in range(26)]
        for c in s[begin - 1:begin + size - 1]:
            ci = ord(c) - ord("a")
            self.counter[ci] += 1
        if size == 1:
            self.left = None
            self.right = None
            self.ci = ci
        else:
            sl = ceil(size / 2.0)
            sr = size - sl
            self.left = Segtree(begin, sl, s)
            self.right = Segtree(begin + sl, sr, s)

    def change_ith_to_c(self, i1, ci):
        if self.size == 1:
            prev = self.ci
            self.ci = ci
        else:
            sl = ceil(self.size / 2.0)
            child = self.left if i1 <= self.begin + sl - 1 else self.right
            prev = child.change_ith_to_c(i1, ci)
        self.counter[prev] -= 1
        self.counter[ci] += 1
        return prev

    def qt2(self, l, r):
        if l == self.begin and r == self.begin + self.size - 1:
            return {ci for ci in range(26) if self.counter[ci]}
        sl = ceil(self.size / 2.0)
        center = self.begin + sl - 1  # End of left
        if r <= center:
            return self.left.qt2(l, r)
        elif l > center:
            return self.right.qt2(l, r)
        else:
            return self.left.qt2(l, center) | self.right.qt2(center + 1, r)

    def __repr__(self):
        return "[{} {} {} {}]".format(self.begin, self.begin + self.size - 1,
            repr(self.left), repr(self.right))

def main():
    n = int(input())
    s = input()
    st = Segtree(1, n, s)
    q = int(input())
    for i in range(q):
        t, l, r = input().split()
        if t == "1":
            ci = ord(r) - ord("a")
            st.change_ith_to_c(int(l), ci)
        else:
            continue
            print(len(st.qt2(int(l), int(r))))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

from math import ceil

class Segtree:
    def __init__(self, begin, size, s):
        self.begin = begin
        self.size = size
        self.counter = [0 for i in range(26)]
        for c in s[begin - 1:begin + size - 1]:
            ci = ord(c) - ord("a")
            self.counter[ci] += 1
        if size == 1:
            self.left = None
            self.right = None
            self.ci = ci
        else:
            sl = ceil(size / 2.0)
            sr = size - sl
            self.left = Segtree(begin, sl, s)
            self.right = Segtree(begin + sl, sr, s)

    def change_ith_to_c(self, i1, ci):
        if self.size == 1:
            prev = self.ci
            self.ci = ci
        else:
            sl = ceil(self.size / 2.0)
            child = self.left if i1 <= self.begin + sl - 1 else self.right
            prev = child.change_ith_to_c(i1, ci)
        self.counter[prev] -= 1
        self.counter[ci] += 1
        return prev

    def qt2(self, l, r):
        if l == self.begin and r == self.begin + self.size - 1:
            return {ci for ci in range(26) if self.counter[ci]}
        sl = ceil(self.size / 2.0)
        center = self.begin + sl - 1  # End of left
        if r <= center:
            return self.left.qt2(l, r)
        elif l > center:
            return self.right.qt2(l, r)
        else:
            return self.left.qt2(l, center) | self.right.qt2(center + 1, r)

    def __repr__(self):
        return "[{} {} {} {}]".format(self.begin, self.begin + self.size - 1,
            repr(self.left), repr(self.right))

def main():
    n = int(input())
    s = input()
    st = Segtree(1, n, s)
    q = int(input())
    for i in range(q):
        t, l, r = input().split()
        if t == "1":
            continue
            ci = ord(r) - ord("a")
            st.change_ith_to_c(int(l), ci)
        else:
            print(len(st.qt2(int(l), int(r))))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class Segment_tree():
    def __init__(self, n, string):
        self.inf = pow(2, 32)
        self.n = n
        self.string = string
        self.N = 1
        while self.N < self.n:
            self.N *= 2
        self.size = self.N * 2
        self.size -= 1
        self.N -= 1
        self.segment = [set()]*(self.N) + [set(self.string[i]) for i in range(self.n)] + [set()]*(self.size-self.N-self.n)
        for i in range(self.N-1, -1, -1):
            self.segment[i] = self.segment[2*i+1]|self.segment[2*i+2]
        
    def undate(self, i, x):
        
        self.segment[i] = set(x)
        while i > 0:
            i = (i-1)//2
            self.segment[i] = self.segment[2*i+1]|self.segment[2*i+2]
        
    def find(self, a, b, k, l, r):
        if r <= a or b <= l:
            return set()
        elif a <= l and r <= b:
            return self.segment[k]
        else:
            find_l = self.find(a, b, 2*k+1, l, (l+r)//2)
            find_r = self.find(a, b, 2*k+2, (l+r)//2, r)
            return find_l|find_r
    
    def count(self, a, b):
        return len(self.find(a, b, 0, 0, self.size-self.N))


def main():
    n = int(input())
    s = input()
    segment = Segment_tree(n, s)
    q = int(input())
    for i in range(q):
        query = [str(x) for x in input().split()]
        if query[0] == "1":
            segment.undate(int(query[1])+n-1, query[2])
        else:
            l, r = int(query[1])-1, int(query[2])
            print(segment.count(l, r))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#単位元を設定
ide = 0

class SegmentTree:
	def __init__(self,n):
        #セグ木の頂点はindex == 1から。index == 0は無視すること。
        #つまり、STtable[0]は無視。頂点はSTtable[1]。
		self.n = n
		tmp = 0
		while True:
			if 2 ** tmp >= self.n:
				break
			tmp += 1
		self.STtable = [ide] * (2*2**tmp)
		self.STtable_size = len(self.STtable)

	def update(self,i,a):
        #更新のためのインデックスの指定は0_indexedで。
		a_bit = 1 << ord(a)-97
		i += self.STtable_size//2
		self.STtable[i] = a_bit
		while i > 0:
			i //= 2
			self.STtable[i] = self.STtable[i*2] | self.STtable[i*2+1]

	def find(self,a,b,k=1,l=0,r=None):
        #kは頂点番号。初期値は1にすること。
		#[a,b)の最小を返す。
		#[l,r)からです。
        #初期値のrは、self.STtable_size//2にすると、ちょうど要素数と同じ値になって[l,r)のrになる。
        #問題に適するように範囲を指定するように注意。大体[l,r]で指定されている。
		if r == None:
			r = self.STtable_size//2        
		if a >= r or b <= l:
			return ide
		elif a <= l and b >= r:
			return self.STtable[k]
		else:
			mid = (l+r)//2
			if b <= mid:
				return self.find(a,b,2*k,l,mid)
			elif a >= mid:
				return self.find(a,b,2*k+1,mid,r)
			else:
				v1 = self.find(a,mid,2*k,l,mid)
				v2 = self.find(mid,b,2*k+1,mid,r)
			return v1 | v2

N = int(input())
solve = SegmentTree(N)
S = input()
for i in range(N):
	solve.update(i,S[i])
Q = int(input())
ans = []
print(solve.STtable)
for _ in range(Q):
	a,b,c = map(str, input().split())
	if a == '1':
		solve.update(int(b)-1,c)
		print(solve.STtable)
	else:
		tmp = solve.find(int(b)-1,int(c))
		cnt = 0
		for i in range(26):
			if tmp >> i & 1 == 1:
				cnt += 1
		ans.append(cnt)

for a in ans:
	print(a)

Submission status: Wrong Answer

Solution code:
class SegTree():
    def __init__(self,size):
        self.size = 2 ** size.bit_length()
        self.tree_size = 2 * self.size
        self.tree = [0 for _ in range(self.tree_size)]

    def update(self,i,v):
        index = self.size + i
        while index > 0:
            self.tree[index] += v
            index = index // 2

    def search_count(self,l,r):
        l += self.size
        r += self.size

        lcnt,rcnt = 0,0

        while l != r:
            if l & 1:
                lcnt += self.tree[l]
                l += 1
            if r & 1:
                r -= 1
                rcnt += self.tree[r]

            l >>= 1
            r >>= 1
        return lcnt + rcnt


n = int(input())
s = list(input())
segs = [SegTree(n) for _ in range (27)]

for i,c in enumerate(s):
    c = ord(c) - ord('a')

    seg = segs[c]
    seg.update(i,1)

q = int(input())


for _ in range(q):
    t,l,r = [v for v in input().split()]

    if t == '2':
        ans = 0
        l,r = int(l),int(r)
        for i in range(ord('z')-ord('a')):
            if(segs[i].search_count(l-1,r) != 0):
                ans += 1
        print(ans)
    else:
        orig = s[int(l)-1]
        segs[ord(orig)-ord('a')].update(
                int(l)-1,
                -1
                )
        segs[ord(r)-ord('a')].update(
                int(l)-1,
                1
                )
        s[int(l)-1] = r

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

for i in range(q):
  w = list(input().replace(' ',''))
  if w[0] == '1':
    s[int(w[1])-1] = w[2]
  else :
    p = s[int(w[1])-1:int(w[2])]
    print(len(Counter(p)))

Submission status: Wrong Answer

Solution code:
n=int(input())+1
data=[0]*n*2
def update(i,x):
    i+=n
    data[i]=x
    i//=2
    while i:
        data[i]=data[i*2]|data[i*2+1]
        i//=2
def query(l,r):
    l+=n
    r+=n
    s=0
    while l<r:
        if l&1:
            s|=data[l]
            l+=1
        if r&1:
            r-=1
            s|=data[r]
        l//=2
        r//=2
    return sum(map(int,bin(s)[2:]))
s=input()
for i,c in enumerate(s[:-1],n):
    data[i]=1<<(ord(c)-97)
for i in range(n-1,0,-1):
    data[i]=data[2*i]|data[2*i+1]
for _ in range(int(input())):
    q,a,b=input().split()
    if q=="2":
        print(query(int(a)-1,int(b)))
    else:
        update(int(a)-1,1<<(ord(b)-97))

Submission status: Wrong Answer

Solution code:
import copy
import bisect

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

a = [[0 for i in range(26)]]
for i in range(n):
    a.append(copy.deepcopy(a[-1]))
    a[-1][ord(s[i])-97]+=1


b = []

for i in range(q):
    x,y,z = input().split()
    if x=='1':
        d = bisect.bisect_left(b,[int(y),z])
        if d<len(b) and b[d][0]==int(y):
            b[d]=[int(y),z]
        else:
            b.insert(d,[int(y),z])
    else:
        l = int(y)
        r = int(z)
        c = [0 for j in range(26)]
        for j in range(26):
            c[j]=a[r][j]-a[l-1][j]
        for j in range(len(b)):
            if l<=b[j][0]<=r:
                c[ord(b[j][1])-97]+=1
                c[ord(s[b[j][0]-1])-97]-=1
        print(26-c.count(0))

Submission status: Wrong Answer

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


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):
        posit[j].append(i)

    result = []
    for q in query:
        if q[0] == "1":
            p = int(q[1])-1
            c = ord(q[2])

            for i in range(ord("a"), ord("z")+1):
                if p in posit[i]:
                    posit[i].remove(p)
            posit[c].append(p)

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

            ret = 0
            for i in range(ord("a"), ord("z")+1):
                for v in posit[i]:
                    if r-1 >= v >= l-1:
                        ret += 1
                        break
            result.append(ret)


    #print(S)
    #print(posit)
    print(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: Wrong Answer

Solution code:
class SegTreeSum:
    '''
    0-indexedで実装していることに注意
    '''

    def __init__(self, V):
        self.sz = len(V)
        N = 1
        while N < self.sz:
            N *= 2

        self.N = N
        self.node = [0] * (2 * self.N - 1)
        
        for i in range(self.sz):
            self.node[i + self.N - 1] = V[i]
        
        for i in range(self.N - 2, 0, -1):
            # 親から子ノードへアクセスする
            self.node[i] = self.node[2*i+1] + self.node[2*i+2]
    
    def add(self,i,x):
        i += (self.N - 1)
        self.node[i] += x

        while i > 0:
            i = (i - 1) // 2
            self.node[i] = self.node[2*i+1] + self.node[2*i+2]

    def getsum(self,a,b,k=0,l=0,r=-1):
        if r < 0:
            r = self.N
        
        if b <= l or a >= r:
            return 0
        
        if a <= l and b >= r:
            return self.node[k]

        vl = self.getsum(a,b, 2*k+1, l, (l+r)//2)
        vr = self.getsum(a,b, 2*k+2, (l+r)//2, r)
        return vl + vr

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

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

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



    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class SegTreeSum:
    '''
    0-indexedで実装していることに注意
    '''

    def __init__(self, V):
        self.sz = len(V)
        N = 1
        while N < self.sz:
            N *= 2

        self.N = N
        self.node = [0] * (2 * self.N - 1)
        
        for i in range(self.sz):
            self.node[i + self.N - 1] = V[i]
        
        for i in range(self.N - 2, 0, -1):
            # 親から子ノードへアクセスする
            self.node[i] = self.node[2*i+1] + self.node[2*i+2]
    
    def add(self,i,x):
        i += (self.N - 1)
        self.node[i] += x

        while i > 0:
            i = (i - 1) // 2
            self.node[i] = self.node[2*i+1] + self.node[2*i+2]

    def getsum(self,a,b,k=0,l=0,r=-1):
        if r < 0:
            r = self.N
        
        if b <= l or a >= r:
            return 0
        
        if a <= l and b >= r:
            return self.node[k]

        vl = self.getsum(a,b, 2*k+1, l, (l+r)//2)
        vr = self.getsum(a,b, 2*k+2, (l+r)//2, r)
        return vl + vr

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

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

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



    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
q = int(input())
for _ in range(q):
    query = list(input().split())
    if query[0] == '1':
        i = int(query[1])
        s = s[:i] + query[2] + s[i+1:]
    elif query[0]:
        l,r = map(int,query[1:])
        print(len(set(s[l-1:r])))

Submission status: Wrong Answer

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

'''
111
abcdbbdtyyuhgjhguytuhgjhguyrtyetrdhggjutftfuyfyyabcdbbdtyyuhgjhguytuhgjhguyrtyetrdhggjutftfuyfyyabcdbbdtyyuhgjh
6
2 3 6
1 5 z
2 1 50000
1 4 a
1 7 d
2 1 1000000
'''

'''
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())

# s = s * 5000
# print()
# print(len(s))

# 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)
# print(d)


# @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 s[:q1] + q2 + s[q1+1:]
    # s[q1] = q2
    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:
            ans += 1
    '''
    st = time.time()
    temp1 = s[q1:q2 + 1]
    print(f'>>- extract: {time.time()-st}')

    st = time.time()
    temp2 = set(temp1)
    print(f'>>- to set: {time.time()-st}')
    ans = len(list(temp2))
    '''

    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: Wrong Answer

Solution code:
n = int(input())
s = input()
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])
    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: Wrong Answer

Solution code:
n = int(input())
s = input()
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):
    s = 0
    while i > 0:
        s += LIST[i]
        i -= i & (-i)
    return s

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])

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])
    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
        print(cur)

Submission status: Wrong Answer

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
ss = list(input())
q = int(input())
s = []
for i in range(len(ss)):
    a = ord(ss[i])-97
    s.append(a)
#print(s) #test
h = 0
nn = n
while nn:
    nn //= 2
    h += 1

seg = [[0 for _ in range(26)] for _ in range((2**(h+1))-1)]
for i in range(2**h-1, n-1+2**h):
    nl = [i] #所属するsegの番号リスト
    y = i
    for j in range(h):
        y = (y-1)//2
        nl.append(y) #nl完成
    for k in nl:
        seg[k][s[i-2**h+1]] += 1

for _ in range(q):
    bs, cs, ds = input().split()
    b = int(bs)
    c = int(cs)
    if b == 1:
        #print("クエリ1処理開始") #test
        f = ord(ds)-97
        x = c + 2**h - 2
        cl = [x]
        for j in range(h):
            x = (x-1)//2
            cl.append(x)
        #print(cl) #test
        #print(c) #test
        #print(s[c-1]) #test
        for k in cl:
            seg[k][s[c-1]] -= 1
            seg[k][f] += 1
        #print(seg) #test
    else:
        #print("クエリ2処理開始") #test
        d = int(ds)
        C = 2**h + c - 1
        D = 2**h + d
        LI = [] #敷居リスト
        t = C
        u = 1
        jud = False
        while True:
            if t * u == D:
                break
            elif t%2 != 0:
                if (t+1) * u <= D:
                    LI.append(t)
                    t += 1
                else:
                    t *= 2
                    u //= 2
            else:
                if (t+2) * u <= D:
                    t //= 2
                    u *= 2
                elif (t+1) * u <= D:
                    LI.append(t)
                    t += 1
                else:
                    t *= 2
                    u //= 2
        #print(LI)
        sumlist = [0 for _ in range(26)] #範囲内の個数
        for sh in LI:
            sh -= 1
            for j in range(26):
                sumlist[j] += seg[sh][j]
        #print(sumlist)
        ans = 0
        for numbers in sumlist:
            if numbers != 0:
                ans += 1
        print(ans)