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:
from bisect import bisect_left
from heapq import heapify, heappush

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

d = {}
flag = {}
for i in list('abcdefghijklmnopqrstuvwxyz'):
	d.setdefault(i, []).append(-1)
	flag.setdefault(i, []).append(-1)
for i in range(n):
	d[s[i]].append(i)
for i in list('abcdefghijklmnopqrstuvwxyz'):
	heapify(d[i])
	heapify(flag[i])

for i in range(q):
	q1,q2,q3 = map(str,input().split())
	if q1 == '1':
		q2 = int(q2) - 1
		if s[q2] != q3:
			heappush(flag[s[q2]],q2)
			heappush(d[q3],q2)
	else:
		ans = 0
		q2 = int(q2) - 1
		q3 = int(q3) - 1
		if q2 == q3:
			print(1)
			continue
		for string,l in d.items():
			res = 0
			if d[string] != [-1]:
				left = bisect_left(l,q2)
				right = bisect_left(l,q3+1)
			else:
				left = 0
				right = 0
			if flag[string] != [-1]:
				left2 = bisect_left(flag[string],q2)
				right2 = bisect_left(flag[string],q3)
			else:
				left2 = 0
				right2 = 0
			if left != right:
				if right - left > right2 - left2:
					res = 1
			ans += res
			#print(string,l,flag[string],res,[left,right,left2,right2])
		print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from heapq import heapify, heappush

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

d = {}
flag = {}
for i in list('abcdefghijklmnopqrstuvwxyz'):
	d.setdefault(i, []).append(-1)
	flag.setdefault(i, []).append(-1)
for i in range(n):
	d[s[i]].append(i)
for i in list('abcdefghijklmnopqrstuvwxyz'):
	heapify(d[i])
	heapify(flag[i])

for i in range(q):
	q1,q2,q3 = map(str,input().split())
	if q1 == '1':
		q2 = int(q2) - 1
		if s[q2] != q3:
			heappush(flag[s[q2]],q2)
			heappush(d[q3],q2)
	else:
		ans = 0
		q2 = int(q2) - 1
		q3 = int(q3) - 1
		if q2 == q3:
			print(1)
			continue
		for string,l in d.items():
			res = 0
			if d[string] != [-1]:
				left = bisect_left(l,q2)
				right = bisect_left(l,q3+1)
			else:
				left = 0
				right = 0
			if flag[string] != [-1]:
				left2 = bisect_left(flag[string],q2)
				right2 = bisect_left(flag[string],q3+1)
			else:
				left2 = 0
				right2 = 0
			if left != right:
				if right - left > right2 - left2:
					res = 1
			ans += res
			#print(string,l,flag[string],res,[left,right,left2,right2])
		print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

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

d = {}
for i in range(n):
	d.setdefault(s[i], []).append(i)

flag = {}
for i in range(q):
	q1,q2,q3 = map(str,input().split())
	if q1 == '1':
		q2 = int(q2) - 1
		if s[q2] != q3:
			flag.setdefault(s[q2], []).append(q2)
			d.setdefault(q3, []).append(q2)
	else:
		ans = 0
		res = 0
		q2 = int(q2) - 1
		q3 = int(q3) - 1
		if q2 == q3:
			print(1)
			continue
		for string,l in d.items():
			left = bisect_left(l,q2)
			right = bisect_left(l,q3)
			if string in flag:
				left2 = bisect_left(flag[string],q2)
				right2 = bisect_left(flag[string],q3)
			else:
				left2 = 0
				right2 = 0
			if left != right:
				if right - left > right2 - left2:
					res = 1
			ans += res
			#print(string,l,res)
		print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

# binary_search(l, n) = l.index(lに含まれるn以下の最大の数)
# lはsort済で、要素の重複なし
def binary_search(l, n):
    start = 0
    stop = len(l) - 1
    while start < stop:
        center = (start + stop + 1) // 2
        if l[center] <= n:
            start = center
        else:
            stop = center - 1
    return start

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

# alphabet毎に整理
alp = [[] for _ in range(26)]
for i in range(n):
    alp[order(s[i])].append(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        del alp[order(s[b])][binary_search(alp[order(s[b])], b)]
        if alp[order(c)] == []:
            alp[order(c)].append(b)
        elif alp[order(c)][0] < b:
            alp[order(c)].insert(0, b)
        else:
            alp[order(c)].insert(binary_search(alp[order(c)], b) + 1, b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i == []:
                continue
            elif i[0] > c:
                continue
            elif i[binary_search(i, c)] >= b:
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

# binary_search(l, n) = l.index(lに含まれるn以下の最大の数)
# lはsort済で、要素の重複なし
def binary_search(l, n):
    start = 0
    stop = len(l) - 1
    while start < stop:
        center = (start + stop + 1) // 2
        if l[center] <= n:
            start = center
        else:
            stop = center - 1
    return start

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

# alphabet毎に整理
alp = [[] for _ in range(26)]
for i in range(n):
    alp[order(s[i])].append(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        # alp[order(s[b])].remove(b)を二分探索で行う
        del alp[order(s[b])][binary_search(alp[order(s[b])], b)]
        alp[order(c)].insert(binary_search(alp[order(c)], b) + 1, b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i == []:
                continue
            elif i[0] > c:
                continue
            elif i[binary_search(i, c)] >= b:
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():

    n = int(input())
    s = list(input().strip())
    q = int(input())
    alpha = g = [[] for _ in range(26)]
    for i in range(n):
        alpha[ord(s[i])-ord('a')].append(i)
    for i in range(q):
        a, b, c = map(str, input().split())
        if a == '1':
            b = int(b)-1
            alpha[ord(s[b])-ord('a')].remove(b)
            s[b] = c
            alpha[ord(c)-ord('a')].append(b)
        else:
            ans = 0
            for i in range(26):
                if len(alpha[i]) > 0:
                    it = bisect.bisect_left(alpha[i], int(b)-1)
                    if it < len(alpha[i]) and alpha[i][it] < int(c):
                        ans += 1
            print(ans)


main()

Submission status: Wrong Answer

Solution code:
# import numpy as np

class segtree:

    def __init__(self, n,operator,identity):
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_leaves = 2**(len(nb)-1)
        else:
            self.num_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_leaves * 2)]
        self.identity = identity
        self.operator =operator
        self.n = n

    def build(self,init_arr):
        for i in range(self.n):
            self.array[i+self.num_leaves] = init_arr[i]
        for i in range(self.num_leaves):
            pt = self.num_leaves-1-i
            self.array[pt] = self.operator(self.array[pt*2],self.array[pt*2+1])


    def update(self,x,val):
        actual_x = x+self.num_leaves
        self.array[actual_x] = self.operator(self.array[actual_x],val)
        while actual_x > 0 :
            actual_x = actual_x//2
            self.array[actual_x] = self.operator(self.array[actual_x],val)

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        width_of_floor = self.num_leaves//(2**depth)
        leaf_right = leaf_left+width_of_floor-1

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
            return self.operator(val_l,val_r)




def addf(a, b):
    return a+b


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

trees = [segtree(n, addf, 0) for i in range(26)]
buf = [[0 for i in range(n)] for j in range(26)]


for i in range(n):
    c = ord(s[i]) - 97
    buf[c][i] = 1


for i in range(26):
    trees[i].build(buf[i])




s = list(s)

for i in range(q):
    ty, i, c = input().split()

    if ty == "1":
        i = int(i)
        c = ord(c) - 97
        base = ord(s[i-1])-97
        trees[c].update(i-1,1)
        trees[base].update(i-1,0)
    else:
        i = int(i)
        c = int(c)
        i -= 1
        c -= 1
        tp = 0
        for j in range(26):
            # print(trees[j].get(i,c),end=" ")
            if trees[j].get(i,c) > 0:
                tp += 1
        print(tp)

Submission status: Wrong Answer

Solution code:
import numpy as np

class segtree:

    def __init__(self, n,operator,identity):
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_leaves = 2**(len(nb)-1)
        else:
            self.num_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_leaves * 2)]
        self.identity = identity
        self.operator =operator
        self.n = n

    def build(self,init_arr):
        for i in range(self.n):
            self.array[i+self.num_leaves] = init_arr[i]
        for i in range(self.num_leaves):
            pt = self.num_leaves-1-i
            self.array[pt] = self.operator(self.array[pt*2],self.array[pt*2+1])


    def update(self,x,val):
        actual_x = x+self.num_leaves
        self.array[actual_x] = self.operator(self.array[actual_x],val)
        while actual_x > 0 :
            actual_x = actual_x//2
            self.array[actual_x] = self.operator(self.array[actual_x],val)

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        width_of_floor = self.num_leaves//(2**depth)
        leaf_right = leaf_left+width_of_floor-1

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
            return self.operator(val_l,val_r)




def addf(a, b):
    return a+b


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

trees = [segtree(n, addf, 0) for i in range(26)]
buf = [[0 for i in range(n)] for j in range(26)]


for i in range(n):
    c = ord(s[i]) - 97
    buf[c][i] = 1

# for i,t in enumerate(trees):
    # print(len(t.array))
    # print(t.num_leaves)
    # print(t.n)
    # print(len(buf[i]))

for i in range(26):
    trees[i].build(buf[i])




s = list(s)

for i in range(q):
    ty, i, c = input().split()

    if ty == "1":
        i = int(i)
        c = ord(c) - 97
        base = ord(s[i-1])-97
        trees[c].update(i-1,1)
        trees[base].update(i-1,0)
    else:
        i = int(i)
        c = int(c)
        i -= 1
        c -= 1
        tp = 0
        for j in range(26):
            # print(trees[j].get(i,c),end=" ")
            if trees[j].get(i,c) > 0:
                tp += 1
        print(tp)

Submission status: Wrong Answer

Solution code:
import numpy as np

class segtree:

    def __init__(self, n,operator,identity):
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_leaves = 2**(len(nb)-1)
        else:
            self.num_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_leaves * 2)]
        self.identity = identity
        self.operator =operator
        self.n = n

    def build(self,init_arr):
        for i in range(self.n):
            self.array[i+self.num_leaves] = init_arr[i]
        for i in range(self.num_leaves):
            pt = self.num_leaves-1-i
            self.array[pt] = self.operator(self.array[pt*2],self.array[pt*2+1])


    def update(self,x,val):
        actual_x = x+self.num_leaves
        self.array[actual_x] = self.operator(self.array[actual_x],val)
        while actual_x > 0 :
            actual_x = actual_x//2
            self.array[actual_x] = self.operator(self.array[actual_x],val)

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        width_of_floor = self.num_leaves//(2**depth)
        leaf_right = leaf_left+width_of_floor-1

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
            return self.operator(val_l,val_r)


identity = np.array([False for i in range(26)])


def num_kinds(a, b):
    return np.logical_or(a, b)


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

tree = segtree(n, num_kinds, identity)

buf = []
for i in range(n):
    temp = np.array([False for i in range(26)])
    temp[ord(s[i]) - 97] = True
    buf.append(temp)

tree.build(buf)

for i in range(q):
    ty, i, c = input().split()

    if ty == "1":
        i = int(i)
        temp = np.array([False for i in range(26)])
        temp[ord(c) - 97] = True
        tree.update(i - 1, temp)
    else:
        i = int(i)
        c = int(c)
        i -= 1
        c -= 1
        print(sum(tree.get(i, c)))

Submission status: Wrong Answer

Solution code:
import sys
from copy import copy, deepcopy
input = sys.stdin.readline
'''
n, m = map(int, input().split())
n = int(input())
A = list(map(int, input().split()))
S = input().strip()
for CASES in range(int(input())):
'''
inf = 100000000000000000  # 1e17
mod = 998244353

'''
# example input


'''


def replace(pos, char):
    x = pos
    old_char = A[x]
    while x <= n:
        tr[x][old_char] = 0
        x += x & (-x)
    x = pos
    while x <= n:
        tr[x][char] = 1
        x += x & (-x)
    A[pos] = char


def query(pos, char):
    x = pos
    sum = 0
    while x != 0:
        sum += tr[x][char]
        x -= x & (-x)
    return sum


n = int(input())
S = input().strip()
A = [27] * (n + 1)
'''
for i in range(len(S)):
    A.append(ord(S[i])-ord('a'))
'''
tr = [[0] * 30 for i in range(len(S) + 10)]
for i in range(len(S)):
    replace(i + 1, ord(S[i]) - ord('a'))
q = int(input())
for i in range(q):
    QUERY = list((input().split()))
    if int(QUERY[0]) == 1:
        replace(int(QUERY[1]), ord(QUERY[2]) - ord('a'))
    else:
        sum = 0
        for char in range(ord('a'), ord('z') + 1):
            sum += query(int(QUERY[2]), char - ord('a'))
            sum -= query(int(QUERY[1]) - 1, char - ord('a'))
        print(sum)

Submission status: Wrong Answer

Solution code:
import numpy as np
N=int(input())
S=input()
Q=int(input())
D={}
alp=['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', '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,s in enumerate(alp):
    D[s]=i
M=np.zeros((26,N+1))
for i in range(1,N+1):
    M[:,i]=M[:,i-1]
    M[D[S[i-1]],i]+=1
#print(M)
for i in range(Q):
    n,x,y=input().split()
    x=int(x)
    if n=="1":
        #Sのi文字目
        f=D[S[x-1]]
        af=D[y]
        #print(n,x,y,f,af)
        M[f,x:]-=1
        M[af,x:]+=1
    else:
        y=int(y)
        #print(M[:,y]-M[:,x-1])
        print( np.count_nonzero(M[:,y]-M[:,x-1]) )

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from operator import or_


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


n = int(readline())
s = readline().rstrip().decode()
q = int(readline())
li = [1 << ord(x) - 97 for x in s[:-1]]
seg = SegmentTree(li, or_, 0)
ans = []
for _ in range(q):
    f, x, y = readline().rstrip().decode().split()
    x = int(x)
    if f == '1':
        seg.update(x - 1, 1 << ord(y) - 97)
    else:
        y = int(y)
        z = seg.find(x - 1, y)
        cnt = bin(z).count('1')
        ans.append(cnt)
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from operator import or_


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


n = int(readline())
s = readline().rstrip().decode()
q = int(readline())
li = [1 << ord(x) - 97 for x in s[:-1]]
seg = SegmentTree(li, or_, 0)
ans = []
for _ in range(q):
    f, x, y = readline().rstrip().decode().split()
    x = int(x)
    if f == '1':
        seg.update(x - 1, 1 << ord(y) - 97)
    else:
        y = int(y)
        z = seg.find(x - 1, y)
        cnt = 0
        for i in range(26):
            if z & (1 << i):
                cnt += 1
        ans.append(cnt)
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from operator import or_


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


n = int(readline())
s = readline().rstrip().decode()
q = int(readline())
li = [1 << ord(x) - 97 for x in s[:-1]]
seg = SegmentTree(li, or_, 0)
for _ in range(q):
    f, x, y = readline().rstrip().decode().split()
    x = int(x)
    if f == '1':
        seg.update(x - 1, 1 << ord(y) - 97)
    else:
        y = int(y)
        z = seg.find(x - 1, y)
        cnt = 0
        for i in range(26):
            if z & (1 << i):
                cnt += 1
        print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from operator import or_


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


n = int(readline())
s = readline().rstrip().decode()
q = int(readline())
li = [1 << ord(x) - 97 for x in s[:-1]]
seg = SegmentTree(li, or_, 0)
for i in range(q):
    f, x, y = readline().rstrip().decode().split()
    x = int(x)
    if f == '1':
        seg.update(x - 1, 1 << ord(y) - 97)
    else:
        y = int(y)
        z = seg.find(x - 1, y)
        cnt = 0
        for i in range(26):
            if z & (1 << i):
                cnt += 1
        print(cnt)

Submission status: Wrong Answer

Solution code:
class SegmentTree():
    """一点更新、区間取得クエリをそれぞれO(logN)で答えるデータ構造を構築する。
    built(array)   := arrayを初期値とするセグメント木を構築する O(N)。
    update(i, val) := i番目の要素をvalに変更する。
    get_val(l, r)  := 区間[l, r)に対する二項演算の畳み込みの結果を返す。
    """
    def __init__(self, n, op, e):
        """要素数、二項演算、単位元を引数として渡す
        例) 区間最小値 SegmentTree(n, min, 10 ** 18)
            区間和     SegmentTree(n, lambda a, b : a + b, 0)
        """
        self.n = n
        self.op = op
        self.e = e
        self.size = 2 ** ((n - 1).bit_length())
        self.node = [self.e] * (2 * self.size)

    def build(self, array):
        """arrayを初期値とするセグメント木を構築する"""
        for i in range(self.n):
            self.node[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

    def update(self, i, val):
        """i番目の要素をvalに変更する"""
        i += self.size
        self.node[i] = val
        while i > 1:
            i >>= 1
            self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

    def get_val(self, l, r):
        """[l, r)の畳み込みの結果を返す"""
        l, r = l + self.size, r + self.size
        res_l, res_r = self.e, self.e
        while l < r:
            if l & 1:
                res_l = self.op(res_l, self.node[l])
                l += 1
            if r & 1:
                r -= 1
                res_r = self.op(self.node[r], res_r)
            l, r = l >> 1, r >> 1
        return self.op(res_l, res_r)


ALPH = "abcdefghijklmnopqrstuvwxyz"
to_int = {char: i for i, char in enumerate(ALPH)}


n = int(input())
s = input()
q = int(input())
query = [list(input().split()) for i in range(q)]

init = [0] * n
for i, char in enumerate(s):
    init[i] = 1 << to_int[char]

op = lambda a, b: a | b
st = SegmentTree(n, op, 0)
st.build(init)

for i in range(q):
    if query[i][0] == "1":
        _, ind, char = query[i]
        ind = int(ind)
        st.update(ind, 1 << to_int[char])
    else:
        _, l, r = query[i]
        l, r = int(l) - 1, int(r) 
        print(bin(st.get_val(l, r)).count("1"))

Submission status: Wrong Answer

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

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[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


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

li = []
for i in range(n):
    li.append(1 << ord(s[i]) - ord('a'))

#####単位元######
ide_ele = 0

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

for _ in range(q):
    q1 = list(input().split())
    if q1[0] == '1':
        update(int(q1[1]), 1 << ord(q1[2]) - ord('a'))
    else:
        l,r = int(q1[1]), int(q1[2])
        print(bin(query(l-1,r)).count('1'))

Submission status: Wrong Answer

Solution code:
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[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

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

li = []
for i in range(n):
    li.append({s[i]})

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

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

for _ in range(q):
    q1 = list(input().split())
    if q1[0] == '1':
        update(int(q1[1]), {q1[2]})
    else:
        l,r = int(q1[1]), int(q1[2])
        print(len(query(l-1,r)))

Submission status: Wrong Answer

Solution code:
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[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

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

li = []
for i in range(n):
    li.append({s[i]})

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

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

print(seg)

for _ in range(q):
    q1 = list(input().split())
    if q1[0] == '1':
        update(int(q1[1]), {q1[2]})
    else:
        l,r = int(q1[1]), int(q1[2])
        print(len(query(l-1,r)))

Submission status: Wrong Answer

Solution code:
def segfunc(x,y):
    li = [False] * 26
    for i in range(26):
        if x[i] or y[i]:
            li[i] = True
    return li

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[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

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

li = []
for i in range(n):
    li2 = [False] * 26
    li2[ord(s[i]) - 97] = True
    li.append(li2)

#####単位元######
ide_ele = [False] * 26

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

for _ in range(q):
    q1 = list(input().split())
    if q1[0] == '1':
        l = [False] * 26
        l[ord(q1[2]) - 97] = True
        update(int(q1[1]), l)
    else:
        l,r = int(q1[1]), int(q1[2])
        print(query(l-1,r).count(True))