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:
import bisect
alp = "abcdefghijklmnopqrstuvwxyz"
N = int(input())
S = list(input())
Q = int(input())
A = [[] for i in range(len(alp))]
for i in range(N):
    A[alp.index(S[i])].append(i)
for i in range(Q):
    q = list(input().split())
    if q[0]=="1":
        iq,cq = int(q[1]),q[2]
        s = S[iq-1]
        b = bisect.bisect(A[alp.index(s)],iq-1)
        A[alp.index(s)].pop(b-1)
        bisect.insort(A[alp.index(cq)],iq-1)
        S[iq-1]=cq
    else:
        lq,rq = int(q[1]),int(q[2])
        cnt = 0
        for i in range(len(alp)):
            if A[i]==[]:continue
            b = bisect.bisect(A[i],lq-1)
            c = A[i][min(len(A[i])-1,b)]
            if lq<=c+1<=rq:cnt+=1
        print(cnt)
        continue

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left,bisect_right,insort
N = int(input())
S = list(input())
Q = int(input())
D = dict()
D2 = dict()# to be removed
D3 = dict()# to be added

for i in range(97,97+26):
    D[chr(i)] = []
    D2[chr(i)] = []
    D3[chr(i)] = []
for i in range(N):
    D[S[i]].append(i+1)
for i in range(Q):
    t,l,r = input().split()
    if t == str(1):
        k = int(l)
        c = r
        if S[k-1] == c:
            continue
        #delete
        if bisect_right(D2[S[k-1]],k)-bisect_left(D2[S[k-1]],k) == 0:
            insort(D2[S[k-1]],k)
        if bisect_right(D3[S[k-1]],k) - bisect_left(D3[S[k-1]],k) == 1:
            del D3[S[k-1]][bisect_left(D3[S[k-1]],k)]
        #add
        if bisect_right(D3[c],k)-bisect_left(D3[c],k) == 0:
            insort(D3[c],k)
        if bisect_right(D2[c],k)-bisect_left(D2[c],k) == 1:
            del D2[c][bisect_left(D2[c],k)]
        S[k-1] = c
        continue
    l = int(l)
    r = int(r)
    ans = 0
    for i in range(97,97+26):
        X = D[chr(i)]
        X2 = D2[chr(i)]
        X3 = D3[chr(i)]
        if bisect_right(X,r)-bisect_left(X,l) + bisect_right(X3,r)- bisect_left(X3,l) -bisect_right(X2,r)+bisect_left(X2,l)> 0:
            ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)


class SegTree:
    def __init__(self, s):

        N = len(s)

        self.default = set([None])

        # 簡単のために要素数を2のべき乗にしておく
        _n = N
        self.n = 1
        while (self.n < _n):
            self.n = self.n * 2

        self.tree = [self.default for _ in range(2 * self.n - 1)]

        for i, c in enumerate(s):
            self.update(i, c)

    def update(self, i, x):
        i = i + self.n - 1
        if x in self.tree[i]:
            return
        else:
            self.tree[i] = set([x])

        # 親を更新
        while (i > 0):
            i = (i - 1) // 2
            l = self.tree[i * 2 + 1]
            r = self.tree[i * 2 + 2]
            self.tree[i] = l | r

    def query(
        self,
        i_query_start,
        i_query_end,  # exclusive
        i_parent=0,
        i_parent_start=0,
        i_parent_end=None):
        if i_parent_end is None:
            i_parent_end = self.n
        if i_parent > self.n - 1:
            return self.default
        if (i_query_end <= i_parent_start
                or i_parent_end < i_query_start):  # クエリとレンジが重ならない
            return self.default
        elif (i_query_start <= i_parent_start
              and i_parent_end <= i_query_end):  # クエリがレンジを完全に含む
            return self.tree[i_parent]
        else:
            return self.query(i_query_start, i_query_end, 2 * i_parent + 1,
                           i_parent_start, (i_parent_start + i_parent_end) // 2) | \
                self.query(i_query_start, i_query_end, 2 * i_parent + 2,
                           (i_parent_start + i_parent_end) // 2, i_parent_end)


def resolve():
    N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    Q = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ

    # N, D = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # h_list = [int(x) for x in sys.stdin.readline().split()]  # 複数int

    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    # v_list = [int(sys.stdin.readline().split()[0]) for _ in range(N)]
    grid = [[x for x in sys.stdin.readline().split()]
            for _ in range(Q)]  # int grid

    logger.debug('{}'.format([grid]))

    seg = SegTree(S)

    for _type, a, b in grid:
        if _type == '1':
            a = int(a) - 1
            seg.update(a, b)

        else:
            a = int(a) - 1
            b = int(b) - 1
            retset = seg.query(a, b + 1)
            if None in retset:
                print(len(retset) - 1)
            else:
                print(len(retset))


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7"""
        output = """3
1
5"""
        self.assertIO(input, output)

Submission status: Wrong Answer

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

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

for _ in range(q):
    t,i,j=input().split()
    if t == '1':
        s[int(i)]=j
    else:
        c=collections.Counter(s[int(i)-1:int(j)])
        print(len(c))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Jan 24 14:37:00 2020

@author: matsui
"""

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

abc=[chr(i) for i in range(97,123) ]
import numpy as np
dp=np.zeros([N+1,26])

for i in range(1,N+1):
    index=abc.index(S[i-1])
    dp[i,:]=dp[i-1,:]
    dp[i,index]+=1

for i in range(Q):
    q=input().split()
    if int(q[0])==1:
        if S[int(q[1])-1] != q[2]:
            index1=abc.index(S[int(q[1])-1])
            index2=abc.index(q[2])
            for j in range(int(q[1]),N+1): 
                dp[j,index1]-=1
                dp[j,index2]+=1

    if int(q[0])==2:
        res=dp[int(q[2]),:]-dp[int(q[1])-1,:]
        ans=0
        for a in res:
            if a!=0: ans+=1
        print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(str(input()))
num = [[] for i in range(26)]
for i in range(n):
  num[ord(s[i])-ord("a")].append(i+1)
q = int(input())
for _ in range(q):
  nn,a,b = map(str,input().split())
  if nn == "1":
    a = int(a)-1
    num[ord(s[a])-ord("a")].remove(a+1)
    num[ord(b)-ord("a")].append(a+1)
    num[ord(b)-ord("a")].sort()
    s[a] = b
  #    print(s)
  #    print(num)
  else:
  #    print(num)
    ans = 0
    for i in range(26):
      if num[i] != []:
        if int(a) <= num[i][-1] and num[i][0] <= int(b):
          low1 = 0
          high1 = len(num[i])
          while low1+1 < high1:
            mid = (low1+high1)//2
            if int(a) <= num[i][mid]:
              high1 = mid
            else:
              low1 = mid
          low2 = 0
          high2 = len(num[i])
          while low2+1 < high2:
            mid = (low2+high2)//2
            if num[i][mid] <= int(b):
              low2 = mid
            else:
              high2 = mid
  #          print(i,"!!")
  #          print(low1,high1,low2,high2)
          if low1 <= low2:
            ans += 1
    print(ans)

Submission status: Wrong Answer

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

c = {}

for ql in QL:
    if ql[0] == '1':
        c[ql[1]] = ql[2]
    else:
        l = int(ql[1])
        r = int(ql[2])
        s = S[l-1:r]
        del_l = []
        for j in c:
            t = int(j)-l
            if 0 <= t <= r:
                s = s[:t] + c[j] + s[t+1:]
                del_l.append(j)
        for j in del_l:
            c.pop(j)
        print(len(''.join(set(s))))

        S = S[:l-1] + s + S[r:]

Submission status: Wrong Answer

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

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

  if a == 1:
    S = S[:b] + c + S[b+1:]
  elif a == 2:
    c = int(c)
    tmpS = S[b-1:(c)]
    tmpS = list(tmpS)
    setS = set(tmpS)
    print(len(setS))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
class BIT(): #1-indexed
    def __init__(self,n): #n: 要素数
        self.size=n
        self.bit=[0]*(n+1)
    def add(self,i,x): #i番目(1-indexed)にxを加算
        while i<=self.size:
            self.bit[i]+=x
            i+=i&-i
    def sum_1_to_i(self,i): #1番目からi番目(含む)までの総和(1-indexed)
        s=0
        while i>0:
            s+=self.bit[i]
            i-=i&-i
        return s
    def sum_i_to_j(self,i,j): #i番目からj番目(含む)までの総和(1-indexed)
        return self.sum_1_to_i(j)-self.sum_1_to_i(i-1)
    def reset(self): #初期化
        self.bit=[0]*(self.size+1)

def main():
    A='abcdefghijklmnopqrstuvwxyz'
    D=dict()
    for i,a in enumerate(A):
        D[a]=i
    n=int(input())
    S=input().strip()
    L=[BIT(n) for _ in range(26)]
    for i,s in enumerate(S):
        k=D[s]
        L[k].add(i+1,1)
    q=int(input())
    for _ in range(q):
        k,a,b=input().strip().split()
        if k=='1':
            i=int(a)-1
            s=S[i]
            l1=D[s]
            l2=D[b]
            L[l1].add(i+1,-1)
            L[l2].add(i+1,1)
        else:
            l=int(a)
            r=int(b)
            ans=0
            for i in range(26):
                if L[i].sum_i_to_j(l,r)!=0:
                    ans+=1
            print(ans)
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections
import sys
input = sys.stdin.readline
N = int(input())
S = list(input())
Q = int(input())


class segment_tree:
    n = 0
    segtree = []
    max_v = 10**9

    def __init__(self, A, max_n=10**9 + 1):
        N = len(A)
        self.max_v = max_n
        self.n = (N-1).bit_length()
        self.n = 2 ** self.n
        self.segtree = [set() for i in range(2*self.n)]
        for i in range(N):
            self.segtree[self.n+i].add(A[i])
        for i in range(self.n - 1, -1, -1):
            if i == self.n-1:
                self.segtree[i] |= self.segtree[i*2 + 1]
            else:
                self.segtree[i] = self.segtree[i*2 + 1] | self.segtree[i*2 + 2]

    def update(self, i, x):
        id = self.n+i
        while(id >= 0):
            if id >= self.n:
                self.segtree[id] = set(x)
                # print(self.segtree)
            else:
                self.segtree[id] = self.segtree[id *
                                                2 + 1] | self.segtree[id*2 + 2]
                # print(self.segtree[id*2 + 1], self.segtree[id*2+2])
            id = (id - 1) // 2

    def query(self, a, b, k, l, r):
        if r <= a or l >= b:
            return(set())
        if a <= l and r <= b:
            return(self.segtree[k])
        else:
            vl = self.query(a, b, k*2+1, l, (l+r)//2)
            vr = self.query(a, b, k*2+2, (l+r)//2, r)
            return(vl | vr)


ST = segment_tree(S[:-1])

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

    if t == "1":
        a = int(a)
        ST.update(a-1, b)
    elif t == "2":
        a = int(a)
        b = int(b)
        ret = ST.query(a-1, b, 0, 0, N-1)
        # print(ST.segtree)
        print(len(ret))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
q = int(input())
commands = []
for _ in range(q):
    com, x, y = input().split()
    commands.append((com, int(x), y))

size = 1
while size <= n:
    size *= 2

# initialize
segment_tree = [set() for _ in range(2 * size - 1)]

def update(i, x, segment_tree):
    i += size - 1
    segment_tree[i] = set(x)
    while i > 0:
        i = (i - 1) // 2
        left = segment_tree[i * 2 + 1]
        right = segment_tree[i * 2 + 2]
        segment_tree[i] = left | right

def getSum(s, t, k, l, r, segment_tree):
    if r <= s or t <= l:
        return set()
    if s <= l and r <= t:
        return segment_tree[k]
    else:
        ask_left = getSum(s, t, k * 2 + 1, l, (l + r) // 2, segment_tree)
        ask_right = getSum(s, t, k * 2 + 2, (l + r) // 2, r, segment_tree)
        return ask_left | ask_right

for i in range(n):
    update(i, s[i], segment_tree)

for com, x, y in commands:
    if com == '1':
        update(x, y, segment_tree)
    else:
        result = getSum(x - 1, int(y), 0, 0, size, segment_tree)
        print(len(result))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left,bisect_right,insort
N = int(input())
S = input()
Q = int(input())
D = dict()
D2 = dict()# to be removed
D3 = dict()# to be added
for i in range(97,97+26):
    D[chr(i)] = []
    D2[chr(i)] = []
    D3[chr(i)] = []
for i in range(N):
    D[S[i]].append(i+1)
for i in range(Q):
    t,l,r = input().split()
    if t == str(1):
        k = int(l)
        c = r
        if S[k-1] == c:
            continue
        #delete
        if bisect_right(D2[S[k-1]],k)-bisect_left(D2[S[k-1]],k) == 0:
            insort(D2[S[k-1]],k)
        if bisect_right(D3[S[k-1]],k) - bisect_left(D3[S[k-1]],k) == 1:
            del D3[S[k-1]][bisect_left(D3[S[k-1]],k)]
        #add
        if bisect_right(D3[c],k)-bisect_left(D3[c],k) == 0:
            insort(D3[c],k)
        if bisect_right(D2[c],k)-bisect_left(D2[c],k) == 1:
            del D2[c][bisect_left(D2[c],k)]
        continue
    l = int(l)
    r = int(r)
    ans = 0
    for i in range(97,97+26):
        X = D[chr(i)]
        X2 = D2[chr(i)]
        X3 = D3[chr(i)]
        if bisect_right(X,r)-bisect_left(X,l) + bisect_right(X3,r)- bisect_left(X3,l) -bisect_right(X2,r)+bisect_left(X2,l)> 0:
            ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

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

res = []
def str_to_list(s):
    return [x for x in s]

S = str_to_list(S)
print(S)
for i in range(Q):
    qtype, a, b = input().split()
    if qtype == '1':
        a = int(a)
        S[a-1] = b
    elif qtype == '2':
        a = int(a)
        b = int(b)
        c = S[a-1:b]
        res.append(len(set(c)))

for r in res:
    print(r)

Submission status: Wrong Answer

Solution code:
import bisect
import sys

input = sys.stdin.readline
num2alpha = lambda c: chr(c + 97)
alpha2num = lambda c: ord(c) - ord("a")


class SegTreeMax:
    def __init__(self, l):
        self.N = 1
        while self.N < len(l):
            self.N *= 2
        self.L = [0 for _ in range(self.N * 2 - 1)]
        for i in range(len(l)):
            self.L[i + self.N - 1] = l[i]
        for i in range(self.N - 2, -1, -1):
            self.L[i] = max(self.L[i * 2 + 1], self.L[i * 2 + 2])

    def update(self, k, v):
        k += self.N - 1
        self.L[k] = v
        while k > 0 and self.L[(k - 1) // 2] < v:
            k = (k - 1) // 2
            self.L[k] = v

    def query(self, a, b):
        return self.inquiry(0, self.N, 0, a, b)

    def inquiry(self, l, r, k, a, b):
        if r <= a or l >= b:
            return 0
        if a <= l and b >= r:
            return self.L[k]
        vl = self.inquiry(l, (l + r) // 2, k * 2 + 1, a, b)
        if vl == 1:
            return 1
        vr = self.inquiry((l + r) // 2, r, k * 2 + 2, a, b)
        if vr == 1:
            return 1
        return 0


def main():
    N = int(input())
    Stri = input()
    L = []
    for c in Stri:
        L.append(c)
    Q = int(input())
    l0 = [0 for _ in range(N)]
    S = [SegTreeMax(l0) for _ in range(26)]
    for i in range(N):
        S[alpha2num(L[i])].update(i, 1)

    for _ in range(Q):
        a, b, c = input().split()
        if a == "1":
            i = int(b) - 1
            S[alpha2num(L[i])].update(i, 0)
            L[i] = c
            S[alpha2num(c)].update(i, 1)

        else:
            l = int(b) - 1
            r = int(c)
            res = 0
            for i in range(26):
                if S[i].query(l, r):
                    res += 1
            print(res)


main()

Submission status: Wrong Answer

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

class SegmentTree:
    def __init__(self, n, unit): #example (12, min, 2**31-1)
        for k in range(40):
            if 2**k > n:
                break
        self.powers = pow(2,k)
        self.segTree = [unit]*(2*self.powers)
        self.unit = unit
    
    def update(self, i, x):#i番目(0-indexed)にx代入, segTree = [0,*,*,...], 1-indexed, N < k
        i += self.powers
        self.segTree[i] = x
        while i > 1:
            i //= 2
            self.segTree[i] = self.segTree[i*2] + self.segTree[i*2+1]

    def getCal(self, i, j, k=1, l=0, r=-1): #get self.cal of [i,j)!!!!!
        if r < 0: #initization, we want to r = self.powers as an initial value.
            r = self.powers
        if j <= l or r <= i:
            return self.unit
        if i <= l and r <= j:
            return self.segTree[k]
        return self.getCal(i ,j, k*2, l, (l+r+1)//2) + self.getCal(i ,j, k*2+1, (l+r+1)//2, r)


def main():
    N = int( input())
    S = list( input())
    Q = int( input())
    Query = [ tuple( input().split()) for _ in range(Q)]
    A = [SegmentTree(N, 0) for _ in range(26)]
    a = ord('a')
    for i in range(N):
        A[ord(S[i]) - a].update(i, 1)
    ANS = []
    for t, i, c in Query:
        if t == '1':
            i = int(i)
            A[ord(S[i-1])-a].update(i-1, 0)
            A[ord(c)-a].update(i-1,1)
        else:
            i, c = int(i), int(c)
            ans = 0
            for j in range(26):
                if A[j].getCal(i-1, c) > 0:
                    ans += 1
            ANS.append(ans)
    print('\n'.join( map(str, ANS)))
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import string


def resolve():
    N = int(input())
    S = input()
    Q = int(input())
    for _ in range(Q):
        a, x, y = input().split()
        if a == '1':
            S = S[:int(x)] + y + S[int(x)+1:]
        if a == '2':
            subs = S[int(x)-1:int(y)]
            flag = {s: False for s in string.ascii_lowercase}
            for s in subs:
                flag[s] = True
            ans = 0
            for s in flag:
                if flag[s]:
                    ans += 1
            print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
Q = int(input())
lis = [[0]*26 for _ in range(N+1)]
for i,s in enumerate(S):
  k = ord(s)-97
  lis[i+1]=lis[i].copy()
  lis[i+1][k]+=1
  
for _ in range(Q):
  a,b,c = input().split()
  a = int(a)
  b = int(b)
  if a==1:
    x = S[b-1]
    x = ord(x)-97
    y = ord(c)-97
    for i in range(b,N+1):
      lis[i][x]-=1
      lis[i][y]+=1
  elif a==2:
    c = int(c)
    ans = 0
    for i,j in zip(lis[b-1],lis[c]):
      if j-i>0:
        ans+=1
    print(ans)

Submission status: Wrong Answer

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

# int = int(input())
# s = input().split()
# i = list(map(int, input().split()))
# s = [input() for i in range(3)]

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


for i in range(q):
    x, y, z = input().split()
    if x == "1":
        if s[int(y):int(y)+1] != z:
            s = s[:int(y)-1] + z + s[int(y):]
    else:
        print(len(list(set(s[int(y)-1:int(z)]))))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(str(input()))
num = [[] for i in range(26)]
for i in range(n):
  num[ord(s[i])-ord("a")].append(i+1)
q = int(input())
for _ in range(q):
  nn,a,b = map(str,input().split())
  if nn == "1":
    a = int(a)-1
    num[ord(s[a])-ord("a")].remove(a+1)
    num[ord(b)-ord("a")].append(a+1)
    num[ord(b)-ord("a")].sort()
    s[a] = b
  #    print(s)
  #    print(num)
  else:
  #    print(num)
    ans = 0
    for i in range(26):
      if num[i] != []:
        if int(a) <= num[i][-1] and num[i][0] <= int(b):
          low1 = 0
          high1 = len(num[i])
          while low1+1 < high1:
            mid = (low1+high1)//2
            if int(a) <= num[i][mid]:
              high1 = mid
            else:
              low1 = mid
          low2 = 0
          high2 = len(num[i])
          while low2+1 < high2:
            mid = (low2+high2)//2
            if num[i][mid] <= int(b):
              low2 = mid
            else:
              high2 = mid
  #          print(i,"!!")
  #          print(low1,high1,low2,high2)
          if low1 <= high2:
            ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
sl = list(input())
q = int(input())


# Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
        self.el = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, x):
        assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


dic = defaultdict(lambda: BIT(n))
ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
for idx, s in enumerate(sl):
    dic[s].add(idx+1, 1)
for _ in range(q):
    a, b, c = map(str, input().split())
    if a == "1":
        b = int(b)
        dic[sl[b-1]].add(b, -1)
        dic[c].add(b, 1)
    else:
        b = int(b)
        c = int(c)
        ans = 0
        for s in ascii_lowercase:
            if dic[s].get(b-1, c) > 0:
                ans += 1
        print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
ls = list(s)
q = int(input())
query = [input().split() for _ in range(q)]
for t, i, j  in query:
    if t == '1':
        if ls[int(i)-1] != j:
            ls[int(i)-1] = j
            s = ''.join(ls)
            #print(s)
    else: print(len(set(ls[int(i)-1:int(i)-1+int(j)])))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
class SegmentTree():
    def __init__(self,size,unit,f):
        self.size=size
        self.data=[unit for _ in range(2*size)]
        self.unit=unit
        self.f=f
    def update(self,i,x):
        c=self.data
        f=self.f
        i+=self.size
        c[i]=x
        while i>1:
            i//=2
            c[i]=f(c[i*2],c[i*2+1])
    def add(self,i,x):
        c=self.data
        f=self.f
        i+=self.size
        c[i]=f(c[i],x)
        while i>1:
            i//=2
            c[i]=f(c[i*2],c[i*2+1])
    def query(self,l,r):
        c=self.data
        f=self.f
        x=self.unit
        y=self.unit
        l+=self.size
        r+=self.size
        while l<r:
            if l%2:
                x=f(x,c[l])
                l+=1
            if r%2:
                r-=1
                y=f(c[r],y)
            l//=2
            r//=2
        return f(x,y)
def main():
    N = int( input())
    S = list( input())
    Q = int( input())
    Query = [ tuple( input().split()) for _ in range(Q)]
    for i in range(40):
        if N < pow(2,i):
            n = pow(2,i)
            break
    A = [SegmentTree(n, 0, lambda a,b : a+b) for _ in range(26)]
    a = ord('a')
    for i in range(N):
        A[ord(S[i]) - a].update(i, 1)
    ANS = []
    for t, i, c in Query:
        if t == '1':
            i = int(i)
            A[ord(S[i-1])-a].update(i-1, 0)
            A[ord(c)-a].update(i-1,1)
        else:
            i, c = int(i), int(c)
            ans = 0
            for j in range(26):
                if A[j].query(i-1, c) > 0:
                    ans += 1
            ANS.append(ans)
    print('\n'.join( map(str, ANS)))

if __name__ == '__main__':
    main()

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)
        f[s[int(i)-1]].sort()
        alpha[c].append(int(i)-1)
        alpha[c].sort()
    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,L,R)
        print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
s = str(input())
Q = int(input())

def search(s,i,r):
  ans = 0
  vote = [0]*26
  for k in range(int(i)-1,int(r)):
    c = ord(s[k]) - 97
    vote[c] += 1
  for row in vote:
    if row != 0:
      ans += 1
  return ans

for i in range(Q):
  A,B,C = map(str,input().split())
  if int(A) == 1:
    s = s[:int(B)] + C + s[int(B)+1:]
  elif int(A) == 2:
    print(search(s,B,C))

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
S = input()
Q = int(input())
querys = [list(map(str, input().split())) for i in range(Q)]
for i in range(Q):
    if querys[i][0] == "1":
        S = S[:int(querys[0][1])-1] + querys[i][2] + S[int(querys[0][1]):]
    else:
        c = collections.Counter(S[int(querys[i][1]) - 1:int(querys[i][2])])
        print(len(c))

Submission status: Wrong Answer

Solution code:
import bisect
import sys

input = sys.stdin.readline
num2alpha = lambda c: chr(c + 97)
alpha2num = lambda c: ord(c) - ord("a")


class SegTreeMax:
    def __init__(self, l):
        self.N = 1
        while self.N < len(l):
            self.N *= 2
        self.L = [0 for _ in range(self.N * 2 - 1)]
        for i in range(len(l)):
            self.L[i + self.N - 1] = l[i]
        for i in range(self.N - 2, -1, -1):
            self.L[i] = max(self.L[i * 2 + 1], self.L[i * 2 + 2])

    def update(self, k, v):
        k += self.N - 1
        self.L[k] = v
        while k > 0 and self.L[(k - 1) // 2] < v:
            k = (k - 1) // 2
            self.L[k] = v

    def query(self, a, b):
        return self.inquiry(0, self.N, 0, a, b)

    def inquiry(self, l, r, k, a, b):
        if r <= a or l >= b:
            return 0
        if a <= l and b >= r:
            return self.L[k]
        vl = self.inquiry(l, (l + r) // 2, k * 2 + 1, a, b)
        vr = self.inquiry((l + r) // 2, r, k * 2 + 2, a, b)
        return max(vl, vr)


N = int(input())
Stri = input()
L = []
for c in Stri:
    L.append(c)
Q = int(input())
l0 = [0 for _ in range(N)]
S = [SegTreeMax(l0) for _ in range(26)]
for i in range(N):
    S[alpha2num(L[i])].update(i, 1)

for _ in range(Q):
    a, b, c = input().split()
    if a == "1":
        i = int(b) - 1
        S[alpha2num(L[i])].update(i, 0)
        L[i] = c
        S[alpha2num(c)].update(i, 1)

    else:
        l = int(b) - 1
        r = int(c)
        res = 0
        for i in range(26):
            if S[i].query(l, r):
                res += 1
        print(res)

Submission status: Wrong Answer

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

class segtree:
  def __init__(self, initArr, segfunc, idele):
    n = len(initArr)
    stn = 2**((n - 1).bit_length() + 1) - 1
    arr =  [idele for i in range(stn)]
    arr[-n:] = initArr
    for i in range(stn-1, 1, -2):
      arr[(i-1)//2] = segfunc(arr[i-1], arr[i])
  
    self.arr = arr
    self.segfunc = segfunc
    self.idele = idele
  
  def update(self, idx, val):
    idx += len(self.arr)//2
    self.arr[idx] = val
    while idx > 0:
      idx = (idx-1)//2
      self.arr[idx] = self.segfunc(self.arr[idx*2+1], self.arr[idx*2+2])
    return None

  def query(self, x, y, i=0, l=0, r=-1):
    if r < 0: r = len(self.arr)//2 + 1
    if r <= x or y <= l: return self.idele
    if x <= l and r <= y: return self.arr[i]
    return self.segfunc(
      self.query(x, y, 2*i+1, l, (l+r)//2),
      self.query(x, y, 2*i+2, (l+r)//2, r)
    )

st = segtree(list(map(set, S)), lambda a, b: a | b, set())

for q, *p in query:
  if q == "1":
    i, r = p
    st.update(int(i), set(r))
  else:
    l, r = map(int, p)
    print(len(st.query(l-1, r+1)))