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 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),key[ord(y)-kijun])
    else:
        print(judge(query(int(x)-1,int(y))))

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
        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
        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 = sys.stdin.readline
N = int(input())
S = input().rstrip()
Q = int(input())
qs = [input().split() for i in range(Q)]

def ctoi(c):
    return ord(c) - ord('a')

bit = [[0]*(N+2) for _ in range(26)]
def bit_add(x,w,ci):
    while x <= N+1:
        bit[ci][x] += w
        x += (x & -x)
def bit_sum(x,ci):
    ret = 0
    while x > 0:
        ret += bit[ci][x]
        x -= (x & -x)
    return ret

for i,c in enumerate(S):
    bit_add(i+1,1,ctoi(c))

s = list(S)
ans = []
for a,b,c in qs:
    if a=='1':
        x = int(b)
        bit_add(x,1,ctoi(c))
        bit_add(x,-1, ctoi(s[x-1]))
    else:
        tmp = 0
        for i in range(26):
            if bit_sum(int(c),i) - bit_sum(int(b)-1,i) > 0:
                tmp += 1
        ans.append(tmp)
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
from math import ceil, log

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, 0, sum) for _ in range(26)]
for i in range(N):
    letter = abc[S[i]]
    segs[letter].update(i, 1)

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

Submission status: Wrong Answer

Solution code:
n=int(input())
ss=input()
dps=['a']*n
from collections import defaultdict
d=defaultdict(list)
for i in range(n):
    d[ss[i]].append(i)
    dps[i]=ss[i]
sorted(d.items())

Q=int(input())
import bisect
for i in range(Q):
    num,ii,c=input().split()
    #print(d)
    if num=='1':
        if c==dps[int(ii)-1]:
            continue
        d[c].append(int(ii)-1)
        d[dps[int(ii)-1]].remove(int(ii)-1)
        dps[int(ii)-1]=c
    else:
        l,r=int(ii)-1,int(c)-1
        count=0
        for k,lst in d.items():
            idx=bisect.bisect_left(lst,l)
            idx1=bisect.bisect_right(lst,r)
            count+=((idx1-idx)>0)
            #print(lst,l,r,count)
        print(count)
        pass

Submission status: Wrong Answer

Solution code:
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
import bisect
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**21


class Segtree_op():
    def __init__(self, n):
        self.size = 1
        while (n >= 1):
            self.size = self.size << 1
            n = n // 2

        self.arr = [self.unit() for i in range(self.size * 2)]

    def op(self, lch, rch):
        # sum
        return lch + rch
        # update min with holding index
        # if lch[0] <= rch[0]:
        #     return lch
        # else:
        #     return rch

    def unit(self):
        return 0

    def update(self, k, val):
        k += self.size - 1
        self.arr[k] = val
        while (k):
            k = (k - 1) // 2
            self.arr[k] = self.op(self.arr[k * 2 + 1], self.arr[k * 2 + 2])

    def query(self, l, r):
        L = l + self.size
        R = r + self.size
        s = self.unit()
        while L < R:
            # print(R)
            if R & 1:
                R -= 1
                s = self.op(s, self.arr[R - 1])

            if L & 1:
                s = self.op(s, self.arr[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def show(self):
        idx = 1
        while (idx <= self.size):
            print(self.arr[idx - 1:idx * 2 - 1])
            idx *= 2


def main():
    n = getN()
    s = input().strip()
    q = getN()
    segs = [Segtree_op(n) for i in range(26)]
    for i,c in enumerate(s):
        segs[ord(c) - ord("a")].update(i, 1)
    # print(segs[1].arr)
    # print(segs[1].size)
    queries = []
    for query in range(q):
        num, a, b = input().split()
        if num == "1":
            a = int(a)
            segs[ord(s[a-1]) - ord("a")].update(a-1, 0)
            segs[ord(b) - ord("a")].update(a - 1, 1)
        else:
            tmp = 0
            a, b = int(a)-1 , int(b)-1
            for se in segs:
                # print(se.arr)
                if se.query(a, b+1) > 0:
                    tmp += 1
            print(tmp)



if __name__ == '__main__':
    main()

"""
7 
aaaabbb
3
1 7 c
2 1 5
2 1 7
"""

Submission status: Wrong Answer

Solution code:
n=int(input())
S=input()
q=int(input())

D=[[0]*26 for _ in range(n+1)]
for i,s in enumerate(S):
  for j in range(26):
    if j==ord(s)-97:
      D[i+1][j]=D[i][j]+1
    else:
      D[i+1][j]=D[i][j]

n_max=n+1
nn=n_max.bit_length()+1
BITS=[[0]*(2**nn) for _ in range(26)]
for i in range(26):
  BITS[i].insert(0,0)

def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT

for _ in range(q):
  q1,q2,q3=map(str,input().split())
  if q1=="1":
    num=int(q2)-1
    prev=ord(S[num])-97
    new=ord(q3)-97
    if prev!=new:
      bitadd(BITS[prev],num+1,-1)
      bitadd(BITS[new],num+1,1)
  else:
    l,r=int(q2),int(q3)
    ans=0
    for i in range(26):
      diff=D[r][i]-D[l-1][i]+bitsum(BITS[i],r)-bitsum(BITS[i],l-1)
      if diff:
        ans+=1
    print(ans)

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
        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),key[ord(y)-kijun])
    else:
        print(judge(query(int(x)-1,int(y))))

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
        #delete
        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
        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:
n=int(input())
ss=input()
dps=['a']*n
from collections import defaultdict
d=defaultdict(list)
for i in range(n):
    d[ss[i]].append(i)
    dps[i]=ss[i]
sorted(d.items())

Q=int(input())
import bisect
for i in range(Q):
    num,ii,c=input().split()
    #print(d)
    if num=='1':
        d[c].append(int(ii)-1)
        d[dps[int(ii)-1]].remove(int(ii)-1)
        dps[int(ii)-1]=c
    else:
        l,r=int(ii)-1,int(c)-1
        count=0
        for k,lst in d.items():
            idx=bisect.bisect_left(lst,l)
            idx1=bisect.bisect_right(lst,r)
            count+=((idx1-idx)>0)
            #print(lst,l,r,count)
        print(count)
        pass

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_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 i in range(1, N + 1):
#    print(bit[i])
  
for x, y, z in query:
    if x == "1":
        bit_add(int(y), z)
    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)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
S = input().rstrip()
Q = int(input())
qs = [input().split() for i in range(Q)]

def ctoi(c):
    return ord(c) - ord('a')

bit = [[0]*(N+2) for _ in range(26)]
def bit_add(x,ci):
    while x <= N+1:
        bit[ci][x] += 1
        x += (x & -x)
def bit_sum(x,ci):
    ret = 0
    while x > 0:
        ret += bit[ci][x]
        x -= (x & -x)
    return ret

for i,c in enumerate(S):
    bit_add(i+1,ctoi(c))

ans = []
for a,b,c in qs:
    if a=='1':
        bit_add(int(b),ctoi(c))
    else:
        tmp = 0
        for i in range(26):
            if bit_sum(int(c),i) - bit_sum(int(b)-1,i) > 0:
                tmp += 1
        ans.append(tmp)
print(*ans, sep='\n')

Submission status: Wrong Answer

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

def type1(S,i,c):
  S_replace = c
  S = S[:i]+S_replace+S[i+1:]
  return S

def type2(S,l,r):
  l-=1
  ret = len(set(S[l:r]))
  print(ret)

for i in range(Q):
  a,b,c = input().split()
  if a == '1':
    b = int(b)
    S = type1(S,b,c)
  elif a == '2':
    b,c = int(b),int(c)
    type2(S,b,c)

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]
        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:
n = int(input())
s = list(input())
q = int(input())
for i in range(q):  
  a,b,c = map(str,input().split())
  b = int(b)
  if a=='2':
    c = int(c)
    print(len(set(s[b-1:b+c-1])))
  else:
    s[b-1] = c

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
q = int(input())
for i in range(q):
    typ, a, b = input().split()
    if typ=='1':
        s=s[:int(a)]+b+s[int(a)+1:]
    if typ=='2':
        print(len(set(s[int(a)-1:int(b)])))

Submission status: Wrong Answer

Solution code:
import sys

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

class BitSum:
    def __init__(self, n):
        self.n = n + 3
        self.table = [0] * (self.n + 1)

    def add(self, i, x):
        i += 1
        while i <= self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

def main():
    n=II()
    bits=[BitSum(n) for _ in range(26)]
    s=list(SI())
    a=ord("a")
    for i,c in enumerate(s):
        code=ord(c)-a
        bits[code].add(i,1)
    q=II()
    for _ in range(q):
        op,x,y=input().split()
        if op=="1":
            i=int(x)-1
            now=s[i]
            s[i]=c
            bits[ord(now)-a].add(i,-1)
            bits[ord(y)-a].add(i,1)
        else:
            l,r=int(x)-2,int(y)-1
            print(sum(bits[i].sum(r)-bits[i].sum(l)>0 for i in range(26)))


main()

Submission status: Wrong Answer

Solution code:
class segtree:

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

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

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

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

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

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

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

identity = set("!")
def num_kinds(a,b):
    return  a | b

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

tree = segtree(n,num_kinds,identity)

for i in range(n):
    tree.update(i, set([s[i]]))

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

    if ty == "1":
        i = int(i)
        tree.update(i-1,set([c]))
    else:
        i = int(i)
        c = int(c)
        i-=1
        c-=1
        print(len(tree.get(i,c))-1)

Submission status: Wrong Answer

Solution code:
import sys

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

class BitSum:
    def __init__(self, n):
        self.n = n + 3
        self.table = [0] * (self.n + 1)

    def add(self, i, x):
        i += 1
        while i <= self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

def main():
    n=II()
    bits=[BitSum(n) for _ in range(26)]
    s=list(SI())
    a=ord("a")
    for i,c in enumerate(s):
        code=ord(c)-a
        bits[code].add(i,1)
    q=II()
    for _ in range(q):
        op,x,y=input().split()
        if op=="1":
            i=int(x)-1
            now=s[i]
            s[i]=c
            bits[ord(now)-a].add(i,-1)
            bits[ord(y)-a].add(i,1)
        else:
            l,r=int(x)-2,int(y)-1
            print(sum(bits[i].sum(r)-bits[i].sum(l)>0 for i in range(26)))

main()

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
q=int(input())
bit=[[0]*(n+1) for _ in range(26)]
#print(bit)
def upd(at,by,char):
  while at<=n:
    bit[char][at]+=by
    at+=at&-at
def qry(at,char):
  ret=0
  while at>0:
    #print(at,char,end=" inside \n")
    ret+=bit[char][at]
    at-=at&-at
  return ret
for i in range(n):
  upd(i+1,1,ord(s[i])-ord('a'))
for _ in range(q):
  t,l,r=input().split()
  t=int(t)
  if t==1:
    # print(t,l,r,end=" inside if")
    i=int(l)
    cq=r
    prev=ord(s[i-1])-ord('a')
    upd(i,-1,prev)
    curr=ord(cq)-ord('a')
    upd(i,1,curr)
    #change ith character to cq  
  else:
    #    print(t,l,r,end=" inside else")
    l=int(l)
    r=int(r)
    ans=0
    for i in range(26):
      if qry(r,i)-qry(l-1,i)>0:
        ans+=1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
import bisect
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**21


class Segtree_op():
    def __init__(self, n):
        self.size = 1
        while (n >= 1):
            self.size = self.size << 1
            n = n // 2

        self.arr = [self.unit() for i in range(self.size * 2)]

    def op(self, lch, rch):
        # sum
        return lch + rch
        # update min with holding index
        # if lch[0] <= rch[0]:
        #     return lch
        # else:
        #     return rch

    def unit(self):
        return 0

    def update(self, k, val):
        k += self.size - 1
        self.arr[k] = val
        while (k):
            k = (k - 1) // 2
            self.arr[k] = self.op(self.arr[k * 2 + 1], self.arr[k * 2 + 2])

    def query(self, l, r):
        L = l + self.size
        R = r + self.size
        s = self.unit()
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s, self.arr[R - 1])

            if L & 1:
                s = self.op(s, self.arr[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def show(self):
        idx = 1
        while (idx <= self.size):
            print(self.arr[idx - 1:idx * 2 - 1])
            idx *= 2


def main():
    n = getN()
    s = input().strip()
    q = getN()
    segs = [Segtree_op(n) for i in range(26)]
    for i,c in enumerate(s):
        segs[ord(c) - ord("a")].update(i, 1)
    # print(segs[1].arr)
    queries = []
    for query in range(q):
        num, a, b = input().split()
        if num == "1":
            a = int(a)
            segs[ord(s[a-1]) - ord("a")].update(a-1, 0)
            segs[ord(b) - ord("a")].update(a - 1, 1)
        else:
            tmp = 0
            a, b = int(a)-1 , int(b)-1
            for se in segs:
                # print(se.arr)
                if se.query(a, b+1) > 0:
                    tmp += 1
            print(tmp)



if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

prev_l, prev_r = None, None
prev_count = -1

for _ in range(Q):
    tp, l, r = input().split()
    # print(S)
    if int(tp) == 2:
        l = int(l)
        r = int(r)
        if prev_l is None or prev_r is None:
            c = Counter(S[l-1:r])
            prev_l, prev_r = l, r
            prev_count = c
            print(len(c))
        elif l >= prev_l and r <= prev_r:
            print(prev_count)
        else:
            c = Counter(S[l-1:r])
            prev_l, prev_r = l, r
            prev_count = c
            print(len(c))
    else:
        l = int(l)
        S = S[:l - 1] + r + S[l:]

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

class SegTree:
    def __init__(self, N):
        self.N = N
        self._N = 1<<((N-1).bit_length())
        self.node = [0]*2*self._N

    def build(self,lis):
        for i in range(self.N):
            self.node[i+self._N-1] = lis[i]
        for i in range(self._N-2,-1,-1):
            self.node[i] = self.node[i*2+1] | self.node[i*2+2]
        return

    def update(self,i,x):
        i += self._N-1
        self.node[i] = x
        while i:
            i >>= 1
            self.node[i] = self.node[i*2+1] | self.node[i*2+2]

    def query(self,p,q,idx=0,a=0,b=None):
        if b is None:
            b = self._N
        if q <= p or b <= p or q <= a:
            return 0
        elif p <= a and b <= q:
            return self.node[idx]
        else:
            res1 = self.query(p,q,idx*2+1,a,(a+b)//2)
            res2 = self.query(p,q,idx*2+2,(a+b)//2,b)
            return res1 | res2

n = ni()
oa = ord('a')
conv = lambda x: 1<<(ord(x)-oa) 
s = list(map(conv, list(input())))
q = ni()
S = SegTree(n)
S.build(s)
for _ in range(q):
    x,y,z = input().split()
    if x == '1':
        y = int(y)
        S.update(y-1, conv(z))
    else:
        y = int(y)
        z = int(z)
        # print(S.node[S._N-1:], y, z)
        v = S.query(y-1,z)
        # print(v)
        print(str(bin(v)).count('1'))

Submission status: Wrong Answer

Solution code:
n=int(input())
S=input()
q=int(input())

D=[[0]*26 for _ in range(n+1)]
for i,s in enumerate(S):
  for j in range(26):
    if j==ord(s)-97:
      D[i+1][j]=D[i][j]+1
    else:
      D[i+1][j]=D[i][j]

n_max=5*10**5
nn=n_max.bit_length()+1
BITS=[[0]*(2**nn) for _ in range(26)]
for i in range(26):
  BITS[i].insert(0,0)

def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT

for _ in range(q):
  q1,q2,q3=map(str,input().split())
  if q1=="1":
    num=int(q2)-1
    prev=ord(S[num])-97
    new=ord(q3)-97
    bitadd(BITS[prev],num+1,-1)
    bitadd(BITS[new],num+1,1)
  else:
    l,r=int(q2),int(q3)
    ans=0
    for i in range(26):
      diff=D[r][i]-D[l-1][i]+bitsum(BITS[i],r)-bitsum(BITS[i],l-1)
      if diff:
        ans+=1
    print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
    import sys
    input = sys.stdin.readline

    numChar = 26
    #numChar = 5
    ordA = ord('a')

    N = int(input())
    Ss = input()
    nos = [ord(S)-ordA for S in Ss]
    Q = int(input())

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        datas = [[0]*(numPow2+1) for _ in range(numChar)]
        return datas, numPow2
    def addValue(no, iA, A):
        data = datas[no]
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(no, iA):
        data = datas[no]
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans
    def getRangeSum(no, iFr, iTo):
        return getSum(no, iTo) - getSum(no, iFr-1)


    datas, numPow2 = makeBIT(N)

    for i in range(N):
        no = nos[i]
        addValue(no, i, 1)

    anss = []
    for _ in range(Q):
        tp, v1, v2 = input().split()
        if tp == '1':
            pos = int(v1)-1
            no1 = nos[pos]
            no2 = ord(v2)-ordA
            addValue(no1, pos, -1)
            addValue(no2, pos, 1)
        else:
            L, R = int(v1)-1, int(v2)-1
            ans = 0
            for no in range(numChar):
                if getRangeSum(no, L, R):
                    ans += 1
            anss.append(ans)

    print('\n'.join(map(str, anss)))


solve()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left,bisect_right,insort
N = int(input())
S = input()
Q = int(input())
C = [0]
X = set()
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
        insort(D2[S[k-1]],k)
        insort(D3[c],k)
        #D2[S[k-1]].append(k)
        #D3[c].append(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)