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
read=sys.stdin.readline
class SEGTree:
    def __init__(self,n):
        self.Unit=0
        i=1
        while(i<n):
            i*=2
        self.SEG=[self.Unit]*(2*i-1)
        self.d=i
    def update(self,i,x):
        i+=self.d-1
        self.SEG[i]=1<<x
        while i>0:
            i=(i-1)//2
            self.SEG[i]=self.SEG[i*2+1]|self.SEG[i*2+2]
    def find(self,a,b,k,l,r):
        if r<=a or b<=l:
            return self.Unit
        if a<=l and r<=b:
            return self.SEG[k]
        else:
            c1=self.find(a,b,2*k+1,l,(l+r)//2)
            c2=self.find(a,b,2*k+2,(l+r)//2,r)
            return c1|c2
    def get(self,a,b):
        return self.find(a,b,0,0,self.d)
def bitcnt(x):
    res=0
    while x>0:
        if x&1:
            res+=1
        x//=2
    return res

n=int(input())
s=input()
q=int(input())
seg=SEGTree(n)
for i in range(n):
    seg.update(i,ord(s[i])-97)
for i in range(q):
    q,x,y=read().rstrip().split()
    if q=='1':
        seg.update(int(x)-1,ord(y)-97)
    else:
        x,y=int(x)-1,int(y)
        bit=seg.get(x,y)
        print(bitcnt(bit))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


class AVL_like_BIT:  # 1-indexed
    def __init__(self,n):  # 1~nを要素として持ちうる。
        self.n = n
        self.tree = [0]*(self.n+1)
        self.depth = n.bit_length()

    def add(self,k):  # kを木に加える
        while k<=self.n:
            self.tree[k]+=1
            k += k&-k
    
    def delete(self,k): # kを木から削除する
        while k<=self.n:
            self.tree[k]-=1
            k += k&-k

    def sum(self,k):  # 1~kの和
        ans = 0
        while k>0:
            ans += self.tree[k]
            k -= k&-k
        return ans
    
    def lower_bound(self,k):  # k以上の最小要素
        x = self.sum(k-1)
        if x == self.sum(self.n):  # k以上の要素がないときは-1を返す
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  # sum(p) = sum(k-1)なるpの右端 + 1が答え
            q = p+v
            if q <= self.n and self.tree[q] <= x:
                x -= self.tree[q]
                p += v
            v>>=1
        return p+1

    def upper_bound(self,k):  # k以下の最大要素
        x = self.sum(k)
        if x == 0:  # k以下の要素がないときは-1を返す
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  # sum(p) = sum(k)なるpの左端が答え
            q = p+v
            if q <= self.n and self.tree[q] < x:
                x -= self.tree[q]
                p += v
            v>>=1
        return p+1

    def query(self,k):  # k番目の要素出力
        if k > self.sum(self.n):  # k個以上の要素がないときは-1を返す
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  # sum(p) = kなるpの左端が答え
            q = p+v
            if q <= self.n and self.tree[q] < k:
                k -= self.tree[q]
                p += v
            v>>=1
        return p+1

a = ord('a')

n = readint()
s = [0] + [ord(x)-a for x in readstr()]
q = readint()

avl = [AVL_like_BIT(5*10**5 + 10) for i in range(26)]
for i in range(1,n+1):
    avl[s[i]].add(i)

ans = []
for i in range(q):
    j,l,r = readstrs()
    j = int(j)
    l = int(l)
    if j==1:
        avl[s[l]].delete(l)
        s[l] = ord(r)-a
        avl[s[l]].add(l)
    else:
        r = int(r)
        ans.append(0)
        for k in range(26):
            if avl[k].sum(l-1)-avl[k].sum(r):
                ans[-1]+=1

printrows(ans)

Submission status: Accepted

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

def init():
    #set_val
    #for j in range(26):
    #  for i in range(n):
    #    seg[j][i+num-1]=init_val[i]    
    #built
    for j in range(26):
      for i in range(num-2,-1,-1) :
        seg[j][i]=max(seg[j][2*i+1],seg[j][2*i+2]) 
    
def update(k,x):
    K =k+num-1
    seg[SS[k]][K] = 0
    while K:
        K = (K-1)//2
        seg[SS[k]][K] = max(seg[SS[k]][K*2+1],seg[SS[k]][K*2+2])
    K =k+num-1
    seg[x][K]=1
    while K:
      K=(K-1)//2
      seg[x][K]=max(seg[x][K*2+1],seg[x][K*2+2])
    SS[k]=x
    
def query(p,q):
  a=0
  for i in range(26):
    P =p+ num-1
    Q =q+ num-1
    res=ide_ele
    while Q-P>1:
        if P&1 == 0:
            res = max(res,seg[i][P])
        if Q&1 == 1:
            res = max(res,seg[i][Q])
            Q -= 1
        P = P//2
        Q = (Q-1)//2
    if P == Q:
        res = max(res,seg[i][Q])
    else:
        res = max(max(res,seg[i][P]),seg[i][Q])
    a=a+res
  print(a)
  return a

n=int(input())
S=input()
q=int(input())


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

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


SS=[0]*num
for i in range(n):
  seg[ord(S[i])-97][i+num-1]=1
  SS[i]=ord(S[i])-97
#print(SS)
#print(seg)
init()
#print(seg)

for xx in range(q):
  SSS=list(input().split())
  #print(SSS)
  if SSS[0]=="1":
    #print(int(SSS[1])-1,ord(SSS[2])-97)
    update(int(SSS[1])-1,ord(SSS[2])-97)
  else:
    query(int(SSS[1])-1,int(SSS[2])-1)
#print(seg)

Submission status: Accepted

Solution code:

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

#初期化
ind=1
while 2**ind<=n:
    ind+=1
s+="*"*(2**ind-n)
seg=[]
seg2=[]

from collections import deque
tmp=deque([s])
while len(tmp)>0:
    t=tmp.popleft()
    cnt=0
    for ss in t:
        if ss!="*":
            cnt=cnt|2**(ord(ss)-97)
    seg.append(cnt)
    seg2.append(t)
    if len(t)>1:
        tmp.append(t[:len(t)//2])
        tmp.append(t[len(t)//2:])

#セグ木が出来た！
#print(seg)
#print(seg2)

q=int(input())

def change(i,s):
    #i文字目をsに変更する
    #nの親は(n-1)//2
    #nの子は2n+1,2n+2
    global n,seg,ind
    ii=len(seg)-2**ind+i-1
    seg[ii]=2**(ord(s)-97)
    p=(ii-1)//2
    while 1:
        seg[p]=seg[2*p+1]|seg[2*p+2]
        if p==0:
            break
        p=(p-1)//2

    #print(seg)

from collections import deque


def count(l,r):
    global n,seg,s
    #nの親は(n-1)//2
    #nの子は2n+1,2n+2

    d = deque([(1,len(s),0)])
    ans=0

    while len(d)>0:
        tmp=d.popleft()
        #print(tmp)
        ll,rr,i=tmp[0],tmp[1],tmp[2]
        if l<=ll and rr<=r:
            ans=ans|seg[i]
        elif (ll<=l and l<=rr) or (ll<=r and r<=rr):
            d.append((ll,ll+(rr-ll)//2,2*i+1))
            d.append((ll+(rr-ll)//2+1,rr,2*i+2))

    return str(bin(ans)).count("1")


result=[]


for _ in range(q):
    b,i,c=map(str,input().split())
    if b=="1":
        #i文字目をcに変更
        change(int(i),c)
    else:
        #l文字目からr文字目までに含まれる数
        result.append(count(int(i),int(c)))

for item in result:
    print(item)

Submission status: Accepted

Solution code:
import bisect
import sys
sys.setrecursionlimit(10**9)

def main():
    N = int(input())
    S = list(input())

    a_ord = ord('a')
    z_ord = ord('z')

    set_list = [[] for _ in range(z_ord+1)]
    for i in range(N):
        s = S[i]
        set_list[ord(s)].append(i)

    Q = int(input())
    for q in range(Q):
        ipt = input().split()
        if ipt[0] == "1":
            i,c = int(ipt[1]), ipt[2]
            j = ord(S[i-1])

            if j == ord(c): continue
            set_list[j].remove(i-1)
            bisect.insort_left(set_list[ord(c)],i-1)
            S[i-1] = c
            # print(set_list[])

        else:
            l,r = int(ipt[1]), int(ipt[2])
            ans = 0
            # if l == r:
            #     print(1)
            #     continue

            for i in range(a_ord,z_ord+1):
                st = set_list[i]
                if not len(st) > 0: continue

                # print(i,set_list[i])
                l_p = bisect.bisect_left(st,l-1)
                r_p = bisect.bisect_right(st,r-1)

                # print(l-1,r-1,l_p,r_p)
                if l_p < r_p:
                    ans += 1

            # print(ans,"____")
            print(ans)



if __name__ == "__main__":
  main()

Submission status: Accepted

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

    ordA = ord('a')

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

    idEle = 0
    def _binOpe(x, y):
        return x | y
    def makeSegTree(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [idEle] * (2*numPow2)
        return data, numPow2
    def setInit(As):
        for iST, A in enumerate(As, numPow2):
            data[iST] = A
        for iST in reversed(range(1, numPow2)):
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def _update1(iA, A):
        iST = iA + numPow2
        data[iST] = A
    def update(iA, A):
        _update1(iA, A)
        iST = iA + numPow2
        while iST > 1:
            iST >>= 1
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def getValue(iSt, iEn):
        L = iSt + numPow2
        R = iEn + numPow2
        ans = idEle
        while L < R:
            if L & 1:
                ans = _binOpe(ans, data[L])
                L += 1
            if R & 1:
                R -= 1
                ans = _binOpe(ans, data[R])
            L >>= 1
            R >>= 1
        return ans

    data, numPow2 = makeSegTree(N)

    As = [(1<<no) for no in nos]
    setInit(As)

    anss = []
    for _ in range(Q):
        tp, v1, v2 = input().split()
        if tp == '1':
            pos = int(v1)-1
            c = ord(v2)-ordA
            update(pos, 1<<c)
        else:
            L, R = int(v1)-1, int(v2)-1
            v = getValue(L, R+1)
            ans = bin(v).count('1')
            anss.append(ans)

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


solve()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
class SegmentTree:
    #for pypy
    #treeは1-based-index
    __slots__=["size","func","default_val","tree","first_idx"]
    def __init__(self,initial_value_list,func,default_val,first_index=0):
        n=len(initial_value_list)
        self.first_idx=first_index
        self.size=1<<(n-1).bit_length()
        self.func=func#適用関数
        self.default_val=default_val#初期値
        self.tree=[default_val for i in range(2*self.size)]
        # 木の構築
        for i in range(n):
            d=[0]*26;d[initial_value_list[i]-97]=1
            self.tree[self.size+i]=d
        for i in range(self.size-1,0,-1):
            self.tree[i]=self.func(self.tree[2*i],self.tree[2*i+1])

    def update(self,k,x):
        k+=self.size-self.first_idx
        self.tree[k]=x
        while k>1:
            k>>=1
            self.tree[k]=self.func(self.tree[2*k],self.tree[2*k+1])
    def query(self, l, r):
        l+=self.size-self.first_idx
        r+=self.size-self.first_idx
        lret,rret=self.default_val,self.default_val
        while l<r:
            if l&1:
                lret=self.func(lret,self.tree[l])
                l+=1
            if r&1:
                r-=1
                rret=self.func(self.tree[r], rret) # モノイドでは可換律は保証されていないので演算の方向に注意
            l>>=1
            r>>=1
        return self.func(lret, rret)
n=int(input())
def add(x,y):
    v=[0]*26
    for i in range(26):
        v[i]=x[i]+y[i]
    return v
seg=SegmentTree(list(input().rstrip()),add,[0]*26,1)
q=int(input())

for i in range(q):
    a,s,d=input().split()
    if int(a)==1:
        s=int(s)
        v=[0]*26;v[int.from_bytes(d,'big')-97]+=1
        seg.update(s,v)
        
    else:
        r=seg.query(1,int(s))
        l=seg.query(1,int(d)+1)
        
        ans=0
        for i in range(26):
            if l[i]>r[i]:ans+=1
        print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import or_


def read():
    N = int(input().strip())
    S = input().strip()
    Q = int(input().strip())
    return N, S, Q


class SegmentTree():
    
    def __init__(self, size, op=min, init_value=10**8):
        """初期化"""
        self.size = size
        self.op = op
        self.init_value = init_value
        n = 2 ** ((size-1).bit_length())
        treesize = n * 2
        st = [init_value for i in range(treesize)]
        self.st = st

    @classmethod
    def from_array(cls, a, op=min, init_value=10**8):
        st = cls(len(a), op=op, init_value=init_value)
        for i, x in enumerate(a):
            st.update(i, x)
        return st

    def update(self, key, value):
        """値の更新"""
        offset = len(self.st) // 2
        k = offset + key
        self.st[k] = value
        k >>= 1
        while k > 0:
            self.st[k] = self.op(self.st[k * 2], self.st[k * 2 + 1])
            k >>= 1

    def _query_bottomup(self, a, b):
        """区間[a, b) に対する累積操作
        """
        offset = len(self.st) // 2
        a += offset
        b += offset - 1
        s = self.init_value
        while a < b:
            if a & 1 == 1:
                s = self.op(s, self.st[a])
                a += 1
            a >>= 1
            if b & 1 == 0:
                s = self.op(s, self.st[b])
                b -= 1
            b >>= 1
        if a == b:
            s = self.op(s, self.st[a])
        return s

    def _query_topdown(self, a, b, k, l, r):
        """区間[a, b) に対する累積操作
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        if r <= a or b <= l:
            return self.init_value
        if a <= l and r <= b:
            return self.st[k]
        mid = (l + r) // 2
        lv = self._query_topdown(a, b, k * 2, l, mid)
        rv = self._query_topdown(a, b, k * 2 + 1, mid, r)
        return self.op(lv, rv)

    def query(self, a, b):
        """区間[a, b) に対する累積操作"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        return self._query_topdown(a, b, k=1, l=0, r=len(self.st)//2)
        # return self._query_bottomup(a, b)


def solve_online(N, S, Q):
    tree = SegmentTree(N, op=or_, init_value=0)
    C = [ord(s) - ord("a") for s in S]
    for i in range(N):
        c = ord(S[i]) - ord("a")
        tree.update(i, 1 << c)

    for _ in range(Q):
        op, a, b = input().strip().split()
        if op == "1":
            i, c = int(a)-1, ord(b) - ord("a")
            tree.update(i, 1 << c)
        elif op == "2":
            l, r = int(a)-1, int(b)-1
            b = tree.query(l, r+1)
            s = 0
            while b > 0:
                if b & 1 == 1:
                    s += 1
                b >>= 1
            print(s)


if __name__ == '__main__':
    inputs = read()
    outputs = solve_online(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

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


ide_ele = 0


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """

    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


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

ls = []

for ch in s:
    ls.append(1 << (ord(ch) - 97))

seg = SegTree(ls, segfunc, ide_ele)

for i in range(q):
    que = input().split()
    if que[0] == '1':
        iq = int(que[1])
        cq = que[2]
        seg.update(iq-1, 1 << (ord(cq) - 97))
    else:
        lq = int(que[1])
        rq = int(que[2])
        ret = seg.query(lq-1, rq)
        print(str(bin(ret)).count('1'))

Submission status: Accepted

Solution code:
import sys
import math
import bisect
def input():
    return sys.stdin.readline()[:-1]

n=int(input())
s=list(input())
q=int(input())
ans=[]
dic = {}

for i in range(97,97+26):
    dic[chr(i)]=[]

for num,i in enumerate(s):
    dic[i].append(num)

for i in range(q):
    num,l,r = map(str,input().split())
    if int(num)==1:
        l=int(l)-1
        if s[l] == r:
            continue
        else:
            dic[s[l]].pop(bisect.bisect_left(dic[s[l]],l))
            bisect.insort_left(dic[r],l)
            s[l] = r
    else:
        cnt=0
        l=int(l)
        r=int(r)
        for li in dic.values():
            ind = bisect.bisect_left(li,l-1)
            if ind>=len(li):continue
            if li[ind]<=r-1:
                cnt+=1
        ans.append(cnt)

print(*ans,sep="\n")

Submission status: Accepted

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

'''
'init(a)': 配列aで初期化。O(N)
'update(k,x)': a[k]をxに変更 O(logN)
'query(p,q)': [p,q)について "segfunc" したものを返す O(logN)
'ide_ele' : 単位元。
'''

#####segfunc######


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


init_val = []
for s in S:
    init_val.append(1 << (ord(s)-ord('a')))
init(init_val)

for _ in range(Q):
    t, s, u = input().split()
    if t == '1':
        update(int(s)-1, 1 << (ord(u)-ord('a')))
    else:
        print(bin(query(int(s)-1, int(u))).count('1'))

Submission status: Accepted

Solution code:
import sys
import bisect

N = int(sys.stdin.readline().rstrip())
S = list(sys.stdin.readline().rstrip())
Q = int(sys.stdin.readline().rstrip())

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

for i, s in enumerate(S):
    idx[s].append(i + 1)

for _ in range(Q):
    t, i, c = sys.stdin.readline().rstrip().split()
    i = int(i)
    if t == "1":
        if S[i - 1] != c:
            idx[S[i - 1]].remove(i)
            bisect.insort(idx[c], i)
            S[i - 1] = c
    else:
        c = int(c)
        ans = 0
        for a, id in idx.items():
            x = bisect.bisect_left(id, i)
            y = bisect.bisect_right(id, c)
            if y - x:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect
import copy

N = int(sys.stdin.readline().rstrip())
S = list(sys.stdin.readline().rstrip())
Q = int(sys.stdin.readline().rstrip())

cnt = [0] * 26
cumcnt = [cnt]

for i, s in enumerate(S):
    tmp = copy.copy(cumcnt[i])
    tmp[ord(s) - ord("a")] += 1
    cumcnt.append(tmp)

q_remove = {}
q_add = {}

for _ in range(Q):
    t, i, c = sys.stdin.readline().rstrip().split()
    t = int(t)
    i = int(i)
    d = S[i - 1]
    if t == 1:
        if d != c:
            if d not in q_remove.keys():
                q_remove[d] = [i]
            else:
                bisect.insort(q_remove[d], i)
            if c not in q_add.keys():
                q_add[c] = [i]
            else:
                bisect.insort(q_add[c], i)
            S[i - 1] = c 
    else:
        c = int(c)
        cnt_l = copy.copy(cumcnt[i - 1])
        cnt_r = copy.copy(cumcnt[c])
        for q, idx in q_add.items():
            x = bisect.bisect_right(idx, i - 1)
            y = bisect.bisect_right(idx, c)
            cnt_l[ord(q) - ord("a")] += x
            cnt_r[ord(q) - ord("a")] += y
        for q, idx in q_remove.items():
            x = bisect.bisect_right(idx, i - 1)
            y = bisect.bisect_right(idx, c)
            cnt_l[ord(q) - ord("a")] -= x
            cnt_r[ord(q) - ord("a")] -= y
        ans = 0
        for l, r in zip(cnt_l, cnt_r):
            if r - l > 0:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
class SEGTree:
    def __init__(self,n):
        self.Unit=0
        i=1
        while(i<n):
            i*=2
        self.SEG=[self.Unit]*(2*i-1)
        self.d=i
    def update(self,i,x):
        i+=self.d-1
        self.SEG[i]=1<<x
        while i>0:
            i=(i-1)//2
            self.SEG[i]=self.SEG[i*2+1]|self.SEG[i*2+2]
    def find(self,a,b,k,l,r):
        if r<=a or b<=l:
            return self.Unit
        if a<=l and r<=b:
            return self.SEG[k]
        else:
            c1=self.find(a,b,2*k+1,l,(l+r)//2)
            c2=self.find(a,b,2*k+2,(l+r)//2,r)
            return c1|c2
    def get(self,a,b):
        return self.find(a,b,0,0,self.d)
def bitcnt(x):
    res=0
    while x>0:
        if x&1:
            res+=1
        x//=2
    return res

n=int(input())
s=input()
q=int(input())
seg=SEGTree(n)
for i in range(n):
    seg.update(i,ord(s[i])-97)
for i in range(q):
    q,x,y=input().split()
    if q=='1':
        seg.update(int(x)-1,ord(y)-97)
    else:
        x,y=int(x)-1,int(y)
        bit=seg.get(x,y)
        print(bitcnt(bit))

Submission status: Accepted

Solution code:
def main():
    global s,ide_ele,num,seg
    n = int(input())
    s = list(input())
    for i in range(n):
        s[i] = ord(s[i])-97
    ide_ele = 0
    num = 2**(n-1).bit_length()
    seg = [[ide_ele for _ in range(2*num)] for _ in range(26)]
    for i in range(n):
        seg[s[i]][i+num-1] = 1
    for a in range(26):
        for i in range(num-2,-1,-1) :
            seg[a][i] = max(seg[a][2*i+1],seg[a][2*i+2])
    q = int(input())
    for _ in range(q):
        QUERY = list(input().split())
        QUERY[0], QUERY[1] = int(QUERY[0]), int(QUERY[1])
        if QUERY[0] == 1:
            x = ord(QUERY[2])-97
            k = QUERY[1]-1
            pre = s[k]
            s[k] = x
            k += num-1
            seg[pre][k] = 0
            seg[x][k] = 1
            while k:
                k = (k-1)//2
                seg[pre][k] = max(seg[pre][k*2+1],seg[pre][k*2+2])
                seg[x][k] = max(seg[x][k*2+1],seg[x][k*2+2])
        if QUERY[0] == 2:
            P, Q = QUERY[1]-1, int(QUERY[2])
            if Q <= P:
                print(ide_ele)
                break
            P += num-1
            Q += num-2
            ans = ide_ele
            for i in range(26):
                res = ide_ele
                p,q = P,Q
                while q-p > 1:
                    if p&1 == 0:
                        res = max(res,seg[i][p])
                    if q&1 == 1:
                        res = max(res,seg[i][q])
                        q -= 1
                    p = p//2
                    q = (q-1)//2
                if p == q:
                    res = max(res,seg[i][p])
                else:
                    res = max(max(res,seg[i][p]),seg[i][q])
                ans += res
            print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N = ni()
S = ns()
assert len(S) == N
Q = ni()
qs = []
for i in range(Q):
    q = ns().split()
    qs.append(q)


def main():
    orda = ord("a")
    ords = [ord(ch) - orda for ch in S]
    bits = [BIT(N) for _ in range(26)]
    for i, ch in enumerate(ords):
        bits[ch].add(i + 1, +1)  # 1-origin
    for q in qs:
        if q[0] == "1":
            j = int(q[1])  # 1-origin
            nch = ord(q[2]) - orda
            och = ords[j - 1]
            if nch != och:
                ords[j - 1] = nch
                bits[och].add(j, -1)
                bits[nch].add(j, +1)
        else:
            assert q[0] == "2"
            l, r = int(q[1]), int(q[2])  # 1-origin
            n = 0
            for i in range(26):
                b = bits[i]
                if b.sum(r) - b.sum(l - 1) > 0:
                    n += 1
            print(n)


# Binary Indexed Tree (Fenwick Tree)
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


main()

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)

n = int(input())
s = list(input())
q = int(input())
ord_a = ord("a")
queries = [tuple(input().split()) for i in range(q)]
bits = [BIT(n) for i in range(26)]
for k,v in enumerate(s,1):
  bits[ord(v)-ord_a].add(k,1)
for query,i,c in queries:
  if query == "1":
    i = int(i)
    prev = s[i-1]
    if prev != c:
      bits[ord(prev)-ord_a].add(i,-1)
      bits[ord(c)-ord_a].add(i,1)
      s[i-1] = c
  elif query == "2":
    l,r = int(i),int(c)
    res = 0
    for bit in bits:
      if bit.get(r,l-1):
        res += 1
    print(res)

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect_right
import string 

dic = {c:[] for c in string.ascii_lowercase}

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

for i,c in enumerate(s,start=1):
  dic[c].append(i)
  
for i in range(q):
  p,l,r = map(str,input().split())
  if p =='1':
    j = int(l)
    if r == s[j-1]:
      continue
    c = s[j-1]    
    dic[c].pop(bisect_left(dic[c],j))
    dic[r].insert(bisect_left(dic[r],j),j)
    s[j-1] = r
  else:
    ans = 0
    l = int(l)
    r = int(r)
    for c in string.ascii_lowercase:
      pl = bisect_left(dic[c],l)
      if pl < len(dic[c]):
        if dic[c][pl] <= r:
          ans += 1
    print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()

    N0 = 2**(N.bit_length())
    st = [0] * (N0*2)

    def gindex(l, r):
        L = l + N0; R = r + N0
        lm = (L // (L & -L)) // 2
        rm = (R // (R & -R)) // 2
        while L < R:
            if R <= rm:
                yield R - 1
            if L <= lm:
                yield L - 1
            L //= 2; R //= 2
        while L > 0:
            yield L - 1
            L //= 2

    def update(i,s):
        x = 2 ** (ord(s) - ord('a'))
        i += N0-1
        st[i] = x
        while i > 0:
            i = (i-1) // 2
            st[i] = st[i*2+1] | st[i*2+2]

    def query(l,r):
        l += N0
        r += N0
        ret = 0

        while l < r:
            if l % 2:
                ret |= st[l-1]
                l += 1
            if r % 2:
                r -= 1
                ret |= st[r-1]
            l //= 2 ; r //= 2

        return ret


    for i,s in enumerate(sys.stdin.readline().rstrip()):
        update(i+1,s)
    Q = NI()
    for _ in range(Q):
        c,a,b = sys.stdin.readline().split()
        if c == '1':
            update(int(a),b)
        else:
            ret = query(int(a),int(b)+1)
            cnt = 0
            b = 1
            for i in range(26):
                cnt += (b & ret) > 0
                b <<= 1
            print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect

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

alphabet = [chr(ord('a') + i) for i in range(26)]

d = {alphabet[i]: [] for i in range(26)}
for i, a in enumerate(s):
    d[a].append(i)

ans = []
for i in range(q):
    query = input().split()

    if query[0] == '1':
        idx, c = int(query[1]) - 1, query[2]
        if s[idx] == c:
            continue
        d[s[idx]].remove(idx)
        bisect.insort_left(d[c], idx)
        s[idx] = c
    else:
        l, r = int(query[1]) - 1, int(query[2]) - 1
        res = 0
        for c in alphabet:
            if bisect.bisect_right(d[c], r) > bisect.bisect_left(d[c], l):
                res += 1
        ans.append(res)

for i in ans:
    print(i)