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:
"""
セグメント木で行きたいところだけど、集合の管理が必要になるため、時間がかかりすぎてしまう。
と思いきや、文字の種類は26種類しかないので、問題ない。
"""
def main():
    import sys
    input = sys.stdin.readline
    from collections import Counter
    class BIT:
        def __init__(self,n):
            self.size = n
            self.tree = [Counter([]) for _ in range(n+1)]
    
        def change(self,i,x,y):
            while i <= self.size:
                if x in self.tree[i]:
                    self.tree[i][x] -= 1
                if y not in self.tree[i]:
                    self.tree[i][y] = 1
                else:
                    self.tree[i][y] += 1
                i += i&-i
    
        def sum(self,i):
            s = Counter([])
            while i > 0:
                s += self.tree[i]
                i -= i&-i
            cnt = 0
            return s


    N = int(input())
    S = list(input())
    Q = int(input())
    bit = BIT(N)
    for i in range(N):
        bit.change(i+1," ",S[i])

    for _ in range(Q):
        q,a,b = input().split()
        if q == "1":
            x = S[int(a)-1]
            bit.change(int(a),x,b)
        else:
            a = int(a)
            b = int(b)
            count = bit.sum(b) - bit.sum(a-1)
            ans = 0
            for v in count.values():
                if v > 0:
                    ans += 1
            print(ans)
main()

Submission status: Wrong Answer

Solution code:
"""
セグメント木で行きたいところだけど、集合の管理が必要になるため、時間がかかりすぎてしまう。
と思いきや、文字の種類は26種類しかないので、問題ない。
"""
def main():
    import sys
    input = sys.stdin.readline
    class segTree:
        def __init__(self,n):
            if bin(n).count("1") == 1:
                self.leaves = 2**(n.bit_length()-1)
            else:
                self.leaves = 2**n.bit_length()
            self.identity = set()
            self.tree = [set()]*(self.leaves*2)

        def merge(self,x,y):
            #ここにマージ処理を書く
            return x|y

        def update(self,i,x):
            i = i+self.leaves
            self.tree[i] = set(x)
            i >>= 1
            while i > 0:
                self.tree[i] = self.merge(self.tree[i*2],self.tree[i*2+1])
                i >>= 1

        def query(self,l,r):
            #[l:r)のクエリ結果を返す
            l = l + self.leaves
            r = r + self.leaves
            res = self.identity
            while l < r:
                if l&1:
                    res = self.merge(res,self.tree[l])
                    l += 1
                if r&1:
                    r -= 1
                    res = self.merge(res,self.tree[r])
                l >>= 1
                r >>= 1
            return len(res)


    N = int(input())
    S = list(input())
    Q = int(input())
    seg = segTree(N)
    for i in range(N):
        seg.update(i,S[i])

    for _ in range(Q):
        q,a,b = input().split()
        if q == "1":
            a = int(a)
            seg.update(a,b)
        else:
            a = int(a)
            b = int(b)
            print(seg.query(a-1,b))
main()

Submission status: Wrong Answer

Solution code:
"""
セグメント木で行きたいところだけど、集合の管理が必要になるため、時間がかかりすぎてしまう。
と思いきや、文字の種類は26種類しかないので、問題ない。
"""
class segTree:
    def __init__(self,n):
        if bin(n).count("1") == 1:
            self.leaves = 2**(n.bit_length()-1)
        else:
            self.leaves = 2**n.bit_length()
        self.identity = set()
        self.tree = [set()]*(self.leaves*2)

    def merge(self,x,y):
        #ここにマージ処理を書く
        return x|y

    def update(self,i,x):
        i = i+self.leaves
        self.tree[i] = set(x)
        i >>= 1
        while i > 0:
            self.tree[i] = self.merge(self.tree[i*2],self.tree[i*2+1])
            i >>= 1

    def query(self,l,r):
        #[l:r)のクエリ結果を返す
        l = l + self.leaves
        r = r + self.leaves
        res = self.identity
        while l < r:
            if l&1:
                res = self.merge(res,self.tree[l])
                l += 1
            if r&1:
                r -= 1
                res = self.merge(res,self.tree[r])
            l >>= 1
            r >>= 1
        return len(res)


N = int(input())
S = list(input())
Q = int(input())
seg = segTree(N)
for i in range(N):
    seg.update(i,S[i])

for _ in range(Q):
    q,a,b = input().split()
    if q == "1":
        a = int(a)
        seg.update(a,b)
    else:
        a = int(a)
        b = int(b)
        print(seg.query(a-1,b))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = list(input())
Q = int(input())
alphabet = "abcdefghijklmnopqrstuvwxyz"
num = dict()
for i, var in enumerate(alphabet):
  num[var] = i

class Bit():
  def __init__(self, N):
    self.__N = N
    self.__arr = [[0] * 26 for _ in range(1 + N)]
    
  def add_(self, x, a, i):
    while(x < self.__N + 1):
      self.__arr[x][i] += a
      x += x & -x
      
  def sum_(self, x, i):
    res = 0
    while(x > 0):
      res += self.__arr[x][i]
      x -= x & -x
    return res
  
  def sub_sum_(self, x, y, i):
    return self.sum_(y, i) - self.sum_(x, i)

Bit = Bit(N)
for i, var in enumerate(S):
  Bit.add_(i+1, 1, num[var])

for i in range(Q):
  q, l, r = input().split()
  if q == "1":
    l = int(l)
    temp = S[l-1]
    Bit.add_(l, -1, num[temp])
    Bit.add_(l, 1, num[r])
  else:
    l = int(l)
    r = int(r)
    res = 0
    for j in range(26):
      res += min(1, Bit.sub_sum_(l-1, r, j))
    print(res)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import defaultdict
N = int(input())
S = input()
Q = int(input())

dict = defaultdict(set)
for i in range(N):
    dict[S[i]].add(i)
# print(dict)

ans = []

for _ in range(Q):
    a, b, c = input().split()
    a = int(a)

    if a == 1:
        b = int(b) - 1
        if S[b] == c:
            continue
        else:
            dict[S[b]].discard(b)
            dict[c].add(b)

    elif a == 2:
        b = int(b) - 1
        c = int(c) - 1
        char_n = 0
        for key, value in dict.items():
            value = list(value)
            value.sort()
            x1 = bisect.bisect_left(value, b)
            x2 = bisect.bisect_right(value, c)
            if x2 - x1 > 0:
                char_n += 1
        ans.append(char_n)

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import defaultdict
N = int(input())
S = input()
Q = int(input())

dict = defaultdict(set)
for i in range(N):
    dict[S[i]].add(i)
# print(dict)

ans = []

for _ in range(Q):
    a, b, c = input().split()
    a = int(a)
    if a == 1:
        b = int(b) - 1
        dict[S[b]].discard(b)
        dict[c].add(b)

    elif a == 2:
        b = int(b) - 1
        c = int(c) - 1
        char_n = 0
        for key, value in dict.items():
            value = list(value)
            value.sort()
            x1 = bisect.bisect_left(value, b)
            x2 = bisect.bisect_right(value, c)
            if x2 - x1 > 0:
                char_n += 1
        ans.append(char_n)

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import bisect
N = int(input())
S = input()
Q = int(input())


dict = {}
chars = "abcdefghijklmnopqrstuvwxyz"
for i in range(26):
    dict[chars[i]] = set()
for i in range(N):
    dict[S[i]].add(i)
# print(dict)

ans = []

for _ in range(Q):
    a, b, c = input().split()
    a = int(a)
    if a == 1:
        b = int(b) - 1
        for key,value in dict.items():
            if b in value:
                value.discard(b)
                dict[c].add(b)
                break
    elif a == 2:
        b = int(b) - 1
        c = int(c) - 1
        char_n = 0
        for key, value in dict.items():
            value = list(value)
            x1 = bisect.bisect_left(value, b)
            x2 = bisect.bisect_right(value, c)
            if x2 - x1 > 0:
                char_n += 1
        ans.append(char_n)

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import defaultdict
N = int(input())
S = input()
Q = int(input())

dict = defaultdict(set)
for i in range(N):
    dict[S[i]].add(i)
# print(dict)

ans = []

for _ in range(Q):
    a, b, c = input().split()
    a = int(a)
    if a == 1:
        b = int(b) - 1
        for key in dict.keys():
            if b in dict[key]:
                dict[key].discard(b)
                dict[c].add(b)
                break
    elif a == 2:
        b = int(b) - 1
        c = int(c) - 1
        char_n = 0
        for key, value in dict.items():
            value = list(value)
            x1 = bisect.bisect_left(value, b)
            x2 = bisect.bisect_right(value, c)
            if x2 - x1 > 0:
                char_n += 1
        ans.append(char_n)

for i in ans:
    print(i)

Submission status: Wrong Answer

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

def or_more_pow_two(n):
    if (n & (n-1)) == 0:
        return n
    return 1<<(len(bin(n))-2)

class SegmentTree:
    def __init__(self, n, l):
        self.n = or_more_pow_two(n)*2
        self.tree = [0]*self.n
        for i, l_i in enumerate(l):
            self.tree[self.n//2+i] = l_i
        for i in reversed(range(1, self.n//2)):
            self.node_update(i)
            # print(self.tree[i])

    # 1-indexed: [l, r)
    def find(self, l, r, fl=1, fr="self.n//2+1", node=1):
        if fr == "self.n//2+1":
            fr = self.n//2+1
        # print(f"find: ({l}, {r}), ({fl}, {fr}), {node}")
        if l <= fl and fr <= r:
            # print("in", bin(self.tree[node])[2:])
            return self.tree[node]
        elif fr <= l or r <= fl:
            # print("out")
            return 0
        else:
            # print("overlap")
            mid = (fl+fr)//2
            a = self.find(l, r, fl=fl, fr=mid, node=2*node)
            b = self.find(l, r, fl=mid, fr=fr, node=2*node+1)
            return a | b

    def update(self, index, v):
        x = self.n//2+index
        self.tree[x] = v
        while x > 0:
            x >>= 1
            self.node_update(x)

    def node_update(self, index):
        self.tree[index] = self.tree[2*index] | self.tree[2*index+1]

def char_to_bit(c):
    i = ord(c) - 97
    return (1 << i)
def bit_to_type_count(b):
    # print(bin(b)[2:])
    r = bin(b)[2:].count("1")
    # print(r)
    return r
# def bit_to_char(b):
#     for i in range(26):


segtree = SegmentTree(N, map(char_to_bit, S))

for t, *query in QUERY:
    t = int(t)
    if t == 1:
        i, c = query
        i, c = int(i), c
        segtree.update(i, char_to_bit(c))
    elif t == 2:
        l, r = map(int, query)
        l, r = l, r+1
        r = segtree.find(l, r)
        r = bit_to_type_count(r)
        print(r)
    # print(list(map(bin, segtree.tree)))

Submission status: Wrong Answer

Solution code:
from collections import deque

class SegmentTree():
    def __init__(self,n,ide_ele,merge_func,init_val):
        self.n=n
        self.ide_ele=ide_ele
        self.merge_func=merge_func
        self.val=[0 for i in range(1<<n)]
        self.merge=[0 for i in range(1<<n)]
        self.parent=[-1 for i in range(1<<n)]
        deq=deque([1<<(n-1)])
        res=[]
        while deq:
            v=deq.popleft()
            res.append(v)
            if not v&1:
                gap=(v&-v)//2
                self.parent[v-gap]=v
                deq.append(v-gap)
                self.parent[v+gap]=v
                deq.append(v+gap)
        for v in res[::-1]:
            if v-1<len(init_val):
                self.val[v-1]=init_val[v-1]
            self.merge[v-1]=self.val[v-1]
            if not v&1:
                gap=(v&-v)//2
                self.merge[v-1]=self.merge_func(self.merge[v-1],self.merge[v-gap-1],self.merge[v+gap-1])

    def update(self,id,x):
        self.val[id]=x
        pos=id+1
        while pos!=-1:
            if pos&1:
                self.merge[pos-1]=self.val[pos-1]
            else:
                gap=(pos&-pos)//2
                self.merge[pos-1]=self.merge_func(self.val[pos-1],self.merge[pos+gap-1],self.merge[pos-gap-1])
            pos=self.parent[pos]

    def lower_kth_merge(self,nd,k):
        res=self.ide_ele
        if k==-1:
            return res
        maxi=nd-(nd&-nd)+1+k
        pos=maxi
        while pos!=self.parent[nd]:
            if pos<=maxi:
                res=self.merge_func(res,self.val[pos-1],self.merge[-(pos&-pos)//2+pos-1])
            pos=self.parent[pos]
        return res

    def upper_kth_merge(self,nd,k):
        res=self.ide_ele
        if k==-1:
            return res
        mini=nd+(nd&-nd)-1-k
        pos=mini
        while pos!=self.parent[nd]:
            if pos>=mini:
                res=self.merge_func(res,self.val[pos-1],self.merge[(pos&-pos)//2+pos-1])
            pos=self.parent[pos]
        return res

    def query(self,l,r):
        id=1<<(self.n-1)
        while True:
            if id-1<l:
                id+=((id)&(-id))//2
            elif id-1>r:
                id-=((id)&(-id))//2
            else:
                res=self.val[id-1]
                if id%2:
                    return res
                gap=((id)&(-id))//2
                L,R=id-gap,id+gap
                #print(l,r,id,L,R)
                left=self.upper_kth_merge(L,id-1-l-1)
                right=self.lower_kth_merge(R,r-id)
                return self.merge_func(res,left,right)

ide_ele=0

def seg_func(*args):
    res=ide_ele
    for val in args:
        res|=val
    return res

def popcount(x):
    x = x - ((x >> 1) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    return x & 0x0000007f

import sys

input=sys.stdin.readline

N=int(input())
S=input().rstrip()

init_val=[1<<(ord(S[i])-97) for i in range(N)]
test=SegmentTree(19,ide_ele,seg_func,init_val)

for _ in range(int(input())):
    t,l,r=input().split()
    t,l=int(t),int(l)
    if t==1:
        val=ord(r)-97
        test.update(l-1,1<<val)
    else:
        r=int(r)
        res=test.query(l-1,r-1)
        print(popcount(res))

Submission status: Wrong Answer

Solution code:
from collections import deque

class SegmentTree():
    def __init__(self,n,ide_ele,merge_func):
        self.n=n
        self.ide_ele=ide_ele
        self.merge_func=merge_func
        self.val=[0 for i in range(1<<n)]
        self.merge=[0 for i in range(1<<n)]
        self.parent=[-1 for i in range(1<<n)]
        deq=deque([1<<(n-1)])
        while deq:
            v=deq.popleft()
            if not v&1:
                gap=(v&-v)//2
                self.parent[v-gap]=v
                deq.append(v-gap)
                self.parent[v+gap]=v
                deq.append(v+gap)


    def update(self,id,x):
        self.val[id]=x
        pos=id+1
        while pos!=-1:
            if pos&1:
                self.merge[pos-1]=self.val[pos-1]
            else:
                gap=(pos&-pos)//2
                self.merge[pos-1]=self.merge_func(self.val[pos-1],self.merge[pos+gap-1],self.merge[pos-gap-1])
            pos=self.parent[pos]

    def lower_kth_merge(self,nd,k):
        res=self.ide_ele
        if k==-1:
            return res
        mini=nd-(nd&-nd)+1+k
        id=nd
        while True:
            gap=(id&-id)//2
            if id>mini:
                id-=gap
            elif id==mini:
                return self.merge_func(res,self.val[id-1])
            else:
                res=self.merge_func(res,self.val[id-1],self.merge[id-gap-1])
                id+=gap

    def upper_kth_merge(self,nd,k):
        res=self.ide_ele
        if k==-1:
            return res
        maxi=nd+(nd&-nd)-1-k
        id=nd
        while True:
            gap=(id&-id)//2
            if id>maxi:
                res=self.merge_func(res,self.val[id-1],self.merge[id+gap-1])
                id-=gap
            elif id==maxi:
                return self.merge_func(res,self.val[id-1])
            else:
                id+=gap

    def query(self,l,r):
        id=1<<(self.n-1)
        while True:
            if id-1<l:
                id+=((id)&(-id))//2
            elif id-1>r:
                id-=((id)&(-id))//2
            else:
                res=self.val[id-1]
                if id%2:
                    return res
                gap=((id)&(-id))//2
                L,R=id-gap,id+gap
                #print(l,r,id,L,R)
                left=self.upper_kth_merge(L,id-1-l-1)
                right=self.lower_kth_merge(R,r-id)
                return self.merge_func(res,left,right)

ide_ele=0

def seg_func(*args):
    res=ide_ele
    for val in args:
        res|=val
    return res

def popcount(x):
    x = x - ((x >> 1) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    return x & 0x0000007f

import sys

input=sys.stdin.readline

N=int(input())
S=input().rstrip()

test=SegmentTree(19,ide_ele,seg_func)
for i in range(N):
    val=ord(S[i])-97
    test.update(i,1<<val)

for _ in range(int(input())):
    t,l,r=input().split()
    t,l=int(t),int(l)
    if t==1:
        val=ord(r)-97
        test.update(l-1,1<<val)
    else:
        r=int(r)
        res=test.query(l-1,r-1)
        print(popcount(res))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
Q = int(input())
L = [[0] * 26 for _ in range(N+1)]
for i in range(N):
  for j in range(26):
    L[i+1][j] = L[i][j]
  x = ord(S[i]) - ord('a')
  L[i+1][x] += 1
  
for i in range(Q):
  a, b, c = input().split()
  if(int(a) == 1):
    #b番目をcに変える
    x = ord(S[int(b)-1]) - ord('a')
    y = ord(c) - ord('a')
    for k in range(int(b), N+1):
      L[k][x] -= 1
      L[k][y] += 1
  else:
    ans = 0
    LL = list()
    for k in range(26):
      LL.append(L[int(c)][k]-L[int(b)-1][k])
    for k in range(26):
      if(LL[k] != 0):
        ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


class BIT:
    def __init__(self, L):
        self.n = len(L)
        self.bit = [0] * (self.n + 1)

    def update(self, idx, x):
        while idx <= self.n:
            self.bit[idx] += x
            idx += idx & (-idx)

    def query(self, idx):
        res = 0
        while idx > 0:
            res += self.bit[idx]
            idx -= idx & (-idx)
        return res

    def sec_sum(self, left, right):
        return self.query(right) - self.query(left - 1)

    def debug(self):
        print(*[self.sec_sum(i, i) for i in range(1, self.n + 1)])


def resolve():
    n = int(input())
    S = list(input().rstrip())
    q = int(input())

    bits = [BIT(S) for _ in range(26)]
    for idx in range(1, n + 1):
        s = S[idx - 1]
        bits[ord(s) - ord("a")].update(idx, 1)

    for _ in range(q):
        query = list(input().split())
        if query[0] == "1":
            i, c = int(query[1]), query[2]
            prev = S[i - 1]
            bits[ord(prev) - ord("a")].update(i, -1)
            bits[ord(c) - ord("a")].update(i, 1)
        else:
            l, r = int(query[1]), int(query[2])
            res = 0
            for j in range(26):
                if bits[j].sec_sum(l, r):
                    res += 1
            print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
from string import ascii_lowercase

import numpy as np

input = sys.stdin.readline


class SegmentTree:
    def __init__(self, N, X, func, init_v):
        self.N = N
        self.func = func
        self.a2z = {s: i for i, s in enumerate(ascii_lowercase)}
        self.__build(X)

    def __build(self, X):
        # Initialize all nodes
        self.node = [np.zeros(26, dtype=np.int64) for _ in range(2 * self.N)]

        # Elementary intervals are stored
        for i, s in enumerate(X, self.N):
            self.node[i][self.a2z[s]] = 1

        # The internal nodes correspond to intervals that are the union of elementary intervals
        for i in range(self.N - 1, 0, -1):
            self.node[i] = self.func(self.node[i << 1], self.node[i << 1 | 1])

    def update(self, i, s, t):
        i += self.N - 1
        self.node[i][self.a2z[s]] -= 1
        self.node[i][self.a2z[t]] += 1
        while i > 1:
            i >>= 1
            self.node[i] = self.func(self.node[i << 1], self.node[i << 1 | 1])

    def query(self, l, r):
        """Query for right half-open interval [l, r).

        Args:
            l (int): index (1-based index)
            r (int): index (1-based index)
        """
        dst_l = np.zeros(26, dtype=np.int64)
        dst_r = np.zeros(26, dtype=np.int64)
        l += self.N - 1
        r += self.N - 1
        while l < r:
            if l & 1:
                dst_l = self.func(dst_l, self.node[l])
                l += 1
            if r & 1:
                r -= 1
                dst_r = self.func(self.node[r], dst_r)
            l >>= 1
            r >>= 1
        return self.func(dst_l, dst_r)


def main():
    N = int(input())
    S = input().rstrip()

    S = list(S)
    st = SegmentTree(N, S, func=np.add, init_v=np.zeros(shape=26, dtype=np.int64))

    ans = []
    Q = int(input())
    for _ in range(Q):
        query = input().split()
        q = int(query[0])
        if q == 1:
            i = int(query[1])
            t = query[2]
            s = S[i - 1]
            if s != t:
                st.update(i, s, t)
        else:
            l = int(query[1])
            r = int(query[2])
            res = st.query(l, r + 1)
            num = np.sum(res > 0)
            ans.append(num)

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
Q = int(input())
for _ in range(Q):
    q = input().split()
    if q[0] == '1': S = S[:int(q[1])]+q[2]+S[int(q[1]):]
    else:
        T = S[int(q[1]):int(q[2])+1]
        Chrs = set(list(S))
        print(len(Chrs))

Submission status: Wrong Answer

Solution code:
import bisect  # 配列二分法
from collections import defaultdict

N = int(input())
S = [*input()]
Q = int(input())
d = defaultdict(list)

# 各アルファベットの出現場所を記録
for i, c in enumerate(S):
    d[c] += [i]

# この時点でどのアルファベットについてもソート済み
# print(d)

for _ in range(Q):
    q, y, z = input().split()

    if q == '1':
        i = int(y) - 1  # 文字の変更位置

        if S[i] == z: continue  # 同じ文字の場合は処理終了

        # 削除 O(N)
        b = bisect.bisect(d[S[i]], i)  # 2分法で i の出現位置を(log N)で探す
        d[S[i]].pop(b - 1)  # 削除

        # 追加 O(N) かかる？
        S[i] = z
        bisect.insort(d[z], i) 

    else:
        left = int(y) - 1
        right = int(z) - 1

        count = 0
        for v in d.values():
            count += 1 if bisect.bisect(v, right) - bisect.bisect_left(v, left - 1) > 0 else 0

        print(count)

Submission status: Wrong Answer

Solution code:
import bisect  # 配列二分法
from collections import defaultdict

N = int(input())
S = [*input()]
Q = int(input())
d = defaultdict(list)

# 各アルファベットの出現場所を記録
for i, c in enumerate(S):
    d[c] += [i]

# この時点でどのアルファベットについてもソート済み
# print(d)

for _ in range(Q):
    q, y, z = input().split()

    if q == '1':
        i = int(y) - 1  # 文字の変更位置

        if S[i] == z: continue  # 同じ文字の場合は処理終了

        # 削除 O(N)
        b = bisect.bisect(d[S[i]], i)  # 2分法で i の出現位置を(log N)で探す
        d[S[i]].pop(b - 1)  # 削除

        # 追加 O(N) かかる？
        S[i] = z
        bisect.insort(d[z], i) 

    else:
        left = int(y) - 1
        right = int(z) - 1

        print(sum(bisect.bisect(v, right) - bisect.bisect_left(v, left - 1) > 0 for v in d.values()))

Submission status: Wrong Answer

Solution code:
import bisect  # 配列二分法
from collections import defaultdict

N = int(input())
S = [*input()]
Q = int(input())
d = defaultdict(list)

# 各アルファベットの出現場所を記録
for i, c in enumerate(S):
    d[c] += [i]

# この時点でどのアルファベットについてもソート済み
print(d)

for _ in range(Q):
    q, y, z = input().split()

    if q == '1':
        i = int(y) - 1  # 文字の変更位置

        if S[i] == z: continue  # 同じ文字の場合は処理終了

        # 削除 O(N)
        b = bisect.bisect(d[S[i]], i)  # 2分法で i の出現位置を(log N)で探す
        d[S[i]].pop(b - 1)  # 削除

        # 追加 O(N) かかる？
        S[i] = z
        bisect.insort(d[z], i) 

    else:
        left = int(y) - 1
        right = int(z) - 1

        print(sum(bisect.bisect(v, right) - bisect.bisect_left(v, left - 1) > 0 for v in d.values()))

Submission status: Wrong Answer

Solution code:
import sys
# from collections import defaultdict

N = int(sys.stdin.readline().rstrip())
S = sys.stdin.readline().rstrip()
Q = int(sys.stdin.readline().rstrip())

BIT = [[0 for _ in range(N + 1)] for _ in range(26)]  # 初期化（アルファベット分）
alpha = {"a": 0, "b": 1, "c": 2, "d": 3, "e": 4,
         "f": 5, "g": 6, "h": 7, "i": 8, "j": 9,
         "k": 10, "l": 11, "m": 12, "n": 13, "o": 14,
         "p": 15, "q": 16, "r": 17, "s": 18, "t": 19,
         "u": 20, "v": 21, "w": 22, "x": 23, "y": 24, "z": 25}


# 初期化
def initialize():
    global BIT, S, N
    for j in range(N):
        c = alpha[S[j]]  # 文字切り出し／index に変換
        i = j + 1
        while i <= N:
            BIT[c][i] += 1
            i += (i & -i)


def identify(i):
    for c in range(26):
        if sum(i, c) != sum(i - 1, c):
            return c


# 文字の交換
def change(i, before, after):

    global BIT, N
    while i < N:
        BIT[before][i] += -1
        BIT[after][i] += 1
        i += (i & -i)


# 文字数の取り出し
def sum(i, c):

    global BIT

    _sum = 0
    while i > 0:
        _sum += BIT[c][i]
        i -= (i & -i)

    return _sum

initialize()

for _ in range(Q):
    q, x, y = sys.stdin.readline().rstrip().split()
    if q == "1":
        i = int(x)
        ac = alpha[y]
        bc = identify(i)
        change(i, bc, ac)

    else:
        x = int(x)
        y = int(y)
        count = 0
        for c in range(26):
            if sum(y, c) != sum(x - 1, c):
                count += 1
        print(count)

Submission status: Wrong Answer

Solution code:
import sys
# from collections import defaultdict

N = int(sys.stdin.readline().rstrip())
S = sys.stdin.readline().rstrip()
Q = int(sys.stdin.readline().rstrip())

BIT = [{"a": 0, "b": 0, "c": 0, "d": 0, "e": 0,
        "f": 0, "g": 0, "h": 0, "i": 0, "j": 0,
        "k": 0, "l": 0, "m": 0, "n": 0, "o": 0,
        "p": 0, "q": 0, "r": 0, "s": 0, "t": 0,
        "u": 0, "v": 0, "w": 0, "x": 0, "y": 0, "z": 0} for _ in range(N + 1)]  # 初期化


def add(A, B):
    for k in A.keys():
        A[k] += B[k]
    return A


def sub(A, B):
    for k in A.keys():
        A[k] -= B[k]
    return A


def count(A):
    return 26 - list(A.values()).count(0)


def identify(i):
    d = sub(sum(i),sum(i-1))
    for k,v in d.items():
        if v == 1:
            return k

# 初期化
for j in range(N):

    i = j + 1
    while i <= N:
        BIT[i][S[j]] += 1
        i += (i & -i)


# 文字の交換
def change(i, c, char):

    global BIT, N

    while i < N:
        BIT[i][char] -= 1
        BIT[i][c] += 1
        i += (i & -i)


# 文字数の取り出し
def sum(i):

    global BIT, N

    _sum = {"a": 0, "b": 0, "c": 0, "d": 0, "e": 0,
            "f": 0, "g": 0, "h": 0, "i": 0, "j": 0,
            "k": 0, "l": 0, "m": 0, "n": 0, "o": 0,
            "p": 0, "q": 0, "r": 0, "s": 0, "t": 0,
            "u": 0, "v": 0, "w": 0, "x": 0, "y": 0, "z": 0}
    while i > 0:
        _sum = add(_sum, BIT[i])
        i -= (i & -i)

    return _sum


for _ in range(Q):
    q, x, y = sys.stdin.readline().rstrip().split()
    if q == "1":
        x = int(x)
        char = identify(x)
        change(x, y, char)

    else:
        x = int(x)
        y = int(y)
        print(count(sub(sum(y), sum(x - 1))))

Submission status: Wrong Answer

Solution code:
import sys
# from collections import defaultdict

N = int(sys.stdin.readline().rstrip())
S = sys.stdin.readline().rstrip()
Q = int(sys.stdin.readline().rstrip())

BIT = [{"a": 0, "b": 0, "c": 0, "d": 0, "e": 0,
        "f": 0, "g": 0, "h": 0, "i": 0, "j": 0,
        "k": 0, "l": 0, "m": 0, "n": 0, "o": 0,
        "p": 0, "q": 0, "r": 0, "s": 0, "t": 0,
        "u": 0, "v": 0, "w": 0, "x": 0, "y": 0, "z": 0} for _ in range(N + 1)]  # 初期化


def add(A, B):
    for k in A.keys():
        A[k] += B[k]
    return A


def sub(A, B):
    for k in A.keys():
        A[k] -= B[k]
    return A


def count(A):
    return 26 - list(A.values()).count(0)


# 初期化
for j in range(N):

    i = j + 1
    while i < N:
        BIT[i][S[j]] += 1
        i += (i & -i)


# 文字の交換
def change(i, c):

    global BIT, N

    while i < N:
        BIT[i][S[i - 1]] -= 1
        BIT[i][c] += 1
        i += (i & -i)


# 文字数の取り出し
def sum(i):

    global BIT, N

    _sum = {"a": 0, "b": 0, "c": 0, "d": 0, "e": 0,
            "f": 0, "g": 0, "h": 0, "i": 0, "j": 0,
            "k": 0, "l": 0, "m": 0, "n": 0, "o": 0,
            "p": 0, "q": 0, "r": 0, "s": 0, "t": 0,
            "u": 0, "v": 0, "w": 0, "x": 0, "y": 0, "z": 0}
    while i > 0:
        _sum = add(_sum, BIT[i])
        i -= (i & -i)

    return _sum


for _ in range(Q):
    q, x, y = sys.stdin.readline().rstrip().split()
    if q == "1":
        x = int(x)
        if x == 1:
            S = y + S[1:]
        elif x == N:
            S = S[:-1] + y
        else:
            S = S[:x - 1] + y + S[x:]

        change(x, y)

    else:
        x = int(x)
        y = int(y)
        print(count(sub(sum(y), sum(x - 1))))

        # sum