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:
n = int(input())
s = list(input())
q = int(input())
ds = [dict()]
dq = dict()

for i in range(n):
    d = ds[i].copy()
    if s[i] in d:
        d[s[i]] += 1
    else:
        d[s[i]] = 1
    ds += [d]

def dict_sub(d1, d2):
    d3 = d1.copy()
    d4 = d2.copy()
    for k,v in d4.items():
        if k in d3:
            d3[k] -= v
        else:
            d3[k] = -v
    return d3


def dict_add(d1, d2):
    d3 = d1.copy()
    d4 = d2.copy()
    for k,v in d4.items():
        if k in d3:
            d3[k] += v
        else:
            d3[k] = v
    return d3


def dict_len(d):
    ret = 0
    for v in d.values():
        if v > 0:
            ret += 1
    return ret

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

    if a == '1':
        b = int(b) - 1
        ch.add(b)
        if b not in dq:
            dq[b] = dict()
        er = s[b]
        if c in dq[b]:
            dq[b][c] += 1
        else:
            dq[b][c] = 1
        if er in dq[b]:
            dq[b][er] -= 1
        else:
            dq[b][er] = -1
        s[b] = c

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(input())
q = int(input())

ql = []

for _ in range(q):
  ql += [input().split()]

i = 0  
  
while i != len(ql):
  a, b, c = ql[i]
  if a == '1':
    i += 1
    continue
  l = int(b)
  r = int(c)
  del ql[i]
  tmp = []
  for j in range(i-1):
    if l <= int(ql[j][1]) <= r:
      s[int(ql[j][1])-1] = ql[j][2]
      tmp.append(j)
      
  for j in reversed(tmp):
    del ql[j]
    i -= 1
    
  print(len(set(s[l-1:r])))

Submission status: Wrong Answer

Solution code:
import math
import collections

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


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

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

    return A

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

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

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

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

        c_org = S[i - 1] # 元の文字
        # li[c_org][i] -= 1

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
S = list(input())
Q = int(input())

res = []

for _ in range(Q):
    t, q1, q2 = input().split(' ')
    if t == '1':
        S[int(q1)-1] = q2
    else:
        if q1 == q2:
            res.append(1)
        elif int(q2) == N:
            r = len(set(S[int(q1)-1:]))
            res.append(r)
        else:
            r = len(set(S[int(q1)-1:int(q2)-1]))
            res.append(r)

for r in res:
    print(r)

Submission status: Wrong Answer

Solution code:
def print_ans(p,q):
    t = [i for i in NUM_WORD[q]]
    if p>0:
        for i,j in enumerate(NUM_WORD[p-1]):
            t[i] -= j
    for change in CHANGE:
        if p<=change[0]<=q:
            t[change[1]] -= 1
            t[change[2]] += 1
    ans = 0
    for i in t:
        if i!=0:
            ans += 1
    print(ans)


def alpha_to_num(x):
    return ord(x) - 97

N = int(input())
s = input()
Q = int(input())
Questions = []
for i in range(Q):
    Questions.append(input().split())

NUM_WORD = [[0]*26 for i in range(N)]
NUM_WORD[0][alpha_to_num(s[0])] = 1

for i in range(1, N):
    for j in range(26):
        NUM_WORD[i][j] = NUM_WORD[i-1][j]
    NUM_WORD[i][alpha_to_num(s[i])] += 1

CHANGE = []
# [p,q,r]
# No.p, q->r

for question in Questions:
    if question[0]=='2':
        p,q = int(question[1]), int(question[2])
        print_ans(p-1,q-1)
    else:
        p,q = int(question[1]), alpha_to_num(question[2])
        l = alpha_to_num(s[p-1])
        CHANGE.append([p-1, l, q])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
s = list(str(input().rstrip()))
q = int(input())


class SSQ:
    def __init__(self, n, e):
        # 単位元
        self.e = e
        # num_min:n以上の最小の2のべき乗
        self.num_min = 2**(n-1).bit_length()
        self.seg_min = [self.e]*2*self.num_min

    def update(self, k, x):
        k += self.num_min-1
        self.seg_min[k] = x
        while k:
            k = (k-1)//2
            self.seg_min[k] = self.seg_min[k*2+1] or self.seg_min[k*2+2]

    def query(self, p, q):
        q += 1
        if q <= p:
            return self.e
        p += self.num_min-1
        q += self.num_min-2
        res = self.e
        while q-p > 1:
            if p & 1 == 0:
                res = res or self.seg_min[p]
            if q & 1 == 1:
                res = res or self.seg_min[q]
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = res or self.seg_min[p]
        else:
            res = res or self.seg_min[p] or self.seg_min[q]
        return res

ssqs = [SSQ(n, False) for i in range(26)]

for i in range(n):
    ssqs[ord(s[i]) - ord('a')].update(i, True)

out = []
for i in range(q):
    com, x, y = list(input().split())
    if com == '1':
        idx = int(x) - 1
        pre_alph = ord(s[idx-1]) - ord('a')
        ssqs[pre_alph].update(idx, False)
        alph = ord(y) - ord('a')
        s[idx-1] = y
        ssqs[alph].update(idx, True)
    else:
        x, y = int(x) - 1, int(y) - 1
        cnt = 0
        for i in range(26):
            cnt += ssqs[i].query(x, y)
        out.append(str(cnt))
print("\n".join(out))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
Q = int(input())
alps = 'abcdefghijklmnopqrstuvwxyz'
A = []
B = []
for _ in range(Q):
  t, a, b = input().split()
  if t == '1':
    A.append(a)
    B.append(b)
  else:
    dp = {}
    s = S[int(a)-1:int(b)]
    for alp in alps:
      dp[alp] = s.count(alp)
    if A:
      for i in range(len(A)):
        dp[S[int(A[i])-1]] -= 1
        dp[B[i]] += 1

    print(len(list(filter(lambda x: x != 0, dp.values()))))

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
kijun = ord("a")
n = int(readline())
s = readline().rstrip().decode('utf-8')
q = int(readline())
key =[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
lst1 = [0]*n
for i in range(n):
    lst1[i] = key[ord(s[i])-kijun]
#####segfunc######
def segfunc(x,y):
    return x*y

def init(init_val): #渡されたリストでsegを初期化
    #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): #segの要素kをxに変更(セグ木全体の更新)
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        if seg[k]%x == 0:
            continue
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q): #区間[p,q)での、segfuncに準じた値を返す
    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

#####単位元######
"""
最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
　　和のセグ木 → 0　(上の単位元の説明を参照)
　　積のセグ木 → 1　(上の単位元の説明を参照)
　　gcdのセグ木 → 0　(gcdを更新しない値は0)
"""
ide_ele = 1

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num #単位元の配列(計算結果に影響を及ぼさない配列)を作成

init(lst1)

def judge(u):
    res = 0
    for i in key:
        if u%i == 0:
            res += 1
    return res

for i in range(q):
    t,x,y = readline().rstrip().decode('utf-8').split()
    if t == "1":
        update(int(x)-1,key[ord(y)-kijun])
    else:
        print(judge(query(int(x)-1,int(y))))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = list(input())
qN = int(input())
#Q=[list(map(int, input().split())) for i in range(qN)]
#Q=[list(input().split()) for i in range(qN)]

print(S)
#print(Q)

for i in range(qN):
    Q=list(input().split())
    if int(Q[0])==1:
        S[int(Q[1])-1]=Q[2]
    else :
        if int(Q[2])!=N:
            #print(S[int(Q[i][1])-1:int(Q[i][2])])
            print(len(set(S[int(Q[1])-1:int(Q[2])])))
        else: 
            print(len(set(S[int(Q[1])-1:])))          
            
        #count=len(set(S[Q[i][1]-1:end]))  
        #print(count)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

tmp = 'abcdefghijklmnopqrstuvwxyz'
n = I()
s = list(input())
cnt = [0]*n
alpha = defaultdict(list)
for i in range(n):
    alpha[s[i]].append(i)

q = I()
f = defaultdict(list)
for _ in range(q):
    num, i, c = input().split()
    if int(num) == 1:
        f[s[int(i)-1]].append(int(i)-1)
        alpha[c].append(int(i)-1)
    else:
        cnt = 0
        for j in range(26):
            l = bl(alpha[tmp[j]],int(i)-1)
            r = br(alpha[tmp[j]],int(c)-1)
            L = bl(f[tmp[j]],int(i)-1)
            R = br(f[tmp[j]],int(i)-1)
            if r-l - (R-L)> 0:
                cnt += 1
            #print(tmp[j],alpha[tmp[j]],int(i),int(c),l,r)
        print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
kijun = ord("a")
n = int(readline())
s = readline().rstrip().decode('utf-8')
q = int(readline())
key =[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
mod = 10**9+7
lst1 = [0]*n
for i in range(n):
    lst1[i] = key[ord(s[i])-kijun]
#####segfunc######
def segfunc(x,y):
    return x*y%mod

def init(init_val): #渡されたリストでsegを初期化
    #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): #segの要素kをxに変更(セグ木全体の更新)
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        if seg[k]%x == 0:
            continue
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q): #区間[p,q)での、segfuncに準じた値を返す
    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

#####単位元######
"""
最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
　　和のセグ木 → 0　(上の単位元の説明を参照)
　　積のセグ木 → 1　(上の単位元の説明を参照)
　　gcdのセグ木 → 0　(gcdを更新しない値は0)
"""
ide_ele = 1

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num #単位元の配列(計算結果に影響を及ぼさない配列)を作成

init(lst1)

def judge(u):
    res = 0
    for i in key:
        if u%i == 0:
            res += 1
    return res

for i in range(q):
    t,x,y = readline().rstrip().decode('utf-8').split()
    if t == "1":
        update(int(x)-1,key[ord(y)-kijun])
    else:
        print(judge(query(int(x)-1,int(y))))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
Q = int(input())
for _ in range(Q):
  t, i, c = map(str, input().split())
  t = int(t)
  i = int(i)
  if t==1:
    S = S[:i] + c + S[i+1:]
  else:
    c = int(c)
    print(len(set(S[i-1:c])))

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
q=int(input())
def segfunc(x,y):
    return x|y
def init(init_val,var):
    #set_val
    for i in range(n):
        seg[var][i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[var][i]=segfunc(seg[var][2*i+1],seg[var][2*i+2]) 
    
def update(k,x,var):
    k += num-1
    seg[var][k] = x
    while k:
        k = (k-1)//2
        seg[var][k] = segfunc(seg[var][k*2+1],seg[var][k*2+2])
    
def query(p,q,var):
    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[var][p])
        if q&1 == 1:
            res = segfunc(res,seg[var][q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[var][p])
    else:
        res = segfunc(segfunc(res,seg[var][p]),seg[var][q])
    return res

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

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[[ide_ele]*2*num for i in range(26)]
for i in range(n):
    update(i,1,ord(s[i])-97)
for i in range(q):
    a,b,c=input().split()
    if a=="1":
        update(int(b)-1,0,ord(s[int(b)-1])-97)
        update(int(b)-1,1,ord(c)-97)
    else:
        ans=0
        for j in range(26):
            ans+=query(int(b)-1,int(c),j)
        print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict

class SegmentTree:
    def __init__(self, N, func):
        n_ = 1
        
        while n_<N:
            n_ *= 2
            
        self.n = n_
        self.func = func
        
        if self.func==max:
            self.ele = -10**18
        elif self.func==min:
            self.ele = 10**18
        
        self.arr = [self.ele]*(2*self.n-1)
    
    def update(self, k, a):
        k += self.n-1
        self.arr[k] = a
        
        while k>0:
            k = (k-1)//2
            self.arr[k] = self.func(self.arr[2*k+1], self.arr[2*k+2])
     
    def query(self, l, r): #[l:r)
        L, R = l+self.n, r+self.n
        res = self.ele
        
        while L<R:
            if R&1:
                R -= 1
                res = self.func(res, self.arr[R-1])
            
            if L & 1:
                res = self.func(res, self.arr[L-1])
                L += 1
            
            L >>= 1
            R >>= 1
        
        return res

N = int(input())
S = input()
Q = int(input())
sts = []

for _ in range(26):
    st = SegmentTree(N, max)
    
    for i in range(N):
        st.update(i, 0)
        
    sts.append(st)

d = defaultdict(int)
c = 0

for a in 'abcdefghijklmnopqrstuvwxyz':
    d[a] = c
    c += 1

for i in range(N):
    h = d[S[i]]
    sts[h].update(i, 1)

for _ in range(Q):
    inp = input().split()
    ty = int(inp[0])
    
    if ty==1:
        i = int(inp[1])-1
        s = inp[2]
        
        if S[i]==c:
            continue
        
        h = d[S[i]]
        sts[h].update(i, 0)
        h = d[s]
        sts[h].update(i, 1)
    else:
        ans = 0
        l = int(inp[1])-1
        r = int(inp[2])
        
        for i in range(26):
            if sts[i].query(l, r)==1:
                ans += 1
        
        print(ans)

Submission status: Wrong Answer

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

sys.setrecursionlimit(300000)



def update(i, val, n, bi_tree, sign=1):
    i += 1
    while i < n:
        bi_tree[i][val] += (1 * sign)
        i += i & -i


def get_sum(i, bi_tree):
    ans = [0] * 26
    while i > 0:
        tmp = bi_tree[i]
        for j in range(26):
            ans[j] += tmp[j]
        #ans += bi_tree[index]
        i -= i & -i
    return ans


def get_range_sum(left, right, bi_tree):
    r_sum = get_sum(right, bi_tree)
    l_sum = get_sum(left - 1, bi_tree)
    for i in range(26):
        r_sum[i] -= l_sum[i]
    return r_sum


from pprint import pprint

def solve(N, S, Q, queries):
    #arr.insert(0, 0)   # insert dummy node for 1-based indexing
    #bit = [0 for i in range(n+1)]
    bit = [[0] * 26 for i in range(N + 1)]
    s = []
    for i, c in enumerate(S):
        if 'a' <= c <= 'z':
            update(i, ord(c) - ord('a'), N + 1, bit)
        s.append(c)
    #pprint(bit)
    #return

    for q in queries:
        if q[0] == '1':
            i, c = int(q[1]) - 1, q[2]
            p = s[i]
            update(i, ord(p) - ord('a'), N, bit, -1)
            update(i, ord(c) - ord('a'), N, bit, 1)
            s[i] = c
        if q[0] == '2':
            l, r = int(q[1]), int(q[2])
            counts = get_range_sum(l, r, bit)
            ret = 0
            for x in counts:
                if x > 0:
                    ret += 1
            print(ret)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))
    S = str(next(tokens))
    Q = int(next(tokens))
    q = []
    for i in range(Q):
        q.append(list(map(str, input().split())))
    solve(N, S, Q, q)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
q = int(input())
for _ in range(q):
    t,a,b = input().split()
    a = int(a)
    if t == "1":
        s = s[:a-1] + b + s[a-1:]
    else:
        b = int(b)
        print(len(set(s[a-1:b])))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
def main():
    N = int(input())
    S = list(input())
    Q = int(input())
    ans = []
    for _ in range(Q):
        flag, IL, CR = input().split()
        if flag == "1":
            S[int(IL)] = CR
        elif flag == "2":
            cutted = S[int(IL) - 1:int(CR)]
            ans.append(len(set(cutted)))
    for i in ans:
        print(i)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
s = []
A = [[] for i in range(26)]
for i in range(N):
    x = S[i]
    s.append(x)
    n = ord(x) - 97
    A[n].append(i)
Q = int(input())
import bisect
for i in range(Q):
    q,a,b = map(str,input().split())
    a = int(a)
    a -= 1
    if q == '1':
        x = s[a]
        s[a] = b
        A[ord(x)-97].remove(a)
        A[ord(b)-97].append(a)

Submission status: Wrong Answer

Solution code:
from math import ceil, log
from operator import __or__

N = int(input())
S = input()
Q = int(input())
Query = [input().split() for _ in range(Q)]

abc = dict(zip("abcdefghijklmnopqrstuvwxyz", range(26)))


class SegmentTree:
    def __init__(self, length, init_value=None, aggfunc=min):
        self.init_value = init_value
        self.aggfunc = aggfunc

        self.data = [init_value] * (2 ** (1 + ceil(log(length, 2))) - 1)
        self.origin = len(self.data) // 2

    def update(self, idx, value):
        i = idx + self.origin
        self.data[i] = value
        while i > 0:
            i = (i - 1) // 2
            new_value = self.aggfunc(self.data[i * 2 + 1], self.data[i * 2 + 2])
            if self.data[i] != new_value:
                self.data[i] = new_value
            else:
                break

    def query(self, start, stop):
        return self._query(start, stop, 0, 0, self.origin + 1)

    def _query(self, start, stop, k, l, r):
        if (start <= l) & (r <= stop):
            return self.data[k]
        elif (r <= start) | (stop <= l):
            return self.init_value
        else:
            return self.aggfunc(
                self._query(start, stop, k * 2 + 1, l, (l + r) // 2),
                self._query(start, stop, k * 2 + 2, (l + r) // 2, r),
            )


segs = [SegmentTree(N, False, __or__) for _ in range(26)]
for i in range(N):
    letter = abc[S[i]]
    segs[letter].update(i, True)

for q1, q2, q3 in Query:
    if q1 == "1":
        ind = int(q2)
        letter = abc[S[i]]
        segs[letter].update(ind, False)
        letter = abc[q3]
        segs[letter].update(ind, True)
    else:
        ans = sum(seg.query(int(q2) - 1, int(q3)) for seg in segs)
        print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
S = input()
nums = np.zeros((26, N+1), dtype=np.int64)
for i in range(1,N+1):
    nums[:,i] = nums[:,i-1]
    c = ord(S[i-1]) - ord('a')
    nums[c,i] = nums[c,i-1] + 1

Q = int(input())
for i in range(Q):
    t, a, b = input().split()
    if t == '1':
        a = int(a)
        c = ord(S[a-1]) - ord('a')
        nums[c,a:] -= 1
        c = ord(b) - ord('a')
        nums[c,a:] += 1
    else:
        a = int(a)
        b = int(b)
        cnt = np.count_nonzero(nums[:,b] - nums[:,a-1])
        print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input().rstrip())
S = input().rstrip()
Q = int(input().rstrip())
for _ in range(Q):
    type, a, b = input().rstrip().split()
    if type == '1':
        i = int(a)
        c = b
        S = S[:i] + c + S[i+1:]
    elif type == '2':
        l = int(a)
        r = int(b)
        print(len(set(list(S[l-1:r]))))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
s = []
A = [[] for i in range(26)]
for i in range(N):
    x = S[i]
    s.append(x)
    n = ord(x) - 97
    A[n].append(i)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
kijun = ord("a")
n = int(readline())
s = readline().rstrip().decode('utf-8')
q = int(readline())
key =[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
mod = 10**9+7
lst1 = [0]*n
for i in range(n):
    lst1[i] = key[ord(s[i])-kijun]
#####segfunc######
def segfunc(x,y):
    return x*y%mod

def init(init_val): #渡されたリストでsegを初期化
    #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): #segの要素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): #区間[p,q)での、segfuncに準じた値を返す
    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

#####単位元######
"""
最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
　　和のセグ木 → 0　(上の単位元の説明を参照)
　　積のセグ木 → 1　(上の単位元の説明を参照)
　　gcdのセグ木 → 0　(gcdを更新しない値は0)
"""
ide_ele = 1

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num #単位元の配列(計算結果に影響を及ぼさない配列)を作成

init(lst1)

def judge(u):
    res = 0
    for i in key:
        if u%i == 0:
            res += 1
    return res

for i in range(q):
    t,x,y = readline().rstrip().decode('utf-8').split()
    if t == "1":
        update(int(x)-1,key[ord(y)-kijun])
    else:
        print(judge(query(int(x)-1,int(y))))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [ord(a) - 97 for a in input()]
NN = 19
BIT=[[0]*(2**NN+1) for _ in range(26)]
 
def addbit(t, i, x):
    while i <= 2**NN:
        BIT[t][i] += x
        i += i & (-i)

def getsum(t, i):
    ret = 0
    while i != 0:
        ret += BIT[t][i]
        i -= i&(-i)
    return ret


for i, a in enumerate(A):
    BIT[a][i+1] += 1

for t in range(26):
    B = [0] * (2**NN+1)
    for i in range(1<<NN):
        B[i+1] = B[i] + BIT[t][i]
    for i in range(1<<NN):
        BIT[t][i] = B[i] - B[i - (i & (-i))]

Q = int(input())
for _ in range(Q):
    a, b, c = input().rstrip().split()
    if a == "1":
        b = int(b)
        c = ord(c) - 97
        t = A[b-1] - 1
        addbit(t, b, -1)
        addbit(c, b, 1)
    else:
        b, c = int(b), int(c)
        s = 0
        for t in range(26):
            s += 1 if getsum(t, c+1) - getsum(t, b) else 0
        print(s)

Submission status: Wrong Answer

Solution code:
class SegmentTree:
    def __init__(self, a):      
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        l = []
        for _a in a:
            l.append({'dic':{_a:1}, 'set':set(_a)})
        self.data = [{'dic':{}, 'set':set()} for i in range(self.N-1)] + l + [{'dic':{}, 'set':set()} for i in range(self.N-self.n)]
        for i in range(2*self.N-2, 0, -2):
            self.data[(i-1)//2] = self.init_func(self.data[i], self.data[i-1])
    
    def init_func(self, data1, data2):
        s = data1['set'] | data2['set']
        d = data1['dic']
        for k in data2['dic']:
            if k in d:
                d[k] += data2['dic'][k]
            else:
                d[k] = data2['dic'][k]
        return {'dic':d, 'set':s}

    def __len__(self):
        return self.n
    
    def func(self, idx, x1, x2):
        self.data[idx]['dic'][x1] -= 1
        if self.data[idx]['dic'][x1] == 0:
            self.data[idx]['set'].discard(x1)
        if x2 in self.data[idx]['dic']:
            self.data[idx]['dic'][x2] += 1
            if self.data[idx]['dic'][x2] == 1:
                self.data[idx]['set'].add(x2)
        else:
            self.data[idx]['dic'][x2] = 1
            self.data[idx]['set'].add(x2)        

    def update(self, i, x):
        idx = self.N - 1 + i
        pre = list(self.data[idx]['dic'].keys())[0]
        self.data[idx] = {'dic':{x:1}, 'set':set(x)}
        while idx:
            idx = (idx-1) // 2
            self.func(idx, pre, x)
    
    def query(self, i, j):
        # [i, j)
        if i == j:
            return len(self.data[self.N - 1 + i]['set'])
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = set()
            while idx1 + 1 < idx2:
                if idx1&1 == 0: # idx1が偶数
                    result = result | self.data[idx1]['set']
                if idx2&1 == 1: # idx2が奇数
                    result = result | self.data[idx2]['set']
                    idx2 -= 1
                
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            
            if idx1 == idx2:
                result = result | self.data[idx1]['set']
            else: # idx1 + 1 == idx2
                result = result | self.data[idx1]['set'] | self.data[idx2]['set']
            
            return len(result)

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

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

Submission status: Wrong Answer

Solution code:
MAX = set()

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


n_ = 1
while (n_ < n):
  n_ *= 2

dat = [set() for _ in range(2 * n_ - 1)]


def update(k, a):
  k += n - 1
  dat[k] = set(a)
  while (k > 0):
    k = (k - 1) // 2
    dat[k] = dat[k * 2 + 1] | dat[k * 2 + 2]


def query_(a, b, k, l, r):
  if r <= a or b <= l:
    return MAX
  if a <= l and r <= b:
    return dat[k]
  else:
    return query_(a, b, k * 2 + 1, l, (l + r) // 2) | query_(a, b, k * 2 + 2, (l + r) // 2, r)


def query(a, b):
  return query_(a, b, 0, 0, n_)

for i, c in enumerate(s):
  update(i - 1, c)

Q = int(input())
for _ in range(Q):
  Query = input()
  if Query[0] == '1':
    i, c = Query[2:].split()
    i = int(i)
    update(i - 1, c)
  elif Query[0] == '2':
    l, r = map(int, Query[2:].split())
    print(len(query(l - 1, r - 1)) + 1)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
Q = int(input())
query = [input().split() for _ in range(Q)]

bit = [[0 for _ in range(26)] for _ in range(N + 1)]

def bit_add(i, s):
    ss = ord(s) - ord("a")
    while i <= N:
        bit[i][ss] += 1
        i += i & - i
def bit_add2(i, s):
    ss = ord(s) - ord("a")
    while i <= N:
        bit[i][ss] += -1
        i += i & - i
        
def bit_sum(i):
    s = [0] * 26
    while i:
        for j in range(26):
            s[j] += bit[i][j]
        i -= i & -i
    return s
for i in range(1, N + 1):
    s = S[i - 1]
    bit_add(i, s)

for x, y, z in query:
    if x == "1":
        y = int(y)
        bit_add(y, z)
        bit_add2(y, S[y - 1])
    if x == "2":
        answer = 0
        y, z = int(y) - 1, int(z)
        yy = bit_sum(y)
        zz = bit_sum(z)
        #print(yy)
        #print(zz)
        for i in range(26):
            if zz[i] - yy[i] > 0:
                answer += 1
        print(answer)
    #print(bit_sum(N))

Submission status: Wrong Answer

Solution code:
def main():
  n = int(input())
  S = input()
  q = int(input())
  s = S[:]
  for _ in range(q):
    typ, a, b = input().split()
    if int(typ) == 1:
      i = int(a)-1
      if S[i] == b:
        continue
      s = s[:i] + b + s[i+1:]
    if int(typ) == 2:
      x = int(a)-1
      y = int(b)
      print(len(set(s[x:y])))
  
def input_list():
  return map(int, input().split())

import math
import fractions
import itertools
main()