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 functools import reduce
import sys
input = sys.stdin.readline


class SegmentTrees:
    def __init__(self, target, no_effect):
        size = len(target)
        length = 1
        while length < size:
            length *= 2
        self.tree_size = length * 2 - 1
        self.tree = [no_effect] * self.tree_size
        self.areas = [[0, 0] for _ in range(self.tree_size)]
        self.set_areas()
        self.initialize_tree_by_target(target, no_effect)
        self.target = target

    def set_areas(self):
        def decide_children_areas(node):
            left, right = self.areas[node]
            center = (left+right)//2
            child1 = node * 2 + 1
            child2 = node * 2 + 2
            self.areas[child1] = [left, center]
            self.areas[child2] = [center+1, right]

        self.areas[0] = [0, self.tree_size//2]
        for parent in range(self.tree_size//2):
            decide_children_areas(parent)

    @classmethod
    def initialize_func(cls, value):
        return 1 << (ord(value) - ord('a'))

    @classmethod
    def merge_func(cls, a, b):
        return a | b

    def merge_child_data(self, node):
        child1 = node * 2 + 1
        child2 = node * 2 + 2
        merged = self.merge_func(self.tree[child1], self.tree[child2])
        return merged

    def initialize_tree_by_target(self, target: list, no_effect=0):
        def calc_leafs():
            initial_leaf = self.tree_size//2
            leafs = range(initial_leaf, initial_leaf+len(target))
            for value, leaf in zip(target, leafs):
                self.tree[leaf] = self.initialize_func(value)

            residue = range(initial_leaf+len(target), self.tree_size)
            for residual_leaf in residue:
                self.tree[residual_leaf] = no_effect

        calc_leafs()
        for parent in range(self.tree_size//2-1, -1, -1):
            self.tree[parent] = self.merge_child_data(parent)

    def update(self, new_data, position):
        leaf = self.tree_size//2 + position
        new = self.initialize_func(new_data)
        if self.tree[leaf] == new:
            return
        self.tree[leaf] = new
        parent = (leaf-1) // 2
        while parent >= 0:
            new = self.merge_child_data(parent)
            if self.tree[parent] == new:
                break
            self.tree[parent] = new
            parent = (parent-1) // 2

    def get_query(self, _from, to):
        def get_tree_data(node):
            left, right = self.areas[node]
            if _from <= left and right <= to:
                result.append(self.tree[node])
                return
            if to < left or right < _from:
                return

            child1 = node * 2 + 1
            child2 = node * 2 + 2
            get_tree_data(child1)
            get_tree_data(child2)

        result = []
        get_tree_data(0)
        ans = reduce(self.merge_func, result)
        ans = bin(ans).count('1')
        return ans


n = int(input())
S = input().replace('\n', '')
seg_tree = SegmentTrees(target=S, no_effect=0)

Q = int(input())
for _ in range(Q):
    query = input().split()
    if query[0] == '1':
        position, new = int(query[1]), query[2]
        seg_tree.update(new, position)

    elif query[0] == '2':
        _from, to = int(query[1])-1, int(query[2])-1
        print(seg_tree.get_query(_from, to))

Submission status: Wrong Answer

Solution code:
from functools import reduce
import sys
input = sys.stdin.readline


class SegmentTrees:
    def __init__(self, target, no_effect):
        size = len(target)
        length = 1
        while length < size:
            length *= 2
        self.tree_size = length * 2 - 1
        self.tree = [no_effect] * self.tree_size
        self.areas = [[0, 0] for _ in range(self.tree_size)]
        self.set_areas()
        self.initialize_tree_by_target(target, no_effect)

    def set_areas(self):
        def decide_children_areas(node):
            left, right = self.areas[node]
            center = (left+right)//2
            child1 = node * 2 + 1
            child2 = node * 2 + 2
            self.areas[child1] = [left, center]
            self.areas[child2] = [center+1, right]

        self.areas[0] = [0, self.tree_size//2 - 1]
        for parent in range(self.tree_size//2):
            decide_children_areas(parent)

    @classmethod
    def initialize_func(cls, value):
        return 1 << (ord(value) - ord('a'))

    @classmethod
    def merge_func(cls, a, b):
        return a | b

    def merge_child_data(self, node):
        child1 = node * 2 + 1
        child2 = node * 2 + 2
        merged = self.merge_func(self.tree[child1], self.tree[child2])
        return merged

    def initialize_tree_by_target(self, target: list, no_effect=0):
        def calc_leafs():
            initial_leaf = self.tree_size//2
            leafs = range(initial_leaf, initial_leaf+len(target))
            for value, leaf in zip(target, leafs):
                self.tree[leaf] = self.initialize_func(value)

            residue = range(initial_leaf+len(target), self.tree_size)
            for residual_leaf in residue:
                self.tree[residual_leaf] = no_effect

        calc_leafs()
        for parent in range(self.tree_size//2-1, -1, -1):
            self.tree[parent] = self.merge_child_data(parent)

    def update(self, new_data, position):
        leaf = self.tree_size//2 + position
        new = self.initialize_func(new_data)
        if self.tree[leaf] == new:
            return
        self.tree[leaf] = new
        parent = (leaf-1) // 2
        while parent >= 0:
            new = self.merge_child_data(parent)
            if self.tree[parent] == new:
                break
            self.tree[parent] = new
            parent = (parent-1) // 2

    def get_query(self, _from, to):
        def get_tree_data(node):
            left, right = self.areas[node]
            if _from <= left and right <= to:
                result.append(self.tree[node])
                return
            if to < left or right < _from:
                return

            child1 = node * 2 + 1
            child2 = node * 2 + 2
            get_tree_data(child1)
            get_tree_data(child2)

        result = []
        get_tree_data(0)
        ans = reduce(self.merge_func, result)
        ans = bin(ans).count('1')
        return ans


n = int(input())
S = input().replace('\n', '')
seg_tree = SegmentTrees(target=S, no_effect=0)

Q = int(input())
for _ in range(Q):
    query = input().split()
    if query[0] == '1':
        position, new = int(query[1]), query[2]
        seg_tree.update(new, position)

    elif query[0] == '2':
        _from, to = int(query[1])-1, int(query[2])-1
        print(seg_tree.get_query(_from, to))

Submission status: Wrong Answer

Solution code:
from functools import reduce
import sys
input = sys.stdin.readline


class SegmentTrees:
    def __init__(self, target, no_effect):
        size = len(target)
        length = 1
        while length < size:
            length *= 2
        self.tree_size = length * 2 - 1
        self.tree = [no_effect] * self.tree_size
        self.areas = [[0, 0] for _ in range(self.tree_size)]
        self.set_areas()
        self.initialize_tree_by_target(target, no_effect)

    def set_areas(self):
        def decide_children_areas(node):
            left, right = self.areas[node]
            center = (left+right)//2
            child1 = node * 2 + 1
            child2 = node * 2 + 2
            self.areas[child1] = [left, center]
            self.areas[child2] = [center+1, right]

        self.areas[0] = [0, self.tree_size//2 - 1]
        for parent in range(self.tree_size//2):
            decide_children_areas(parent)

    @classmethod
    def initialize_func(cls, value):
        return 1 << (ord(value) - ord('a'))

    @classmethod
    def merge_func(cls, a, b):
        return a | b

    def merge_child_data(self, node):
        child1 = node * 2 + 1
        child2 = node * 2 + 2
        merged = self.merge_func(self.tree[child1], self.tree[child2])
        return merged

    def initialize_tree_by_target(self, target: list, no_effect):
        def calc_leafs():
            initial_leaf = self.tree_size//2
            leafs = range(initial_leaf, initial_leaf+len(target))
            for value, leaf in zip(target, leafs):
                self.tree[leaf] = self.initialize_func(value)

            residue = range(initial_leaf+len(target), self.tree_size)
            for residual_leaf in residue:
                self.tree[residual_leaf] = no_effect

        calc_leafs()
        for parent in range(self.tree_size//2-1, -1, -1):
            self.tree[parent] = self.merge_child_data(parent)

    def update(self, new_data, position):
        leaf = self.tree_size//2 + position
        new = self.initialize_func(new_data)
        if self.tree[leaf] == new:
            return
        self.tree[leaf] = new
        parent = (leaf-1) // 2
        while parent >= 0:
            new = self.merge_child_data(parent)
            if self.tree[parent] == new:
                break
            self.tree[parent] = new
            parent = (parent-1) // 2

    def get_query(self, _from, to):
        def get_tree_data(node):
            left, right = self.areas[node]
            if _from <= left and right <= to:
                result.append(self.tree[node])
                return
            if to < left or right < _from:
                return

            child1 = node * 2 + 1
            child2 = node * 2 + 2
            get_tree_data(child1)
            get_tree_data(child2)

        result = []
        get_tree_data(0)
        ans = reduce(self.merge_func, result)
        ans = bin(ans).count('1')
        return ans


n = int(input())
S = input().replace('\n', '')
seg_tree = SegmentTrees(target=S, no_effect=0)

Q = int(input())
for _ in range(Q):
    query = input().split()
    if query[0] == '1':
        position, new = int(query[1]), query[2]
        seg_tree.update(new, position)

    elif query[0] == '2':
        _from, to = int(query[1])-1, int(query[2])-1
        print(seg_tree.get_query(_from, to))

Submission status: Wrong Answer

Solution code:
class SegmentTree():
    def __init__(self,init_val,n,func): #init_valは長さnの配列 O(2*n)
        self.unit=0
        self.size=pow(2,n-1).bit_length() #n以上の最小の2のべき乗
        self.seg=[self.unit]*2*self.size #セグメントツリー本体
        self.f=func #セグ木により異なる関数
        
        for i in range(n):
            self.seg[i+self.size-1]=init_val[i] 
        
        for i in range(self.size-2,-1,-1):
            self.seg[i]=self.f(self.seg[2*i+1],self.seg[2*i+2])
    
    def update(self,k,x): #k番目の要素をxに変更する
        k+=self.size-1
        self.seg[k]=x
        while k:
            k=(k-1)//2
            self.seg[k]=self.f(self.seg[2*k+1],self.seg[2*k+2])
    
    def query(self,p,q): #[p,q)のクエリに答える　半開区間であることに注意
        if q<=p:
            return self.unit

        p+=self.size-1
        q+=self.size-2
        res=self.unit

        while q-p>1:

            if (p&1)==0:
                res=self.f(res,self.seg[p])

            if (q&1)==1:
                res=self.f(self.f(res,self.seg[p]),self.seg[q])
                q-=1
            p//=2
            q=(q-1)//2
        
        if p==q:
            res=self.f(res,self.seg[p])
        else:
            res=self.f(res,self.seg[q])
        
        return bin(res).count('1')

def main():
    n=int(input())
    s=input()

    dic={i:j for i,j in zip('abcdefghijklmnopqrstuvwxyz',[2**i for i in range(26)])}
    l=[0]*n

    for i in range(n):
        l[i]=dic[s[i]]
    
    def f(x,y):
        return x|y

    st=SegmentTree(l,n,f)
    
    q=int(input())
    for _ in range(q):
        a=list(map(str,input().split()))
        a[0]=int(a[0])

        if a[0]==1:
            a[1]=int(a[1])
            st.update(a[1]-1,dic[a[2]])
        
        else:
            a[1]=int(a[1])-1
            a[2]=int(a[2])
            print(st.query(a[1],a[2]))
            
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class SegTree:
    def __init__(self,aa):
        n=1<<(len(aa)-1).bit_length()
        tree=[0]*(2*n-1)
        tree[n-1:n-1+len(aa)]=aa
        for i in range(n-2,-1,-1):tree[i]=tree[2*i+1]|tree[2*i+2]
        self.tree=tree
        self.n=n

    def update(self,i,a):
        i=self.n-1+i
        self.tree[i]=a
        while i:
            i=(i-1)//2
            self.tree[i]=self.tree[2*i+1]|self.tree[2*i+2]

    def SegOr(self,l,r,i=0,segl=0,segr=-1):
        if segr==-1:segr=self.n
        if r<=segl or segr<=l:return 0
        if l<=segl and segr<=r:return self.tree[i]
        m=(segl+segr)//2
        return self.SegOr(l,r,2*i+1,segl,m)|self.SegOr(l,r,2*i+2,m,segr)

def main():
    code=lambda c:ord(c)-ord("a")
    popcnt=lambda x:bin(x).count("1")
    n=II()
    s=SI()
    aa=[1<<code(c) for c in s]
    st=SegTree(aa)
    q=II()
    for _ in range(q):
        op,x,y=SI().split()
        if op=="1":
            i=int(x)-1
            st.update(i,code(y))
        else:
            l,r=int(x)-1,int(y)
            print(popcnt(st.SegOr(l,r)))

main()

Submission status: Wrong Answer

Solution code:
N=int(input())
S=list(input())
Q=int(input())
#print(S) 012345
do=[input().split() for i in range(Q)]
answer=[]
check=[]
#print(do)
for i in range(Q):
    if int(do[i][0])==1:
        S[int(do[i][1])-1]=do[i][2]
        #print(S)###　       
    else:
        for j in range(int(do[i][1])-1,int(do[i][2])):
            check.append(S[j])
        check.sort()
       # print(check)####
        while True:
            q=0
            for k in range(len(check)-2):
                if check[k]==check[k+1]:
                    trash=check.pop(k)
                    #print(check)###
                    q=1
                    break
            if q==0:
                break
        #print(check)#####        
        answer.append(len(check))
        check=[]
#print(answer)#####        
kotae=""     
for h in range(len(answer)):
    print(answer[h])

Submission status: Wrong Answer

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())
Query=[input().split() for i in range(Q)]


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,b):
    k += num-1
    if seg[k] and seg[k].pop()==b:
        return()
    seg[k].add(b)
    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

ide_ele =set()

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

for i in range(N):
    update(i,S[i])

for type,i,c in Query:

    if type=="1":
        update(int(i)-1,c)
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)

Submission status: Wrong Answer

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math

a=set([1])
b=set([1])
print(a==b)
#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())
Query=[input().split() for i in range(Q)]


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,b):
    k += num-1
    if seg[k]==set([b]):
        return ()
    seg[k] = set([b])
    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

ide_ele =set()

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

for i in range(N):
    update(i,S[i])

for type,i,c in Query:

    if type=="1":
        update(int(i)-1,c)
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(input())
q = int(input())
ds = [[0]*26]
dq = dict()

for i in range(n):
    d = ds[i].copy()
    d[ord(s[i]) - ord('a')] += 1
    ds += [d]


def list_sub(l1, l2):
    ret = []
    for i in range(min(len(l1), len(l2))):
        ret += [l1[i] - l2[i]]
    return ret


def list_add(l1, l2):
    ret = []
    for i in range(min(len(l1), len(l2))):
        ret += [l1[i] + l2[i]]
    return ret


def list_len(l):
    ret = 0
    for x in l:
        if x > 0:
            ret += 1
    return ret

ans = []
for i in range(q):
    a,b,c = input().split()

    if a == '1':
        b = int(b) - 1
        if b not in dq:
            dq[b] = [0] * 26
        er = s[b]
        dq[b][ord(c) - ord('a')] += 1
        dq[b][ord(er) - ord('a')] -= 1
        s[b] = c

    if a == '2':
        b = int(b) - 1
        c = int(c) - 1
        d = list_sub(ds[c+1], ds[b])

        l = sorted(list(dq.items()))
        for k,v in l:
            if c < k:
                break
            if k < b:
                d = list_sub(d, v)
            else:
                d = list_add(d, v)
        ans += [list_len(d)]
for x in ans:
    print(x)

Submission status: Wrong Answer

Solution code:
import numpy as np
n=int(input())
s=input()
t=np.zeros((26,n+1))
for i in range(n):
    t[ord(s[i])-97][i+1]+=1
t=np.cumsum(t,axis=1)
for i in range(int(input())):
    a,b,c=map(str,input().split())
    if a=="1":
        if s[int(b)-1]!=c:
            t[ord(s[int(b)-1])-97][int(b):]-=1
            t[ord(c)-97][int(b):]+=1
    else:
        d=0
        b,c=int(b),int(c)
        for j in range(26):
            if t[j][c]>t[j][b-1]:
                d+=1
        print(d)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
q = int(input())
import sys
input = sys.stdin.readline
Q = [list(input().split()) for i in range(q)]

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

import string
DD = [chr(i) for i in range(ord("a"), ord("z")+1)]
D = {}
for i in range(len(DD)):
    D[DD[i]] = i
S = []
for i in range(n):
    S.append(D[s[i]])
B = [Bit(n) for i in range(26)]
for i in range(26):
    for j in range(n):
        if S[j] == i:
            B[i].add(j+1, 1)  # 合計n回

for i in range(q):
    qu = int(Q[i][0])
    if qu == 2:
        l = int(Q[i][1])
        r = int(Q[i][2])
        ans = 0
        for j in range(26):
            p = min(1, B[j].sum(r) - B[j].sum(l-1))
            # print(j,p)
            ans += p
        print(ans)
    elif qu == 1:
        iq = int(Q[i][1])-1
        c = D[Q[i][2]]
        pc = S[iq]
        B[pc].add(iq+1, -1)
        B[c].add(iq+1, 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
q = int(input())
import sys
input = sys.stdin.readline
Q = [list(input().split()) for i in range(q)]

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

import string
DD = [chr(i) for i in range(ord("a"), ord("z")+1)]
D = {}
for i in range(len(DD)):
    D[DD[i]] = i
S = []
for i in range(len(s)):
    S.append(D[s[i]])
B = [Bit(n) for i in range(26)]
for i in range(26):
    for j in range(n):
        if S[j] == i:
            B[i].add(j+1, 1)

for i in range(q):
    qu = int(Q[i][0])
    if qu == 2:
        l = int(Q[i][1])
        r = int(Q[i][2])
        ans = 0
        for j in range(26):
            p = min(1, B[j].sum(r) - B[j].sum(l-1))
            # print(j,p)
            ans += p
        print(ans)
    elif qu == 1:
        iq = int(Q[i][1])-1
        c = D[Q[i][2]]
        pc = S[iq]
        B[pc].add(iq+1, -1)
        B[c].add(iq+1, 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
q = int(input())
import sys
input = sys.stdin.readline
Q = [list(input().split()) for i in range(q)]

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

import string
DD = [chr(i) for i in range(ord("a"), ord("z")+1)]
D = {}
for i in range(len(DD)):
    D[DD[i]] = i
S = []
for i in range(len(s)):
    S.append(D[s[i]])
B = [Bit(n) for i in range(26)]
for i in range(26):
    T = [0] * n
    for j in range(n):
        if D[s[j]] == i:
            T[j] = 1
    # for j in range(1, n):
    #     T[j] += T[j-1]
    for j in range(n):
        B[i].add(j+1, T[j])

for i in range(q):
    qu = int(Q[i][0])
    if qu == 2:
        l = int(Q[i][1])
        r = int(Q[i][2])
        ans = 0
        for j in range(26):
            p = min(1, B[j].sum(r) - B[j].sum(l-1))
            # print(j,p)
            ans += p
        print(ans)
    elif qu == 1:
        iq = int(Q[i][1])-1
        c = D[Q[i][2]]
        pc = S[iq]
        B[pc].add(iq+1, -1)
        B[c].add(iq+1, 1)

Submission status: Wrong Answer

Solution code:
import bisect
N=int(input())
S=list(input())
Q=int(input())
D="abcdefghijklmnopqrstuvwxyz"
def lower_bound(K,s):
  l=0
  r=len(K)-1
  while l<=r:
    mid = (l+r)//2
    if K[mid]==s:
      return True
    elif K[mid]<s:
      l=mid+1
    else:
      r=mid-1
      
  return False
for i in range(Q):
  a,b,c=map(str,input().split())
  a=int(a);b=int(b)-1
  if a==1:
    S[b-1]=c
  else:
    c=int(c)-1
    ans=0
    K=sorted(S[b:c+1])
    for j in D:
      if K[0]>j:
        pass
      elif K[-1]<j:
        break
      elif lower_bound(K,j):
        ans+=1
    print(ans)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache


class SegmentTree():
    def __init__(self, S):
        # S:英小文字からなる配列
        # tmp = len(S)
        # cnt = 0
        # while tmp // 2 > 0:
        #     tmp //= 2
        #     cnt += 1
        self.size = 19
        # sizeはSの長さ<=2**nをみたす最小のn
        self.array = [set()] * (2**(self.size + 1) - 1)
        for i, c in enumerate(S):
            self.array[i + 2**self.size - 1] = {c}
        for i in range(2**self.size - 1)[::-1]:
            self.array[i] = self.array[2 * i + 1] | self.array[2 * i + 2]

    @lru_cache(maxsize=1000)
    def subquery(self, l, r, k, i, j):
        # 区間[i,j)の中で区間[l,r)の文字列の集合を返す
        if j <= l or r <= i:
            return set()
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_set = self.subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_set = self.subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return l_set | r_set

    def query(self, l, r):
        # [l,r)に含まれる文字の種類数
        return len(self.subquery(l, r, 0, 0, 2**self.size))

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = {c}
        while tmp > 0:
            tmp = (tmp - 1) // 2
            self.array[tmp] = self.array[2 * tmp + 1] | self.array[2 * tmp + 2]


N = int(input())
S = list(input())
Q = int(input())
tree = SegmentTree(S)
for q in range(Q):
    t, i, c = input().split()
    if t == '1':
        i = int(i) - 1
        tree.update(i, c)
    else:
        l, r = int(i) - 1, int(c)
        print(tree.query(l, r))
# S = ['a', 'b', 'c', 'd', 'b', 'b', 'd']
# tree = SegmentTree(S)
# print(tree.query(2, 6))

Submission status: Wrong Answer

Solution code:
n=int(input())
s=list(input())
q=int(input())
c=[chr(i) for i in range(97, 97+26)]
l=[input().split() for i in range(q)]

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

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

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

def query(p,q,c):
  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[c][p])
    if q&1==1:
      res=segfunc(res,seg[c][q])
      q-=1
    p=p//2
    q=(q-1)//2
  if p==q:
    res=segfunc(res,seg[c][p])
  else:
    res=segfunc(segfunc(res,seg[c][p]),seg[c][q])
  return res

ide_ele=0

num=2**(n-1).bit_length()
seg=[[ide_ele]*2*num for i in range(26)]

L=[[0 for i in range(n)] for j in range(26)]
for i in range(n):
  L[c.index(s[i])][i]+=1

for i in range(26):
  init(L[i],i)

for i in range(q):
  if l[i][0]=='1':
    update(int(l[i][1])-1,1,c.index(l[i][2]))
    update(int(l[i][1])-1,-1,c.index(s[int(l[i][1])-1]))
  else:
    ct=0
    for j in range(26):
      if query(int(l[i][1])-1,int(l[i][2]),j)!=0:
        ct+=1
    print(ct)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=list(input())
q=int(input())
c=[chr(i) for i in range(97, 97+26)]
l=[input().split() for i in range(q)]

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

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

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

def query(p,q,c):
  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[c][p])
    if q&1==1:
      res=segfunc(res,seg[c][q])
      q-=1
    p=p//2
    q=(q-1)//2
  if p==q:
    res=segfunc(res,seg[c][p])
  else:
    res=segfunc(segfunc(res,seg[c][p]),seg[c][q])
  return res

ide_ele=0

num=2**(n-1).bit_length()
seg=[[ide_ele]*2*num for i in range(26)]

L=[[0 for i in range(n)] for j in range(26)]
for i in range(n):
  L[c.index(s[i])][i]+=1

for i in range(26):
  init(L[i],i)

for i in range(q):
  if l[i][0]=='1':
    update(int(l[i][1])-1,1,c.index(l[i][2]))
    update(int(l[i][1])-1,-1,c.index(s[int(l[i][1])-1]))
  else:
    ct=0
    for j in range(26):
      if query(int(l[i][1])-1,int(l[i][2]),j)!=0:
        ct+=1
    print(ct)

Submission status: Wrong Answer

Solution code:
def order(c):
    return 1 << (ord(c) - 97)

def count(n):
    return bin(n).count("1")

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

def main():
    N = int(input())
    S = [x for x in input()]
    Q = int(input())
    L = 1
    while L < N:
        L *= 2
    L*=2 
    Seg = [0]*(L*2)

    def update(k, x):
        k += L 
        Seg[k] = x
        while k > 0:
            k = (k - 1) // 2
            Seg[k] = Seg[2*k+1]|Seg[2*k+2]
        Seg[0] = Seg[1]|Seg[2]

    def find(a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            #print("find*", (a,b,k,l,r), "=",count(Seg[k]))
            return Seg[k]
        vl = find(a, b, 2*k+1, l, (l+r)//2)
        vr = find(a, b, 2*k+2, (l+r)//2, r)
        #print("find_", (a,b,k,l,r), "=",count(merge(vl, vr)))
        return merge(vl, vr)

    # read S, and update tree
    for i in range(N):
        update(i, order(S[i]))
        #print("Seg", *[count(x) for x in Seg])
    #print("Seg=", [count(x) for x in Seg])
    return
    for _ in range(Q):
        q, i, c = input().split()
        if q == '1':
            i = int(i)-1
            if S[i] == c:
                continue
            S[i] = c
            update(i, order(S[i]))
            #print("Seg=", [count(x) for x in Seg])
        else:
            l, r = int(i), int(c)
            #print((l,r))
            print(count(find(l, r+1, 0, 0, L)))
main()