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: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class SegmentTree():
    def __init__(self, n):
        self.n = 2**(n-1).bit_length()
        self.data = [0 for _ in range(2*self.n)]

    def set(self, k, v):
        v_val = ord(v)-ord('a') #アルファベットを数字にする。'a'->1, 'b'->2 ..
        self.data[k+self.n-1] = 1 << v_val #含むアルファベットをbitで管理

    def build(self):
        for k in reversed(range(self.n-1)):
            self.data[k] = self.data[k*2+1] | self.data[k*2+2] 

    def update(self, k, a):
        k += self.n-1
        v_val = ord(a)-ord("a")
        self.data[k] = 1 << v_val

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.data[k*2+1] | self.data[k*2+2]

    def query(self, l, r):
        L = l+self.n
        R = r+self.n
        ret = 0
        while L < R:
            if R & 1:
                R -= 1
                ret |= self.data[R-1]
            if L & 1:
                ret |= self.data[L-1]
                L += 1
            L >>= 1
            R >>= 1
        return ret

N = int(input())
S = [v for v in input()[:-1]]
Q = int(input())
query = [[v for v in input()[:-1].split()] for _ in range(Q)]

Seg = SegmentTree(N)
for i, s in enumerate(S):
    Seg.set(i, s)

Seg.build()

for q, v1, v2 in query:
    if q == "1":
        Seg.update(int(v1)-1, v2)
    else:
        val = Seg.query(int(v1)-1, int(v2))
        print(bin(val)[2:].count("1"))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
N = int(input())
S = list(input())
Q = int(input())

D = {chr(ord('a') + i): [] for i in range(26)}

for i, s in enumerate(S):
    D[s].append(i)

for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1]), query[2]
        i -= 1
        s = S[i]
        if s == x:
            continue

        D[s].remove(i)
        next_i = bisect_left(D[x], i)
        D[x].insert(next_i, i)
        S[i] = x

    if query[0] == '2':
        l, r = int(query[1]), int(query[2])
        l, r = l - 1, r - 1
        ans = 0
        for i in range(26):
            s = chr(ord('a') + i)

            li = bisect_left(D[s], l)
            ri = bisect_right(D[s], r)

            if ri - li > 0:
                ans += 1

        print(ans)

Submission status: Accepted

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, -1)
        addbit(c, b+1, 1)
        A[b-1] = c
    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: Accepted

Solution code:
#ライブラリインポート
from collections import defaultdict
INF = float("inf")
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#更新クエリ
def update(data, k, x, N0):
	k += N0 - 1
	data[k] = x
	while k > 0:
		k = (k - 1) // 2
		data[k] = data[2 * k + 1] | data[2 * k + 2]

#求値クエリ 最初:query(a, b, 0, 0, N0)
def query(data, a, b, k, l, r):
	if r <= a or b <= l:
		return 0
	if a <= l and r <= b:
		return data[k]
	else:
		vl = query(data, a, b, k * 2 + 1, l, (l + r) // 2)
		vr = query(data, a, b, k * 2 + 2, (l + r) // 2, r)
		return vl | vr

#処理内容
def main():
	N = int(input())

	#セグ木初期化
	N0 = 2 ** (N - 1).bit_length()
	S = list(input())
	data = [0] * (2 * N0 - 1)
	for i in range(N):
		data[N0 - 1 + i] = 2 ** (ord(S[i]) - 97)
		ind = N0 - 1 + i
		while ind > 0:
			ind = (ind - 1) // 2
			data[ind] = data[ind * 2 + 1] | data[ind * 2 + 2]

	Q = int(input())
	for _ in range(Q):
		que = list(input().split())
		if que[0] == "1":
			i = int(que[1]) - 1
			c = 2 ** (ord(que[2]) - 97)
			update(data, i, c, N0)
		else:
			a = int(que[1])
			b = int(que[2])
			a -= 1
			jjj = query(data, a, b, 0, 0, N0)
			ans = 0
			while jjj != 0:
				if jjj % 2 == 1:
					ans += 1
				jjj = int(jjj // 2)

			print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  n = int(input())
  s = list(input())

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

  def init(init_val):
      #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):
      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):
      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

  #####単位元######
  ide_ele = 0

  #num:n以上の最小の2のべき乗
  num =2**(n-1).bit_length()
  seg=[ide_ele]*2*num

  A = []
  for i in range(n):
    A.append(1<<(ord(s[i])-96))
  init(A)
  q = int(input())
  for _ in range(q):
    p,a,b = input().split()
    if p == "1":
      update(int(a)-1,1<<(ord(b)-96))
    if p == "2":
      print(bin(query(int(a)-1,int(b))).count("1"))
main()

Submission status: Accepted

Solution code:
N = int(input())
S = list(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_add2(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 x, y, z in query:
    if x == "1":
        y = int(y)
        bit_add2(y, S[y - 1])
        bit_add(y, z)
        S[y - 1] = 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)
    #print(S)
    #print(bit_sum(N))

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))



def main():
    mod=10**9+7
    N=I()
    S=input()
    Q=I()
    
    #####segfunc######

    #評価関数
    def segfunc(x,y):
        return x|y


    #初期化
    def init(init_val):
        #init_valは操作する数列
        for i in range(N):
            seg[i+num-1]=set([ord(init_val[i])])    
        #built
        for i in range(num-2,-1,-1) :
            seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
            

    #k番目の値をxに更新
    def update(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])

            
    #[p,q)の区間に対するクエリへの応答
    def query(p,q):
        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 len(res)


    #####単位元######
    ide_ele = set([])

     #num:n以上の最小の2のべき乗
    num =2**(N-1).bit_length()
    seg=[ide_ele]*2*num
    init(S)



    
    for i in range(Q):
        q,a,b=input().split()
        if q=="1":
            update(int(a)-1,set([ord(b)]))
        else:
            print(query(int(a)-1,int(b)))
            
    
    

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        if i == 0:
            return 0
        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
aas = "abcdefghijklmnopqrstuvwxyz"
N = int(input().strip())
S = list(input().strip())
Q = int(input().strip())
cbt = dict()
MX = 5 * 10**5 + 2
for c in aas:
    cbt[c] = Bit(MX)
    for i, a in enumerate(S):
        if a == c:
            cbt[c].add(i+1, 1)

for _ in range(Q):
    t, i, c = input().split()
    t = int(t)
    if t == 1:
        i = int(i)
        if S[i-1] != c:
            cbt[S[i-1]].add(i, -1)
            cbt[c].add(i, 1)
            S[i-1] = c
    else:
#        print(S)
        l, r = int(i), int(c)
#        print(l, r)
        s = 0
        for a in aas:
            bt = cbt[a]
#            print(a, bt.sum(r),bt.sum(l-1))
            s += (bt.sum(r)-bt.sum(l-1)>0)
        print(s)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

import math


class SegmentTree(object):
    # セグメント木

    def __init__(self, N):
        """サイズNの配列を元にしたセグメント木
        """
        # 単位元
        self.idelem = 0
        # 比較関数

        def f(a, b):
            return a | b

        self.func = f

        self.N0 = 1
        while self.N0 < N:
            self.N0 <<= 1
        self.tree = [self.idelem]*(2*self.N0)

    def update(self, k, x):
        """k番目の値をxに更新
        """
        k += self.N0-1
        self.tree[k] = x
        while k > 1:
            k = (k-1)//2
            self.tree[k] = self.func(self.tree[2*k+1], self.tree[2*k+2])

    def query(self, l, r):
        """区間[l, r)の最小値
        """
        l += self.N0-1
        r += self.N0-1
        s = self.idelem
        while l < r:
            if r % 2 == 0:
                r -= 1
                s = self.func(s, self.tree[r])

            if l % 2 == 0:
                s = self.func(s, self.tree[l])
                l += 1
            l //= 2
            r //= 2
        return s

    def __str__(self):
        return str(self.tree[self.N0-1:-1])


def bit_sum(n):
    wa = 0
    while n > 0:
        wa += n & 1
        n >>= 1
    return wa


def main():
    N = int(input())
    S = input()
    Q = int(input())
    query = [input().split() for i in range(Q)]

    seg = SegmentTree(N)
    for i, c in enumerate(S):
        seg.update(i, 1 << (ord(c)-ord('a')))

    for q in query:
        if q[0] == "1":
            seg.update(int(q[1])-1, 1 << (ord(q[2])-ord('a')))
        else:
            ans = seg.query(int(q[1])-1, int(q[2]))
            print(bit_sum(ans))
    pass


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = [ord(i) - 97 for i in input()]
Q = int(input())

# 添字が1から始まることに注意
class BinaryIndexedTree() :
  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
      
alph = [BinaryIndexedTree(N + 10) for _ in range(26)]
for i in range(N) :
  alph[S[i]].add(i + 1, 1)

for _ in range(Q) :
  type, x, y = input().split()
  if type == '1' :
    x = int(x)
    s = S[x - 1]
    alph[s].add(x, -1)
    alph[ord(y) - 97].add(x, 1)
    S[x - 1] = ord(y) - 97
  else :
    x, y = int(x), int(y)
    ret = 0
    for i in range(26) :
      if alph[i].sum(y) - alph[i].sum(x - 1) > 0 :
        ret += 1
    print(ret)

Submission status: Accepted

Solution code:
def segfunc(x,y):
    return x | y

def init(init_val):
    #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):
    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):
    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

ide_ele = 0

n = 500000
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
def main():
    N = int(input())
    S = input()
    for i, s in enumerate(S):
        update(i, 1 << (ord(s) - 97))
        
    Q = int(input())
    for _ in range(Q):
        t, a, b = input().split()
        if t == '1':
            update(int(a) - 1, 1 << (ord(b) - 97))
        else:
            print(bin(query(int(a) - 1, int(b))).count('1'))

main()

Submission status: Accepted

Solution code:
n=int(input())
S=list(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
    S[num]=q3
    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>0:
        ans+=1
    print(ans)

Submission status: Accepted

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]))
        s[x-1] = 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: Accepted

Solution code:
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)


def main():
    import sys

    input = sys.stdin.readline

    n = int(input())  # 5 * 10 ** 5
    s = input().rstrip()

    base = ord('a')
    *s, = (ord(c) - base for c in s)

    q = int(input())  # 2 * 10 ** 4

    bits = [BIT(n + 1) for _ in range(26)]
    for i, x in enumerate(s, 1):
        bits[x].add(i, 1)

    ret = []
    for _ in range(q):
        query = iter(input().split())
        if next(query) == '1':
            # 変更
            pos = int(next(query))

            bf = s[pos - 1]
            char = ord(next(query)) - base

            bits[bf].add(pos, -1)
            s[pos - 1] = char

            bits[char].add(pos, 1)

        else:
            # 返答
            l = int(next(query))
            r = int(next(query))

            tt = 0
            for x in range(26):
                if bits[x].get(l - 1, r) > 0:
                    tt += 1
            ret.append(tt)

    print(*ret, sep='\n')


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

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 = (i-1)>>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, bin(v))
        print(str(bin(v)).count('1'))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
S = list(input())
Q = INT()

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

dic_char = defaultdict(int)
for i, char in enumerate(ascii_lowercase):
	dic_char[char] = i

bits = [None]*len(ascii_uppercase)
for i in range(len(ascii_uppercase)):
	bits[i] = Bit(N)

for i in range(N):
	bits[dic_char[S[i]]].add(i+1, 1)

for _ in range(Q):
	a, b, c = input().split()
	if a == "1":  # BITを更新
		b = int(b)
		char = S[b-1]
		bits[dic_char[char]].add(b, -1)
		bits[dic_char[c]].add(b, 1)
		S[b-1] = c
	if a == "2":
		cnt = 0
		b, c = int(b), int(c)
		for i in range(len(ascii_uppercase)):
			cnt += bits[i].sum(c)-bits[i].sum(b-1) >= 1
		print(cnt)

Submission status: Accepted

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] = y
            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: Accepted

Solution code:
import bisect

N = int(input())
S = input()
Q = int(input())
alphabet_dic = {}
alphabet_array = []
for i,s in enumerate(S):
    alphabet_array.append(s)
    if s in alphabet_dic:
        alphabet_dic[s].append(i)
    else:
        alphabet_dic[s] = [i]
# print(alphabet_dic)

for _ in range(Q):
    a, b, c = map(str,input().split())
    if int(a) == 1:
        b = int(b)
        now_str = alphabet_array[b-1]
        if now_str != c:
            alphabet_array[b-1] = c
            alphabet_dic[now_str].remove(b-1)
            if c in alphabet_dic:
                bisect.insort_left(alphabet_dic[c],b-1)
            else:
                alphabet_dic[c] = [b-1]
    else:
        ans = 0
        b = int(b)
        c = int(c)
        for index_array in alphabet_dic.values():
            if not len(index_array) or index_array[-1] < b-1:
                continue
            i = bisect.bisect_left(index_array,b-1)
            if index_array[i] <= c-1:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 15 22:01:38 2019

@author: aozora
"""
class BIT:
  def __init__(self,n):
    self.N = n
    self.data = [0]*(N+1)
  def bit_add(self,i,a):
    j = i+1
    while j<=N:
      self.data[j] += a
      j += j&-j
  def bit_sum(self,i):
    m = 0
    j = i+1
    while j>0:
      m += self.data[j]
      j -= j&-j
    return m
N = int(input())
S = list(input())
Q = int(input())
dic = [0]*26
s = ord('a')
for i in range(26):
  dic[i] = BIT(N)
for i, c in enumerate(S):
  c = ord(c)-s
  dic[c].bit_add(i,1)
for i in range(Q):
  t, a, b = input().split()
  t = int(t)
  if t==1:
    a = int(a)-1
    c = S[a]
    S[a] = b
    b = ord(b)-s
    c = ord(c)-s
    dic[b].bit_add(a,1)
    dic[c].bit_add(a,-1)
  else:
    a = int(a)
    b = int(b)
    ans = 0
    a -= 1
    b -= 1
    for i in range(26):
      if a>0:
        z = dic[i].bit_sum(b)-dic[i].bit_sum(a-1)
      else:
        z = dic[i].bit_sum(b)
      if z>0:
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
import math

class segtree:
    def __init__(self,size):
        n = 1
        while n < size:
            n *= 2
        self.node = [0]*(2*n-1)
        self.begin = n

    def update(self,dex,value):
        dex += self.begin-1
        self.node[dex] = value
        while dex > 0:
            dex = (dex-1)//2
            self.node[dex] = self.node[dex*2+1] | self.node[dex*2+2]

    def segment(self,l,r):
        l += self.begin-1
        r += self.begin-1
        ans = 0
        while l <= r:
            if l==0:
                ans = self.node[0]
                break
            if l%2 == 0:
                ans |= self.node[l]
            l//=2
            if r%2 == 1:
                ans |= self.node[r]
            r = r//2 -1
        return ans

    def view(self):
        return  self.node

N = int(input())
seg = segtree(N)
S = input()
for i in range(N):
    seg.update(i,2**(ord(S[i])-ord("a")))
Q = int(input())
anses = []
for i in range(Q):
    a,b,c = input().split()
    if a=="1":
        seg.update(int(b)-1,2**(ord(c)-ord("a")))
    elif a=="2":
        ans = seg.segment(int(b)-1,int(c)-1)
        count = 0
        while ans:
            if ans & 1:
                count += 1
            ans >>= 1
        anses.append(count)
for i in anses:
    print(i)

Submission status: Accepted

Solution code:
class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s


n = int(input())
s = [ord(si) - ord('a') for si in list(input())]
bit_list = [BIT1(n + 1) for _ in range(26)]
for i in range(n):
    bit_list[s[i]].add(i + 1, +1)

q = int(input())
for _ in range(q):
    k, a, b = input().split()
    k = int(k)
    a = int(a)
    if k == 1:
        b = ord(b) - ord('a')
        # type1: update
        bit_list[s[a - 1]].add(a, -1)
        bit_list[b].add(a, +1)
        s[a - 1] = b
    else:
        # type2: calc
        b = int(b)
        a -= 1
        cnt = 0
        for bit_i in bit_list:
            if bit_i.sum(b) - bit_i.sum(a) > 0:
                cnt += 1
        print(cnt)

Submission status: Accepted

Solution code:
class BIT:
  ini = 0
  def __init__(s, num):
    s.N = 1
    while s.N <= num:
      s.N *= 2
    s.T = [s.ini] * s.N
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, n):
    k = x + 1
    s.T[k - 1] += n
    k += k & -k
    while k <= s.N:
      s.T[k - 1] += n
      k += k & -k
  def getV(s, x):
    if x <= 0: return 0
    ans = s.T[x - 1]
    x -= x & -x
    while x != 0:
      ans += s.T[x - 1]
      x -= x & -x
    return ans

N = int(input())
S = list(input())
Q = int(input())
Query = [list(input().split()) for _ in range(Q)]

B = []
R = {}

def add(i, s):
  global cnt
  if s not in R:
    b = BIT(N)
    b.update(i, 1)
    R[s] = cnt
    cnt += 1
    B.append(b)
  else:
    t = R[s]
    B[t].update(i, 1)

def minus(i, s):
  global cnt
  t = R[s]
  B[t].update(i, -1)

cnt = 0
for i in range(N):
  s = S[i]
  add(i, s)

for i in range(Q):
  q = Query[i]
  q[0] = int(q[0])
  q[1] = int(q[1])
  if q[0] == 1:
    n = q[1] - 1
    s = S[n]
    add(n, q[2])
    minus(n, s)
    S[n] = q[2]
  else:
    ans = 0
    q[2] = int(q[2])
    x, y = q[1] - 1, q[2]
    for i in range(cnt): 
      if B[i].getV(x) != B[i].getV(y):
        ans += 1
    print(ans)