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:
# ABC157e


#print(bin(toBitSet([1, 2, 3, 2])))

# for i in range(97, 123):
#    print(chr(i))


def main():
    import sys
    sys.setrecursionlimit(10**6)
    # 再帰関数を使わない限りPypyで出すこと

    class SegmentTree:
        #####単位元######
        ide_ele = 10**12

        # num:n以上の最小の2のべき乗

        def segfunc(self, x, y):
            return min(x, y)  # 例としてmin関数を設定

        def __init__(self, n):
            super().__init__()
            self.num = 2**(n-1).bit_length()  # nは元々の配列の長さ
            self.seg = [self.ide_ele]*(2*self.num+1)

        def init(self, init_val):  # セグ木にしたい配列を渡す
            # set_val
            for i in range(len(init_val)):
                self.seg[i+self.num-1] = init_val[i]
            # built
            for i in range(self.num-2, -1, -1):
                self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])

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

        def query(self, p, q):
            if q <= p:
                return ide_ele
            p += self.num-1
            q += self.num-2
            res = self.ide_ele
            while q-p > 1:
                if p & 1 == 0:
                    res = self.segfunc(res, self.seg[p])
                if q & 1 == 1:
                    res = self.segfunc(res, self.seg[q])
                    q -= 1
                p = p//2
                q = (q-1)//2
            if p == q:
                res = self.segfunc(res, self.seg[p])
            else:
                res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
            return res

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

    def toBitSet(numberSet):
        theSet = 0
        for i in numberSet:
            theSet = theSet | 1 << i
        return theSet

    def alphabetToZeroIndexed(alphabet):
        return ord(alphabet) - 97

    tree = SegmentTree(n)

    for i in range(n):
        tree.update(i+1, toBitSet([alphabetToZeroIndexed(s[i])]))

    for _ in range(q):
        a, b, c = input().split()
        b = int(b)
        if int(a) == 1:
            tree.update(b, toBitSet([alphabetToZeroIndexed(c)]))
        else:
            c = int(c)
            print(bin(tree.query(b, c+1)).count('1'))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

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

def query(p,q,c):
  if q<=p:
    return ide_ele
  p+=num-1
  q+=num-2
  res=ide_ele
  while q-p>1:
    if p&1==0:
      res=segfunc(res,seg[c][p])
    if q&1==1:
      res=segfunc(res,seg[c][q])
      q-=1
    p=p//2
    q=(q-1)//2
  if p==q:
    res=segfunc(res,seg[c][p])
  else:
    res=segfunc(segfunc(res,seg[c][p]),seg[c][q])
  return res

ide_ele=0

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

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
import copy
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

n=int(input())
s=input()
q=int(input())
qlst=[list(input().split()) for i in range(q)]

lst=[0]*n

for i in range(n):
    lst[i] = pow(2,(ord(s[i])-ord("a")))

print(lst)
#####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 = 0
 
#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num #単位元の配列(計算結果に影響を及ぼさない配列)を作成
 
init(lst)
 
def judge(u):
    res = 0
    for i in range(27):
        if u>>i & 1:
            res += 1
    return res
 
for i in range(q):
    t,x,y = qlst[i]
    if t == "1":
        update(int(x)-1,pow(2,ord(y)-ord("a")))
    else:
        print(judge(query(int(x)-1,int(y))))

Submission status: Wrong Answer

Solution code:
# coding: UTF-8
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    class BIT():
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s
    
    N=int(input())
    S=list(input())
    Q=int(input())
    bit=[BIT(N) for _ in range(26)]
    
    S2=[0]*N
    
    for i in range(N):
        S2[i]=ord(S[i])-ord('a')
    
    for i,x in enumerate(S2):
        bit[x].add(i,1)
    
    for _ in range(Q):
        a,b,c=input().split()
        if a=='1':
            b=int(b)-1
            c=ord(c)-ord('a')
            bit[c].add(b,1)
            bit[S2[b]].add(b,-1)
        else:
            b=int(b)-1
            c=int(c)-1
            ans=0
            for i in range(26):
                if bit[i].sum(c)-bit[i].sum(b-1):
                    ans+=1
            print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
N = int(input())
S = list(input())
Q = int(input())
alpha = "abcdefghijklmnopqrstuvwxyz"
d = dict()

for x in alpha:
    d[x] = ord(x) - 97


class segment_tree:
    n = 0
    segtree = []

    def __init__(self, A):
        N = len(A)
        self.n = (N-1).bit_length()
        self.n = 1 << self.n
        self.segtree = [0 for i in range(2*self.n)]
        for i in range(N):
            self.segtree[self.n+i-1] = 1 << d[A[i]]
        for i in range(self.n - 2, -1, -1):
            self.segtree[i] = self.segtree[i*2 + 1] | self.segtree[i*2 + 2]

    def update(self, i, x):
        id = self.n+i - 1
        while(id >= 0):
            if id >= self.n:
                self.segtree[id] = 1 << d[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(0)
        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)


def popcount(x):
    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
    x = x + (x >> 8)  # 16bitごと
    x = x + (x >> 16)  # 32bitごと
    x = x + (x >> 32)  # 64bitごと = 全部の合計
    return x & 0x0000007f


ST = segment_tree(S[:-1])
N = (N-1).bit_length()
N = 1 << N

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

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

Submission status: Wrong Answer

Solution code:
import sys


class SegTreeSet:
    """
    bitフラグで集合を管理するセグメント木

    要素の種類数は特に明示的に与える必要は無いが、まぁ常識の範囲内で
    """

    def __init__(self, n, initial=0):
        """
        :param n: 文字列長
        :param initial: 初期値
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [initial] * (n2 << 1)
        self.initial = initial

    def update(self, i, x):
        """
        i番目の値にxをXOR

        :param i: index(0-indexed)
        :param x: Bit flag for operating bitwise_xor on leaf node
        """
        i += self.offset
        self.tree[i] ^= x
        while i > 1:
            self.tree[i >> 1] = self.tree[i] | self.tree[i ^ 1]
            i >>= 1

    def get_size(self, a, b):
        """
        [a, b)の要素種数を得る

        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.initial

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result |= self.tree[r - 1]
            if l & 1:
                result |= self.tree[l]
                l += 1
            l >>= 1
            r >>= 1

        return bin(result).count('1')


char_mappings = {chr(i + 97): 1 << i for i in range(26)}

n = int(input())
s = input()
s = list(s)
st = SegTreeSet(n)
q = int(input())
ans = []
for line in sys.stdin:
    i, j, k = line.rstrip().split()
    if i == '1':
        j = int(j) - 1
        if s[j] == k:
            continue
        b = char_mappings[k] | char_mappings[s[j]]
        st.update(j, b)
        s[j] = k
    else:
        l = int(j) - 1
        r = int(k)
        ans.append(st.get_size(l, r))
print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)

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

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

sc = iter(open(0).read().split())
ni = lambda: int(next(sc))
ns = lambda: next(sc)
nc = lambda: ord(next(sc)) - ord('a')

N, S, Q = ni(), ns(), ni()

B = [BIT(N) for _ in range(26)]
for i, s in enumerate(S, 1):
    B[ord(s) - ord('a')].add(i, 1)

A = []
for _ in range(Q):
    if ni() == 1:
        i, c = ni(), nc()
        B[c].add(i, 1)
    else:
        l, r = ni(), ni()
        A.append(sum(b.sum(l - 1) < b.sum(r) for b in B))

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

Submission status: Wrong Answer

Solution code:
NN = 19
X = [0] * ((1<<NN+1)-1)
 
def popcount(x):
    x -= (x >> 1) & 0x55555555
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x += x >> 8
    x += x >> 16
    return x & 0x3f

def update(a, x):
    i = (1<<NN) - 1 + a
    X[i] = x
    while True:
        i = (i-1) // 2
        X[i] = X[2*i+1] | X[2*i+2]
        if i == 0:
            break

def rangeor(a, b):
    l = a + (1<<NN)
    r = b + (1<<NN)
    x = 0
    while l < r:
        if l%2:
            x |= X[l-1]
            l += 1
        if r%2:
            r -= 1
            x |= X[r-1]
        l >>= 1
        r >>= 1
    return x

N = int(input())
A = [ord(a) - 97 for a in input()]
for i, a in enumerate(A):
    X[(1<<NN) + i] = 1 << a
for i in range((1<<NN)-1)[::-1]:
    X[i] = X[i*2+1] | X[i*2+2]

Q = int(input())
for _ in range(Q):
    a, b, c = input().rstrip().split()
    if a == "1":
        b = int(b)
        c = ord(c) - 97
        update(b, 1<<c)
    else:
        b, c = int(b), int(c)
        print(popcount(rangeor(b, c+1)))
        print([i for i in range(26) if rangeor(b, c+1)>>i & 1])

Submission status: Wrong Answer

Solution code:
NN = 19
X = [0] * ((1<<NN+1)-1)
 
def popcount(x):
    x -= (x >> 1) & 0x55555555
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x += x >> 8
    x += x >> 16
    return x & 0x3f

def update(a, x):
    i = (1<<NN) - 1 + a
    X[i] = x
    while True:
        i = (i-1) // 2
        X[i] = X[2*i+1] | X[2*i+2]
        if i == 0:
            break

def rangeor(a, b):
    l = a + (1<<NN)
    r = b + (1<<NN)
    x = 0
    while l < r:
        if l%2:
            x |= X[l-1]
            l += 1
        if r%2:
            r -= 1
            x |= X[l-1]
        l >>= 1
        r >>= 1
    return x

N = int(input())
A = [ord(a) - 97 for a in input()]
for i, a in enumerate(A):
    update(i+1, 1<<a)

Q = int(input())
for _ in range(Q):
    a, b, c = input().rstrip().split()
    if a == "1":
        b = int(b)
        c = ord(c) - 97
        update(b, 1<<c)
    else:
        b, c = int(b), int(c)
        print(popcount(rangeor(b, c+1)))

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()
    i = int(i) - 1
    if int(num) == 1:
        if s[int(i)-1] == c:
            continue
        r = br(f[s[i]],i)
        f[s[i]] = f[s[i]][:r] + [i] + f[s[i]][r:]
        r = br(alpha[c],i)
        alpha[c] = alpha[c][:r] + [i] + alpha[c][r:]
        s[i] = c
    else:
        cnt = 0
        c = int(c)-1
        for j in range(26):
            l = bl(alpha[tmp[j]],i)
            r = br(alpha[tmp[j]],c)
            L = bl(f[tmp[j]],i)
            R = br(f[tmp[j]],c)
            if r - l - (R - L) > 0:
                cnt += 1
        print(cnt)

Submission status: Wrong Answer

Solution code:
import collections
import sys
input = sys.stdin.readline
N = int(input())
S = list(input())
Q = int(input())
alpha = "abcdefghijklmnopqrstuvwxyz"
d = dict()

for x in alpha:
    d[x] = ord(x) - 97


class segment_tree:
    n = 0
    segtree = []

    def __init__(self, A):
        N = len(A)
        self.n = (N-1).bit_length()
        self.n = 2 ** self.n
        self.segtree = [0 for i in range(2*self.n)]
        for i in range(N):
            self.segtree[self.n+i] = 1 << d[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] = 1 << d[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(0)
        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)


def popcount(x):
    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
    x = x + (x >> 8)  # 16bitごと
    x = x + (x >> 16)  # 32bitごと
    x = x + (x >> 32)  # 64bitごと = 全部の合計
    return x & 0x0000007f


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)
        print(popcount(ret))

Submission status: Wrong Answer

Solution code:
import collections
import sys
input = sys.stdin.readline
N = int(input())
S = list(input())
Q = int(input())
alpha = "abcdefghijklmnopqrstuvwxyz"
d = dict()

for x in alpha:
    d[x] = ord(x) - 97


class segment_tree:
    n = 0
    segtree = []

    def __init__(self, A):
        N = len(A)
        self.n = (N-1).bit_length()
        self.n = 2 ** self.n
        self.segtree = [0 for i in range(2*self.n)]
        for i in range(N):
            self.segtree[self.n+i] = 1 << d[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] = 1 << d[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(0)
        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)


def popcount(x):
    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
    x = x + (x >> 8)  # 16bitごと
    x = x + (x >> 16)  # 32bitごと
    x = x + (x >> 32)  # 64bitごと = 全部の合計
    return x & 0x0000007f


ST = segment_tree(S[:-1])
print(ord("b") - 97)


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)
        print(popcount(ret))

Submission status: Wrong Answer

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
import copy
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

n=int(input())
s=input()
q=int(input())
query=[list(input().split()) for i in range(q)]

al=[chr(ord('a') + i) for i in range(26)]
lst={}
erase={}
insert={}
for i in range(26):
    lst[al[i]]=[]
    erase[al[i]]=[]
    insert[al[i]]=[]

for i in range(n):
    lst[s[i]].append(i)

# print(lst)

for i in range(q):
    if query[i][0]=="1":
        one,j,c=query[i]
        j=int(j)
        if s[j-1]!=c:
            erase[s[j-1]].append(j-1)
            erase[s[j-1]].sort()

            insert[c].append(j-1)
            insert[c].sort()

    else:
        two,l,r=query[i]
        ans=0
        l=int(l)
        r=int(r)
        for i in range(26):
            tmp=0
            tmp+=bisect.bisect_right(lst[al[i]],r-1)-bisect.bisect_left(lst[al[i]],l-1)
            tmp-=bisect.bisect_right(erase[al[i]],r-1)-bisect.bisect_left(erase[al[i]],l-1)
            tmp+=bisect.bisect_right(insert[al[i]],r-1)-bisect.bisect_left(insert[al[i]],l-1)
            if tmp>0:
                ans+=1
        print(ans)
    # print(erase)
    # print(insert)

Submission status: Wrong Answer

Solution code:
class BIT:
    def __init__(self, n, init=None):
        self.size = n
        if init is None:
            self.bit = [0] * (n + 1) # don't use bit[0]
        else:
            self.bit = [0] + init
            for i in range(1, n):
                self.bit[i + (i & -i)] += self.bit[i]

    def sum(self, i):
        '''
        Calculate bit[1] + ... + bit[i]
        '''
        S = 0
        while i > 0:
            S += self.bit[i]
            i -= i & -i
        return S

    def add(self, i, x):
        '''
        set bit[i] to be bit[i] + x
        '''
        assert i > 0
        while i <= self.size:
            self.bit[i] += x
            i += i & -i

ALPHA = 'abcdefghijklmnopqrstuvwxyz'
N = int(input())
S = list(input())
bits = {al: BIT(N) for al in ALPHA}
for i, s in enumerate(S, 1): bits[s].add(i, 1)
Q = int(input())
for _ in range(Q):
    t, a, b = input().split()
    t = int(t); a = int(a)
    if t == 1:
        if S[a-1] != b:
            bits[S[a-1]].add(a, -1)
            bits[b].add(a, 1)
    else:
        b = int(b)
        ans = 0
        for al in ALPHA:
            bit = bits[al]
            ans += (bit.sum(b) - bit.sum(a-1)) > 0
        print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
import copy
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

n=int(input())
s=input()
q=int(input())
query=[list(input().split()) for i in range(q)]

al=[chr(ord('a') + i) for i in range(26)]
lst={}
erase={}
insert={}
for i in range(26):
    lst[al[i]]=[]
    erase[al[i]]=[]
    insert[al[i]]=[]

for i in range(n):
    lst[s[i]].append(i)

# print(lst)

for i in range(q):
    if query[i][0]=="1":
        one,j,c=query[i]
        j=int(j)

        erase[s[j-1]].append(j-1)
        erase[s[j-1]].sort()

        insert[c].append(j-1)
        insert[c].sort()

    else:
        two,l,r=query[i]
        ans=0
        l=int(l)
        r=int(r)
        for i in range(26):
            tmp=0
            tmp+=bisect.bisect_right(lst[al[i]],r-1)-bisect.bisect_left(lst[al[i]],l-1)
            tmp-=bisect.bisect_right(erase[al[i]],r-1)-bisect.bisect_left(erase[al[i]],l-1)
            tmp+=bisect.bisect_right(insert[al[i]],r-1)-bisect.bisect_left(insert[al[i]],l-1)
            if tmp>0:
                ans+=1
        print(ans)
    # print(erase)
    # print(insert)

Submission status: Wrong Answer

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

alpha = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', \
  'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

def twopowerceil(n):  # return m s.t. m>=n and m=2**p
    for i in range(40):
        m = 2**i
        if m >= n:
            return m
    return -1

#      0
#   1     2
# 3   4  5  6
#       :
# leaf i - n-1+i
# parent   - (i-1)//2
# children - 2*i+1, 2*i+2

def sgtoper(x,y):
    return (x or y)  # min,max,gcd,...

SGTDEFAULT = False # for or ; BIG for min ; ..
  # s.t. sgtoper(x,SGTDEFAULT) = x

# nn = twopowerceil(n)
# tree must be initialized to [SGTDEFAULT]*(2*nn)
def sgtinit(tree,a,n,nn):  # upto N-1, not N
    for i in range(n):
        tree[nn-1+i] = a[i]
    for i in range(nn-2,-1,-1):
        tree[i] = sgtoper(tree[2*i+1], tree[2*i+2])

def sgtget(tree,x,y,nn):
    return sgtgetcore(tree,x,y,0,0,nn)

# x,y: from query  k: suffix at focus l,r: range for k
# right ends (y,r) not included
def sgtgetcore(tree,x,y,k,l,r):
    if r<=x or y<=l:
        return SGTDEFAULT
    if x<=l and r<=y:
        return tree[k]
    vl = sgtgetcore(tree,x,y,2*k+1,l,(l+r)//2)
    vr = sgtgetcore(tree,x,y,2*k+2,(l+r)//2,r)
    return sgtoper(vl, vr)

def sgtupd(tree,i,x,nn):
    k = i+nn-1
    tree[k] = x
    while k>0:
        k = (k-1)//2
        tree[k] = sgtoper(tree[2*k+1], tree[2*k+2])

n = inn()
nn = twopowerceil(n)
tr = {}
for c in alpha:
    tr[c] = [False]*(2*nn)
ss = ins()
s = []
for i in range(n):
    s.append(ss[i])
a = {}
for c in alpha:
    a[c] = [False]*n
for i in range(n):
    a[s[i]][i] = True
for c in alpha:
    sgtinit(tr[c],a[c],n,nn)

#ddprint("tree")
#for c in alpha:
#    ddprint(c)
#    ddprint(tr[c])

q = inn()
for qq in range(q):
    x,y,z = input().split()
    #ddprint(f"x {x} y {y} z {z}")
    if x == '1':
        i = int(y)-1
        c = z
        sgtupd(tr[s[i]], i, False, nn)
        sgtupd(tr[c], i, True, nn)
    else:
        l = int(y)
        r = int(z)
        sm = 0
        for c in alpha:
            v = sgtget(tr[c],l-1,r,nn)
            if v:
                sm += 1
        print(sm)

Submission status: Wrong Answer

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

for i in range(q):
    type,iq,q=map(str,input().split())
    '''
    if type == "1":
        s = "".join([s[:int(iq)-1],q,s[int(iq):]])
    '''
    if type =="2":
        print(len(set(s[int(iq)-1:int(q)])))

Submission status: Wrong Answer

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

for i in range(q):
    type,iq,q=map(str,input().split())
    if type == "1":
        s = "".join([s[:int(iq)-1],q,s[int(iq):]])
'''
    else:
        print(len(set(s[int(iq)-1:int(q)])))
'''

Submission status: Wrong Answer

Solution code:
import math

class SegmentTree:
	def update(self, i, x):
		i += self.num_leaves-1
		self.nodes[i] = x
		while i > 0:
			i = (i-1) // 2
			self.nodes[i] = self.monoid(self.nodes[i*2+1],self.nodes[i*2+2])
			
	def query(self,a,b,k=0,l=0,r=None):
		if r is None:
			r = self.num_leaves
		if r <= a or b <= l:
			return None
		if a <= l and r <= b:
			return self.nodes[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 self.monoid(vl,vr)
		
	def __init__(self, monoid, values):
		self.monoid = lambda x, y : monoid(x, y) if x is not None and y is not None else (x if x is not None else y)
		self.num_leaves = 2**math.ceil(math.log2(len(values)))
		self.nodes = [None for i in range(self.num_leaves*2-1)]
		for i in range(len(values)):
			self.update(i,values[i])

n = int(input())
s = input()
q = int(input())
Q = [input().split() for i in range(q)]

SGT = [SegmentTree(lambda x,y: x or y, [False for i in range(n)]) for j in range(26)]

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

for i in range(q):
    a,b,c = Q[i]
    b = int(b)
    if a == "1":
        SGT[ord(s[b-1])-ord('a')].update(b-1, False)
        SGT[ord(c)-ord('a')].update(b-1, True)
    else:
        c = int(c)
        cnt = 0
        for j in range(26):
            cnt += SGT[j].query(b-1,c)
        print(cnt)

Submission status: Wrong Answer

Solution code:
import math

class SegmentTree:
	def update(self, i, x):
		i += self.num_leaves-1
		self.nodes[i] = x
		while i > 0:
			i = (i-1) // 2
			self.nodes[i] = self.monoid(self.nodes[i*2+1],self.nodes[i*2+2])
			
	def query(self,a,b,k=0,l=0,r=None):
		if r is None:
			r = self.num_leaves
		if r <= a or b <= l:
			return None
		if a <= l and r <= b:
			return self.nodes[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 self.monoid(vl,vr)
		
	def __init__(self, monoid, values):
		self.monoid = lambda x, y : monoid(x, y) if x is not None and y is not None else (x if x is not None else y)
		self.num_leaves = 2**math.ceil(math.log2(len(values)))
		self.nodes = [None for i in range(self.num_leaves*2-1)]
		for i in range(len(values)):
			self.update(i,values[i])

n = int(input())
s = input()
q = int(input())
Q = [input().split() for i in range(q)]

SGT = [SegmentTree(lambda x,y: x or y, [False for i in range(n)]) for j in range(26)]

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

for i in range(q):
    a,b,c = Q[i]
    b = int(b)
    if a == "1":
        SGT[ord(s[b-1])-ord('a')].update(b-1, True)
        SGT[ord(c)-ord('a')].update(b-1, True)
    else:
        c = int(c)
        cnt = 0
        for j in range(26):
            cnt += SGT[j].query(b-1,c)
        print(cnt)