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:
class SegTreeSum:
    def __init__(self, V):
        self.sz = len(V)
        N = 1
        while N < self.sz:
            N *= 2
        self.N = N
        self.node = [0] * (2 * self.N - 1)
        for i in range(self.sz):
            self.node[i + self.N - 1] = V[i]

        for i in range(self.N-2,-1,-1):
            self.node[i] = self.node[2*i+1] + self.node[2*i+2]

        
    def add(self,x,val):
        x += (self.N - 1)

        self.node[x] += val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = self.node[2*x+1] + self.node[2*x+2]

    def getsum(self,a,b,k=0,l=0,r=-1):
        if r < 0:
            r = self.N
        
        if b <= l or a >= r:
            return 0
        
        if a <= l and b >= r:
            return self.node[k]

        vl = self.getsum(a,b, 2*k+1, l, (l+r)//2)
        vr = self.getsum(a,b, 2*k+2, (l+r)//2, r)
        return vl + vr

def main():
    N = int(input())
    S = input()
    Q = int(input())
    V = [0] * N
    seg_a = SegTreeSum(V)
    seg_b = SegTreeSum(V)
    seg_c = SegTreeSum(V)
    seg_d = SegTreeSum(V)
    seg_e = SegTreeSum(V)
    seg_f = SegTreeSum(V)
    seg_g = SegTreeSum(V)
    seg_h = SegTreeSum(V)
    seg_i = SegTreeSum(V)
    seg_j = SegTreeSum(V)
    seg_k = SegTreeSum(V)
    seg_l = SegTreeSum(V)
    seg_m = SegTreeSum(V)
    seg_n = SegTreeSum(V)
    seg_o = SegTreeSum(V)
    seg_p = SegTreeSum(V)
    seg_q = SegTreeSum(V)
    seg_r = SegTreeSum(V)
    seg_s = SegTreeSum(V)
    seg_t = SegTreeSum(V)
    seg_u = SegTreeSum(V)
    seg_v = SegTreeSum(V)
    seg_w = SegTreeSum(V)
    seg_x = SegTreeSum(V)
    seg_y = SegTreeSum(V)
    seg_z = SegTreeSum(V)
    Segs = [ seg_a, seg_b, seg_c, seg_d, seg_e, seg_f, \
        seg_g, seg_h, seg_i, seg_j, seg_k, seg_l, seg_m, \
        seg_n, seg_o, seg_p, seg_q, seg_r, seg_s, seg_t, \
        seg_u, seg_v, seg_w, seg_x, seg_y, seg_z ]
    for i in range(26):
        tmp = chr(i + 97)
        for j, k in enumerate(S):
            if k == tmp:
                Segs[i].add(j,1)
    
    for _ in range(Q):
        a, b, c = input().split()
        b = int(b) - 1
        if a == '1':
            d = ord(c) - 97
            Segs[i].add(b,1)
        else:
            ans = 0
            c = int(c)
            for i in range(26):
                if Segs[i].getsum(b,c):
                    ans += 1
            print(ans)





if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
s = input()
ss = [[(1 << ord(c) - ord('a')) for c in s]]
while len(ss[-1]) > 1:
    r = []
    for i in range(0, len(ss[-1]), 2):
        if i == len(ss[-1]) - 1:
            r.append(ss[-1][i])
        else:
            r.append(ss[-1][i] | ss[-1][i + 1])
    ss.append(r)
#print(ss)

def update(j, v):
    ss[0][j] = v
    for k in range(1, len(ss)):
        j = j // 2
        #print('k=', k, 'j=', j)
        if 2 * j + 1 >= len(ss[k - 1]):
            ss[k][j] = ss[k - 1][2 * j]
        else:
            ss[k][j] = ss[k - 1][2 * j] | ss[k - 1][2 * j + 1]
    #print('j=', j, 'v=', v, 'ss=', ss)

def all_or(i, j, k):
    #print('all_or(', i, j, k, ')')
    if i == j:
        return 0
    if k == 0:
        return ss[0][i]
    ik, jk = (i >> k), (j >> k)
    if ik == jk:
        return all_or(i, j, k - 1)
    r = 0
    if i == ik << k:
        r = ss[k][ik]
    else:
        r = all_or(i, jk << k, k - 1)
    r |= all_or(jk << k, j, k - 1)
    return r

def popcount(v):
    r = 0
    while v != 0:
        v = (v & (v - 1))
        r += 1
    return r

q = int(input())

for i in range(q):
    cs = [x for x in input().split()]
    cs[0], cs[1] = int(cs[0]), int(cs[1]) - 1
    if cs[0] == 1:
        #print('cs[2]=', cs[2], 'mask=', 1 << (ord(cs[2]) - ord('a')))
        update(cs[1], (1 << (ord(cs[2]) - ord('a'))))
    else:
        #print('all_or(', cs[1], int(cs[2]), ')=',all_or(cs[1], int(cs[2]), len(ss) - 1))
        # r = 0
        #for j in range(cs[1], int(cs[2])):
        #    r |= ss[0][j]
        print(popcount(all_or(cs[1], int(cs[2]), len(ss) - 1)))
        # print(popcount(r))

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
s = input()
ss = [[(1 << ord(c) - ord('a')) for c in s]]
while len(ss[-1]) > 1:
    r = []
    for i in range(0, len(ss[-1]), 2):
        if i == len(ss[-1]) - 1:
            r.append(ss[-1][i])
        else:
            r.append(ss[-1][i] | ss[-1][i + 1])
    ss.append(r)
#print(ss)

def update(j, v):
    ss[0][j] = v
    for k in range(1, len(ss)):
        j = j // 2
        #print('k=', k, 'j=', j)
        if 2 * j + 1 >= len(ss[k - 1]):
            ss[k][j] = ss[k - 1][2 * j]
        else:
            ss[k][j] = ss[k - 1][2 * j] | ss[k - 1][2 * j + 1]
    #print('j=', j, 'v=', v, 'ss=', ss)

def all_or(i, j, k):
    #print('all_or(', i, j, k, ')')
    if i == j:
        return 0
    if k == 0:
        return ss[0][i]
    ik, jk = (i >> k), (j >> k)
    if ik == jk:
        return all_or(i, j, k - 1)
    r = 0
    if i == ik << k:
        r = ss[k][ik]
    else:
        r = all_or(i, jk << k, k - 1)
    r |= all_or(jk << k, j, k - 1)
    return r

def popcount(v):
    r = 0
    while v != 0:
        v = (v & (v - 1))
        r += 1
    return r

q = int(input())

for i in range(q):
    cs = [x for x in input().split()]
    cs[0], cs[1] = int(cs[0]), int(cs[1]) - 1
    if cs[0] == 1:
        #print('cs[2]=', cs[2], 'mask=', 1 << (ord(cs[2]) - ord('a')))
        update(cs[1], (1 << (ord(cs[2]) - ord('a'))))
    else:
        #print('all_or(', cs[1], int(cs[2]), ')=',all_or(cs[1], int(cs[2]), len(ss) - 1))
        r = 0
        for j in range(cs[1], int(cs[2])):
            r |= ss[0][j]
        print(popcount(all_or(cs[1], int(cs[2]), len(ss) - 1)))
        # print(popcount(r))

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
s = input()
ss = [[(1 << ord(c) - ord('a')) for c in s]]
while len(ss[-1]) > 1:
    r = []
    for i in range(0, len(ss[-1]), 2):
        if i == len(ss[-1]) - 1:
            r.append(ss[-1][i])
        else:
            r.append(ss[-1][i] | ss[-1][i + 1])
    ss.append(r)
#print(ss)

def update(j, v):
    ss[0][j] = v
    for k in range(1, len(ss)):
        j = j // 2
        #print('k=', k, 'j=', j)
        if 2 * j + 1 >= len(ss[k - 1]):
            ss[k][j] = ss[k - 1][2 * j]
        else:
            ss[k][j] = ss[k - 1][2 * j] | ss[k - 1][2 * j + 1]
    #print('j=', j, 'v=', v, 'ss=', ss)

def all_or(i, j, k):
    #print('all_or(', i, j, k, ')')
    if i == j:
        return 0
    if k == 0:
        return ss[0][i]
    ik, jk = i >> k, j >> k
    if ik == jk:
        return all_or(i, j, k - 1)
    irest, jrest = i & ((1 << k) - 1), j & ((1 << k) - 1)
    r = 0
    if irest == 0:
        r = ss[k][ik]
    else:
        r = all_or(i, jk * (1 << k), k - 1)
    if jrest != 0:
        r |= all_or(jk * (1 << k), j, k - 1)
    return r

def popcount(v):
    r = 0
    while v != 0:
        v = (v & (v - 1))
        r += 1
    return r

q = int(input())

for i in range(q):
    cs = [x for x in input().split()]
    cs[0], cs[1] = int(cs[0]), int(cs[1]) - 1
    if cs[0] == 1:
        #print('cs[2]=', cs[2], 'mask=', 1 << (ord(cs[2]) - ord('a')))
        update(cs[1], (1 << (ord(cs[2]) - ord('a'))))
    else:
        #print('all_or(', cs[1], int(cs[2]), ')=',all_or(cs[1], int(cs[2]), len(ss) - 1))
        print(popcount(all_or(cs[1], int(cs[2]), len(ss) - 1)))

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 = [0 for _ in range(2 * size - 1)]


def alphabet2bit(string):
    return 1 << (26 - (ord(string) - ord('a')))

def update(i, x, segment_tree):
    i += size - 1
    segment_tree[i] = alphabet2bit(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 0
    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(bin(result).count('1'))

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 = [0 for _ in range(2 * size - 1)]


def alphabet2bit(string):
    return 1 << (26 - (ord(string) - ord('a')))

def update(i, x, segment_tree):
    i += size - 1
    segment_tree[i] = alphabet2bit(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 0
    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(bin(result).count('1'))

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from bisect import bisect_left
import sys,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
s = list(input())
q = inp()
Qs = [input().split() for i in range(q)]
upd = []
acc = [[0] * 26 for i in range(n+1)]
for i,t in enumerate(s):
    tmp = ord(t) - ord('a')
    # print(tmp)
    for j in range(26):
        if j == tmp:
            acc[i+1][j] = acc[i][j] + 1
            continue
        acc[i+1][j] = acc[i][j]
# print(acc)
for i,t in enumerate(Qs):
    a,b,c = t
    b = int(b)
    if a == '1':
        upd.append([b,ord(s[b-1])-ord('a'),ord(c)-ord('a')])
    else:
        c = int(c)
        cnt = 0
        now = [0] * 26
        for j in range(26):
            now[j] = acc[c][j] - acc[b-1][j]
        for j,k in enumerate(upd):
            if b-1 <= k[0] <= c:
                now[k[1]] -= 1
                now[k[2]] += 1
        for j in range(26):
            if now[j] > 0: cnt += 1
        print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from bisect import bisect_left
import sys,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
s = list(input())
q = inp()
Qs = [input().split() for i in range(q)]
upd = []
acc = [[0] * 26 for i in range(n+1)]
for i,t in enumerate(s):
    tmp = ord(t) - ord('a')
    # print(tmp)
    for j in range(26):
        if j == tmp:
            acc[i+1][j] = acc[i][j] + 1
            continue
        acc[i+1][j] = acc[i][j]
# print(acc)
for i,t in enumerate(Qs):
    a,b,c = t
    b = int(b)
    if a == '1':
        upd.append([b,ord(s[b-1])-ord('a'),ord(c)-ord('a')])
    else:
        c = int(c)
        cnt = 0
        now = [0] * 26
        for j in range(26):
            now[j] = acc[c][j] - acc[b-1][j]
        for j,k in enumerate(upd):
            if k[0] <= c:
                now[k[1]] -= 1
                now[k[2]] += 1
        for j in range(26):
            if now[j] > 0: cnt += 1
        print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from bisect import bisect_left
import sys,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
s = list(input())
q = inp()
Qs = [input().split() for i in range(q)]
upd = []
acc = [[0] * 26 for i in range(n+1)]
for i,t in enumerate(s):
    tmp = ord(t) - ord('a')
    # print(tmp)
    for j in range(26):
        if j == tmp:
            acc[i+1][j] = acc[i][j] + 1
            continue
        acc[i+1][j] = acc[i][j]
# print(acc)
for i,t in enumerate(Qs):
    a,b,c = t
    b = int(b)
    if a == '1':
        upd.append([b,ord(s[b-1])-ord('a'),ord(c)-ord('a')])
    else:
        c = int(c)
        cnt = 0
        now = [0] * 26
        for j in range(26):
            now[j] = acc[c][j] - acc[b-1][j]
        for j,k in enumerate(upd):
            if b < k[0] <= c:
                now[k[1]] -= 1
                now[k[2]] += 1
        for j in range(26):
            if now[j] > 0: cnt += 1
        print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from bisect import bisect_left
import sys,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
s = list(input())
q = inp()
Qs = [input().split() for i in range(q)]
upd = []
acc = [[0] * 26 for i in range(n+1)]
for i,t in enumerate(s):
    tmp = ord(t) - ord('a')
    # print(tmp)
    for j in range(26):
        if j == tmp:
            acc[i+1][j] = acc[i][j] + 1
            continue
        acc[i+1][j] = acc[i][j]
# print(acc)
for i,t in enumerate(Qs):
    a,b,c = t
    b = int(b)
    if a == '1':
        upd.append([b,ord(s[b-1])-ord('a'),ord(c)-ord('a')])
    else:
        c = int(c)
        cnt = 0
        now = [0] * 26
        for j in range(26):
            now[j] = acc[c][j] - acc[b-1][j]
        for j,k in enumerate(upd):
            if b <= k[0] <= c:
                now[k[1]] -= 1
                now[k[2]] += 1
        for j in range(26):
            if now[j] > 0: cnt += 1
        print(cnt)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    S = input()
    c = lambda x: 1 << (ord(x) - ord('a'))
    d = [c(S[i]) for i in range(N)]
    l = lambda x,y:x|y
    bit_l = BinaryIndexedTree(d, l)
    bit_r = BinaryIndexedTree(list(reversed(d)), l)
    Q = int(input())
    for _ in range(Q):
        t, a, b = input().split()
        if t == '1':
            a = int(a)
            bit_l.add(a, c(b))
            bit_r.add(N-a+1, c(b))
        else:
            a, b = int(a), int(b)
            l = bit_l.sum(b)
            r = bit_r.sum(N-a+1)
            print(bin(l&r).count('1'))

class BinaryIndexedTree:
    def __init__(self, initial_values, f=lambda x,y:x+y, zero=0):
        self.__f, self.__z, self.__n = f, zero, len(initial_values)
        self.__dat = [zero] * (self.__n + 1)
        for i in range(1, self.__n + 1):
            self.add(i, initial_values[i-1])

    def add(self, i, v):
        while i <= self.__n:
            self.__dat[i] = self.__f(self.__dat[i], v)
            i += -i&i

    def sum(self, r):
        ans = self.__z
        while r:
            ans = self.__f(ans, self.__dat[r])
            r -= -r&r
        return ans

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
  import sys
  n,s,_,*t=sys.stdin.buffer.read().split()
  n=int(n)
  d=[0]*n+[1<<c-97for c in s]
  for i in range(n-1,0,-1):d[i]=d[i+i]|d[i-~i]
  for q,a,b in zip(*[iter(t)]*3):
    i,s=a[0]+n-49,0
    if q<b'2':
      d[i]=1<<b[0]-97
      while i>1:
        i//=2
        d[i]=d[i+i]|d[i-~i]
      continue
    j=b[0]+n-48
    while i<j:
      if i&1:
        s|=d[i]
        i+=1
      if j&1:
        j-=1
        s|=d[j]
      i//=2
      j//=2
    print(bin(s).count('1'))
main()

Submission status: Wrong Answer

Solution code:
import numpy as np

N = [int(i) for i in input().split()][0]
string = list(input())
Q = [int(i) for i in input().split()][0]
queries = [[i for i in input().split()] for _ in range(Q)]

tmp = N 
c = 0
while tmp > 0:
  c += 1
  tmp //= 2
N2 = 2**c

seg_trees = np.array([[0 for _ in range(26)] for _ in range(N2*2 -1)])
for n in range(N):
  ind = ord(string[n]) - ord("a")
  seg_trees[N2-1+n][ind] = 1                     

def set_seg_tree(i, seg_trees):
  if i >= N2 -1:
    return seg_trees[i]
  left = 2*i + 1
  right = 2*i + 2
  l_seg = set_seg_tree(left, seg_trees)
  r_seg = set_seg_tree(right, seg_trees)
  seg_trees[i] = l_seg + r_seg
  return seg_trees[i]
set_seg_tree(0, seg_trees)

    
def modify_diff(i, c, diff, seg_trees):
  i += N2 -1
  seg_trees[i, c] += diff
  while i > 0:
    i = (i - 1)//2
    seg_trees[i, c] = seg_trees[i * 2 + 1, c] + seg_trees[i * 2 + 2, c]

def get_sum(a, b, k, l, r, seg_trees):
  if (b <= l) or (r <= a):
    return 0
  if (a <= l) and (r <= b):
    return seg_trees[k]
  vl = get_sum(a, b, k * 2 + 1, l, (l + r)//2, seg_trees)
  vr = get_sum(a, b, k * 2 + 2, (l + r)//2, r, seg_trees)
  return vl + vr

for query in queries:
  type_, i, q = query
  if type_ == "1":
    i = int(i) - 1
    pos = ord(q) - ord("a")
    old = ord(string[i]) - ord("a")
    string[i] = q
    modify_diff(i, 1, pos, seg_trees)
    modify_diff(i, -1, old, seg_trees)
  else:
    l = int(i) - 1
    r = int(q)
    ret = get_sum(l, r, 0, 0, N2, seg_trees)
    print(np.sum(ret > 0))

Submission status: Wrong Answer

Solution code:
# import math
# from itertools import permutations as permus
# from fractions import gcd

# import numpy as np
# import scipy as scp

# 入力の受け取り
n = int(input())
s = input()
q = int(input())

times = q

strlis = list(s)

def qtype1(strlis,i,c):
    i = int(i)
    if len(strlis) >= 2:
        strlis = strlis[:max(i-2,0)] + list(c) + strlis[i:]
    else:
        strlis[i-1] = c

def qtype2(i,c):
    i = int(i)
    c = int(c)
    count = len(set(strlis[i-1:c]))
    print(count)

querys = []
for _ in range(times):
    querys.append(list(input().split()))

for qtype,i,c in querys:
    if qtype == "1":
        qtype1(strlis,i,c)
    elif qtype == "2":
        qtype2(i,c)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

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

class SegTree:
    def __init__(self, nn, A):
        l = len(A)
        self.nn = nn
        self.X = [0] * ((1<<nn)-1) + A
        for i in range((1<<nn)-1)[::-1]:
            self.X[i] = self.X[i*2+1] | self.X[i*2+2]
    
    def update(self, a, x):
        i = (1<<self.nn) - 1 + a
        self.X[i] = x
        while i:
            i = (i-1) // 2
            self.X[i] = self.X[2*i+1] | self.X[2*i+2]

    def rangeor(self, a, b):
        l = a + (1<<self.nn)
        r = b + (1<<self.nn)
        x = 0
        while l < r:
            if l%2:
                x |= self.X[l-1]
                l += 1
            if r%2:
                r -= 1
                x |= self.X[r-1]
            l >>= 1
            r >>= 1
        return x
    
N = int(input())
A = [ord(a) - 97 for a in input()]
X = [0] * (1<<19)
for i, a in enumerate(A):
    X[i] = 1 << a

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

Submission status: Wrong Answer

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

al = "abcdefghijklmnopqrstuvwxyz"
ald = {}
for i in range(26):
    ald[al[i]] = i

def BIT_query(BIT, idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(N, BIT, idx, x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

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

bits = [[0]*(N+1) for i in range(26)]

for i in range(N):
    ind = ald[S[i]]
    BIT_update(N, bits[ind], i+1, 1)

for i in range(Q):
    f, a, b = (i for i in input().split())
    if f == "1":
        a = int(a)
        if S[a-1] == b:
            pass
        else:
            ind = ald[S[a-1]]
            BIT_update(N, bits[ind], a, -1)
            ind = ald[b]
            BIT_update(N, bits[ind], a, 1)
    else:
        a = int(a)
        b = int(b)
        ans = 0
        for bit in bits:
            if a != 1:
                mi = BIT_query(bit, a-1)
            else:
                mi = 0
            if BIT_query(bit, b) > mi:
                ans += 1
        print(ans)

Submission status: Wrong Answer

Solution code:
A = ord("a")
N = int(input())
S = list(map(lambda c: ord(c) - A, input().strip()))
Q = int(input())

def count(s, e):
	counts = [0] * 26
	for i in range(s, min(N, e)):
		counts[S[i]] += 1
	return counts

count_table = []

w = 1
while True:
	counts = []
	j = 0
	while j < N:
		counts.append(count(j, j + w))
		j += w
	count_table.append([w, counts])
	if w >= N:
		break
	w *= 2

#for i, counts in enumerate(count_table):
#	print(i, ">", len(counts))

#def set2str(s):
#	return "".join(chr(A + j) + str(s[j]) if s[j] > 0 else "" for j in range(26))

def count2(e):
	result = [0] * 26
	
	for w, counts in count_table:
		if e % (w * 2) >= w:
#			print(">", e, w, (e // w - 1))
			c = counts[e // w - 1]
			for i in range(26):
				result[i] += c[i]
	return result

for _ in range(Q):
	t, i, q = input().split()
	
#	print("q", t, i, q)
	
	if t == "1":
		i = int(i) - 1
		q = ord(q) - A
		s = S[i]
		if s != q:
			for w, counts in count_table:
				c = counts[(i + 1) // w - 1]
				c[s] -= 1
				c[q] += 1
				S[i] = q
	else:
		l = int(i) - 1
		r = int(q)
		c1 = count2(l)
		c2 = count2(r)
		c3 = 0
#		exists = []
#		e1 = []
#		e2 = []
		for i in range(26):
			if c2[i] - c1[i] > 0:
				c3 += 1
#				exists.append(chr(A + i))
#			if c1[i] > 0:
#				e1.append(chr(A + i))
#			if c2[i] > 0:
#				e2.append(chr(A + i))
		
#		for w, counts in count_table:
#			print(",".join(set2str(c) for c in counts))
#		print(c3, e1, e2, exists)
		print(c3)

Submission status: Wrong Answer

Solution code:
class SegmentTree:
	def __init__(self, n, *, init = None, data = None, merge = None):
		if init != None and data != None:
			raise Error("init and data cannot be specified at a time")
		if init == None and data == None:
			raise Error("one of init or data must be specified")
		self.n = n
		data_table = []
		if data:
			data_table.append((1, data))
		else:
			data_table.append((1, tuple(init(i, i + 1) for i in range(n))))
		
		w = 2
		if merge == None:
			while w <= n:
				data_table.append((w, tuple(init(i, i + w) for i in range(0, ((n - 1) // w + 1) * w, w))))
				w *= 2
		else:
			last_data = data_table[0][1]
			while w <= n:
				if len(last_data) % 2 == 0:
					new_data = tuple(merge(last_data[i * 2], last_data[i * 2 + 1]) for i in range(0, (n - 1) // w + 1))
				else:
					new_data = tuple(merge(last_data[i * 2], last_data[i * 2 + 1]) for i in range(0, (n - 1) // w)) + (last_data[-1], )
				data_table.append((w, new_data))
				last_data = new_data
				w *= 2
		self.data_table = data_table
		
	def data_at(self, i):
		for w, data_list in self.data_table:
			yield data_list[(i + 1) // w - 1]
	
	def data_range(self, s, e = None):
		if e == None:
			e = s
			s = 0
		if s == 0:
			for w, data_list in reversed(self.data_table):
				if e % (w * 2) >= w:
					yield data_list[e // w - 1]
		elif s < e:
			for w, data_list in self.data_table:
				w2 = w * 2
				m = s % w2
				new_s = s + w2 - m
				if new_s > e:
					break
				if m != 0:
					yield data_list[s // w]
					s = new_s
			if s == e:
				return
			for w, data_list in reversed(self.data_table):
				new_s = s + w
				if new_s <= e:
					yield data_list[s // w]
					s = new_s
			
			return
			for w, data_list in self.data_table:
#				print(f"({s} - {e})")
				w2 = w * 2
				m = s % w2
				if m != 0:
					yield data_list[s // w]
					s += w2 - m
					if s == e:
						break
				m = e % w2
				if m != 0:
					yield data_list[e // w - 1]
					e -= m
					if s == e:
						break
	
	def output(self, func):
		for w, data_list in self.data_table:
#			print(f"#{w}: " + ", ".join(func(data) for data in data_list))
			pass


A = ord("a")
N = int(input())
S = list(map(lambda c: ord(c) - A, input().strip()))
Q = int(input())

def count(s, e):
	counts = [0] * 26
	for i in range(s, min(N, e)):
		counts[S[i]] += 1
	return counts

def merge(count1, count2):
	result = list(count1)
	for i in range(26):
		result[i] += count2[i]
	return result

st = SegmentTree(N, init = count, merge = merge)

for _ in range(Q):
	t, i, q = input().split()
	
	if t == "1":
		i = int(i) - 1
		q = ord(q) - A
		s = S[i]
		for data in st.data_at(i):
			data[s] -= 1
			data[q] += 1
		S[i] = q
	else:
		l = int(i) - 1
		r = int(q)
		result = [0] * 26
		for data in st.data_range(l, r):
			for i in range(26):
				result[i] += data[i]
		
		count = 0
		for i in range(26):
			if result[i] > 0:
				count += 1
#		st.output(lambda data: "".join(chr(A + j) + str(data[j]) if data[j] > 0 else "" for j in range(26)))
		
		print(count)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
Q=int(input())
Qu=[input().split() for w in range(Q)]
def Query(a,b,c):
  if a==1:
    P=S[:b]+c+S[b+1:]
    return P
  
  else:
    c=int(c)
    L=S[b-1:c]
    
    print(len(set(L)))
    return S
    
    
for i in range(Q):
  S=Query(int(Qu[i][0]),int(Qu[i][1]),Qu[i][2])

Submission status: Wrong Answer

Solution code:
def getsum(BITTree,i):
    s = 0
    i = i+1
    while i > 0:
        s += BITTree[i]
        i -= i & (-i)
    return s

def updatebit(BITTree , n , i ,v):
    i += 1
    while i <= n:
        BITTree[i] += v
        i += i & (-i)

def construct(arr, n):
    BITTree = [0]*(n+1)
    for i in range(n):
        updatebit(BITTree, n, i, arr[i])
    return BITTree

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

BIT = [construct([0]*(N+1),N+1) for k in range(26)]

for k in range(N):
    updatebit(BIT[ord(S[k])-97],N,k,1)

for _ in range(int(input())):
    l = list(input().split())
    if l[0] == "1":
        updatebit(BIT[ord(S[int(l[1])-1])-97],N,int(l[1])-1,-1)
        updatebit(BIT[ord(l[2])-97],N,int(l[1])-1,1)
    else:
        t = 0
        a, b = int(l[1])-1, int(l[2])-1
        for k in range(26):
            if getsum(BIT[k],b)-getsum(BIT[k],a-1) > 0:
                t += 1
        print(t)

Submission status: Wrong Answer

Solution code:
n=int(input())+1
w = input()
data=[0]*n*2
def update(i,x):
    i+=n
    data[i]=x
    i//=2
    while i:
      data[i]=data[i*2]|data[i*2+1]
      i//=2
def query(l,r):
    l+=n
    r+=n
    s=0
    while l<r:
      if l&1 == 1:
        s|=data[l]
        l+=1
      if r&1 == 1:
        r-=1
        s|=data[r]
      l//=2
      r//=2
    return bin(s).count('1')
def word_num(a):
    return 1<<(ord(a)-97)

for i in range(n-1):
    data[i+n] = word_num(w[i])    
for i in range(n-1,0,-1):
    data[i]=data[i*2]|data[i*2 + 1]
print(list(map(lambda x:bin(x),data)))      

ans=[]
q=int(input())
for i in range(q):
    a,s,t=input().split()
    if a=='1':
        s=int(s)
        update(int(s)-1,word_num(t))
    if a=='2':
        s=int(s)
        t=int(t)
        ans.append(query(int(s)-1,int(t)))
for i in range(len(ans)):
    print(ans[i])