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: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    s = [None] + list(input())
    q = int(input())
    alpha = [[] for i in range(26)]
    for i, si in enumerate(s[1:], 1):
        alpha[ord(si)-97].append(i)
    check = lambda x, y, z: [i for i in z if i >= x and i <= y]
    for _ in range(q):
        i, a, b = input().split()
        a = int(a)
        if i == "1":
            alpha[ord(s[a])-97].remove(a)
            alpha[ord(b)-97].append(a)
            s[a] = b
        else:
            cnt = 0
            for i in range(26):
                if alpha[i] and check(a, int(b), alpha[i]):
                    cnt += 1
            print(cnt)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    s = [None] + list(input())
    q = int(input())
    for _ in range(q):
        i, a, b = input().split()
        if i == "1":
            s[int(a)] = b
        else:
            print(len(set(s[int(a):int(b)+1])))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

for i in range(q):
  w = list(input().split())
  if w[0] == '1':
    s[int(w[1])-1] = w[2]
  else :
    p = s[int(w[1])-1:int(w[2])]

    print(len(Counter(p)))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

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

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


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


def lam(x, y):
    ret = [a | b for a, b in zip(x, y)]
    return ret


def a2n(a):
    return ord(a)-ord("a")


def createInp(n):
    return [False if i != n else True for i in range(26)]


Seg = SegmentTree(len(S), lam, init=[0]*26)
for i, s in enumerate(S):
    Seg.set(i, createInp(a2n(s)))
Seg.build()

for q, l, r in queries:
    if q == "1":
        Seg.update(int(l)-1, createInp(a2n(r)))
    else:
        print(sum(Seg.query(int(l)-1, int(r))))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

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

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


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

Seg = SegmentTree(len(S), lambda x, y: x | y, init=set())
for i, s in enumerate(S):
    Seg.set(i, {s})
Seg.build()

for q, l, r in queries:
    if q == "1":
        Seg.update(int(l)-1, {r})
    else:
        print(len(Seg.query(int(l)-1, int(r))))

Submission status: Time Limit Exceeded

Solution code:
def initialize(N):
    i=1
    while i<N:
        i*=2
    return [0]*(2*i-1),i

def update(i,x):
    i+=d-1
    bit=ord(x)-97
    SEG[i]=0 | (1<<bit)
    while i>0:
        i=(i-1)//2
        SEG[i]=SEG[i*2+1]|SEG[i*2+2]
        
def find(a,b,k,l,r):
    if r<=a or b<=l:
        return 0
    if a<=l and r<=b:
        return SEG[k]
    else:
        c1=find(a,b,2*k+1,l,(l+r)//2)
        c2=find(a,b,2*k+2,(l+r)//2,r)
        return c1|c2
        
N=int(input())
S=input()
Q=int(input())

SEG,d=initialize(N)
for i in range(N):
    update(i,S[i])

for i in range(Q):
    com,s,t=map(str,input().split())
    if(com=='1'):
        update(int(s)-1,t)
    else:
        cnt=0
        bit=find(int(s)-1,int(t),0,0,d)
        while(bit>0):
            if(bit&1):
                cnt+=1
            bit//=2
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def update(c,i,x): # x in [1,-1]
    m = i+n
    if x==1:
        while m>0:
            T[c][m][1] += 1
            m = m//2
    else:
        while m>0:
            T[c][m][1] -= 1
            m = m//2
def find(c,m,l,r):
    L,R = T[c][m][0]
    if R<=l or L>=r:
        return 0
    if l<=L and R<=r:
        return T[c][m][1]
    else:
        return find(c,2*m,l,r)+find(c,2*m+1,l,r)
N = int(input())
S = list(input().strip())
Q = int(input())
k = 0
while 2**k<N:
    k += 1
n = 2**k
T = {chr(j):[[] for i in range(2*n)] for j in range(97,123)}
for j in range(97,123):
    for i in range(n,2*n):
        T[chr(j)][i] = [[i-n,i-n+1],0]
    for i in range(n-1,0,-1):
        T[chr(j)][i] = [[T[chr(j)][2*i][0][0],T[chr(j)][2*i+1][0][1]],0]
for i in range(N):
    c = S[i]
    update(c,i,1)
A = [input().split() for _ in range(Q)]
for i in range(Q):
    q = A[i]
    if q[0]=="1":
        i = int(q[1])-1
        c = q[2]
        if S[i]==c:continue
        update(S[i],i,-1)
        update(c,i,1)
        S[i] = c
    else:
        l,r = int(q[1]),int(q[2])
        cnt = 0
        for j in range(97,123):
            if find(chr(j),1,l-1,r)>0:
                cnt += 1
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def update(c,i,x): # x in [1,-1]
    m = i+n
    if x==1:
        while m>0:
            T[c][m][1] += 1
            m = m//2
    else:
        while m>0:
            T[c][m][1] -= 1
            m = m//2
def find(c,m,l,r):
    L,R = T[c][m][0]
    if R<=l or L>=r:
        return 0
    if l<=L and R<=r:
        return T[c][m][1]
    else:
        return find(c,2*m,l,r)+find(c,2*m+1,l,r)
N = int(input())
S = list(input().strip())
Q = int(input())
k = 0
while 2**k<N:
    k += 1
n = 2**k
T = {chr(j):[[] for i in range(2*n)] for j in range(97,123)}
for j in range(97,123):
    for i in range(n,2*n):
        T[chr(j)][i] = [[i-n,i-n+1],0]
    for i in range(n-1,0,-1):
        T[chr(j)][i] = [[T[chr(j)][2*i][0][0],T[chr(j)][2*i+1][0][1]],0]
for i in range(N):
    c = S[i]
    update(c,i,1)
for _ in range(Q):
    q = list(input().split())
    if q[0]=="1":
        i = int(q[1])-1
        c = q[2]
        if S[i]==c:continue
        update(S[i],i,-1)
        update(c,i,1)
        S[i] = c
    else:
        l,r = int(q[1]),int(q[2])
        cnt = 0
        for j in range(97,123):
            if find(chr(j),1,l-1,r)>0:
                cnt += 1
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    #print(r)

def solve():
    K = iip(False)
    S = input()
    S = [ord(i) for i in S]
    Q = iip(False)

    posit = {}
    for i in range(ord("a"), ord("z")+1):
        posit[i] = []

    query = []
    for i in range(Q):
        query.append(input().split())

    for i, j in enumerate(S, 1):
        posit[j].append(i)

    result = []
    for q in query:
        if q[0] == "1":
            p = int(q[1])
            before = S[p-1]
            after = ord(q[2])
            if before == after:
                continue
            S[p-1] = after

            idx = bisect_left(posit[before], p)

            posit[before].pop(idx)
            insort_left(posit[after], p)

        else:
            l = int(q[1])
            r = int(q[2])

            ret = 0
            for i in range(ord("a"), ord("z")+1):
                for v in posit[i]:
                    if r >= v >= l:
                        ret += 1
                        break
            result.append(ret)


    #print(S)
    #print(posit)
    split_print_space(result)

    return



#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    #print(r)

def solve():
    K = iip(False)
    S = input()
    S = [ord(i) for i in S]
    Q = iip(False)

    posit = {}
    for i in range(ord("a"), ord("z")+1):
        posit[i] = []

    query = []
    for i in range(Q):
        query.append(input().split())

    for i, j in enumerate(S, 1):
        posit[j].append(i)

    result = []
    for q in query:
        if q[0] == "1":
            p = int(q[1])
            c = ord(q[2])

            for i in range(ord("a"), ord("z")+1):
                if p in posit[i]:
                    posit[i].remove(p)
            posit[c].append(p)

        else:
            l = int(q[1])
            r = int(q[2])

            ret = 0
            for i in range(ord("a"), ord("z")+1):
                for v in posit[i]:
                    if r >= v >= l:
                        ret += 1
                        break
            result.append(ret)


    #print(S)
    #print(posit)
    split_print_space(result)

    return



#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class SegTreeSum:
    '''
    0-indexedで実装していることに注意
    '''

    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, 0, -1):
            # 親から子ノードへアクセスする
            self.node[i] = self.node[2*i+1] + self.node[2*i+2]
    
    def add(self,i,x):
        i += (self.N - 1)
        self.node[i] += x

        while i > 0:
            i = (i - 1) // 2
            self.node[i] = self.node[2*i+1] + self.node[2*i+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 ctoi(c):
    return ord(c) - ord('a')

def main():
    N = int(input())
    S = list(input())
    Q = int(input())
    Segtree = [SegTreeSum([0] * N) for _ in range(27)]
    for i, c in enumerate(S):
        Segtree[ctoi(c)].add(i,1)

    for _ in range(Q):
        q, *query = map(str, input().split())
        if q == '1':
            i, c = query
            i = int(i) - 1
            Segtree[ctoi(c)].add(i, 1)
            Segtree[ctoi(S[i])].add(i,-1)
            S[i] = c
        else:
            l, r = query
            l = int(l) - 1
            r = int(r)
            ans = 0
            for j in range(27):
                if Segtree[j].getsum(l,r):
                    ans += 1
            print(ans)



    


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
s = list(input())
q = int(input())
for i in range(q):
  que = input().split()
  if que[0] == '1':
    na,mu = que[1],que[2]
    na = int(na)
    s[na-1] = mu
  else:
    na,mu = que[1],que[2]
    na,mu = int(na),int(mu)
    c = set(s[na-1:mu])
    print(len(c))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q = int(input())
for i in range(q):
  que = input().split()
  if que[0] == '1':
    s[int(que[1])-1] = que[2]
  else:
    c = set(s[int(que[1])-1:int(que[2])])
    print(len(c))

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
s = list(input())
Q = int(input())

# print()
# s = s * 10000
# print(len(s))

# @elapsed_time
def convert(s: list, q1: int, q2: str):
    # return s[:q1] + q2 + s[q1+1:]
    s[q1] = q2
    return s


# @elapsed_time
def calc(s: list, q1: int, q2: int):
    res = list(set(s[q1:q2+1]))
    # checks = ['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']
    # print(res)
    return len(res)


for _ in range(Q):
    q, q1, q2 = input().split()
    q = int(q)
    if q == 1:
        s = convert(s, int(q1) - 1, q2)
    if q == 2:
        print(calc(s, int(q1) - 1, int(q2) - 1))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

N = int(input())
s = input()
Q = int(input())


def convert(s: str, q1: int, q2: str):
    return s[:q1] + q2 + s[q1+1:]


def calc(s: str, q1: int, q2: int):
    res = list(set(s[q1:q2+1]))
    # checks = ['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']
    # res = np.array([check(set_s, l) for l in checks])

    # print(res)
    return len(res)


def check(s, check_str: str):
    if s in check_str:
        return 1
    return 0


for _ in range(Q):
    q, q1, q2 = input().split()
    q = int(q)
    if q == 1:
        s = convert(s, int(q1) - 1, q2)
    if q == 2:
        print(calc(s, int(q1) - 1, int(q2) - 1))

Submission status: Time Limit Exceeded

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

class SegmentTree():
    def segfunc(self, x, y):
        return max(x, y)
        
    def __init__(self, ide_ele, n, l, target):
        # n以上の最小の2のべき乗、一番下の段はここからスタートになる
        self.ide_ele = ide_ele
        self.num =2**(n-1).bit_length()
        self.tree = [ide_ele]*self.num*2
        # 一番下の段
        for i in range(n):
            if l[i] == target:
                self.tree[i+self.num-1] = 1
        # 
        for i in range(self.num-2, -1, -1):
            self.tree[i] = self.segfunc(self.tree[2*i+1], self.tree[2*i+2])
    
    def update(self, k, add):
        k += self.num-1
        if add:
            self.tree[k] = 1
        else:
            self.tree[k] = 0
        while k:
            k = (k-1)//2
            self.tree[k] = self.segfunc(self.tree[k*2+1], self.tree[k*2+2])
    
    def query(self, p, q):
        if q<=p:
            return self.ide_ele

        # [p, q)
        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.tree[p])
            if q&1 == 1: #右なのに左端
                res = self.segfunc(res, self.tree[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p==q:
            res = self.segfunc(res, self.tree[p])
        else:
            res = self.segfunc(self.segfunc(res, self.tree[p]), self.tree[q])
        return res

    # 閉区間になってる
    def rec_query(self, p, q, k, l, r):
        #q -= 1 [)の場合
        #print(p, q, k, l, r)
        if r < p or q < l: # out of range
            return self.ide_ele
        if p <= l and r <= q:
            return self.tree[k]
        else:
            vl = self.rec_query(p, q, k*2+1, l, (l+r)//2)
            vr = self.rec_query(p, q, k*2+2, (l+r)//2+1, r)
        #print(vl, vr)
        return self.segfunc(vl, vr)



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

result = ""

d = {}
for i in range(26):
    d[chr(ord("a")+i)] = SegmentTree(0, N, S, chr(ord("a")+i))

for q in range(Q):
    case, p, q = (i for i in input().split())
    #print(case, p, q)
    p = int(p)-1
    case = int(case)
    if case==1:
        #print(p)
        d[S[p]].update(p, False)
        d[q].update(p, True)
        S = S[:p] + q + S[p+1:]
    else:
        ans = 0
        for c in range(26):
            #print(d[chr(ord("a")+c)].tree)
            ans += d[chr(ord("a")+c)].query(p, int(q))
        result += str(ans)+"\n"

#print(S)
print(result[:-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter

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

    char_list = list(S)

    for _ in range(Q):
        Query = list(map(str, input().split()))

        if Query[0] == '1':
            index = int(Query[1]) - 1
            if char_list[index] != Query[2]:
                char_list[index] = Query[2]

        elif Query[0] == '2':
            start = int(Query[1]) - 1
            end = int(Query[2]) - 1
            print(len(Counter(char_list[start:end+1])))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

c_list = [0] * N
for i in range(N):
    c_list[i] = 1 << (ord(S[i]) - 97)

Q = int(input())
for _ in range(Q):
    q = input().split()
    # print(q)

    if q[0] == "1":
        i = int(q[1])
        c = q[2]
        c_list[i - 1] = 1 << (ord(c) - 97)
        # print(c_list)
    elif q[0] == "2":
        l = int(q[1])
        r = int(q[2])
        
        x = 0
        for i in range(l - 1, r):
            x |= c_list[i]
        # print(bin(x))

        x = x - ((x >> 1) & 0b01010101010101010101010101010101)
        x = (x & 0b00110011001100110011001100110011) + ((x >> 2) & 0b00110011001100110011001100110011)
        x = (x + (x >> 4)) & 0b00001111000011110000111100001111
        x = x + (x >> 8)
        x = x + (x >> 16)
        count = x & 0b11111
        print(count)

Submission status: Time Limit Exceeded

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

char_list = []
for i in range(N):
    char_list.append(S[i])


Q = int(input())
for _ in range(Q):
    q = input().split()
    # print(q)

    if q[0] == "1":
        i = int(q[1])
        c = q[2]
        char_list[i - 1] = c
        # print(char_list)
    elif q[0] == "2":
        l = int(q[1])
        r = int(q[2])
        temp_list = char_list[l - 1:r]
        target_set = set(temp_list)
        count = len(target_set)
        print(count)

Submission status: Time Limit Exceeded

Solution code:

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

char_list = []
for i in range(N):
    char_list.append(S[i])


def type1(char_list, i, c):
    char_list[i - 1] = c
    return char_list

def type2(char_list, l, r):
    target_list = char_list[l - 1:r]
    # print(target_list)
    target_set = set(target_list)
    count = len(target_set)
    return count


Q = int(input())
for _ in range(Q):
    q = input().split()
    # print(q)

    if q[0] == "1":
        i = int(q[1])
        c = q[2]
        char_list = type1(char_list, i, c)
        # print(char_list)
    elif q[0] == "2":
        l = int(q[1])
        r = int(q[2])
        count = type2(char_list, l, r)
        print(count)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc157/tasks/abc157_e
import bisect

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

acc = [[] for _ in range(26)]
for i in range(N):
    acc[ord(S[i]) - ord('a')].append(i)

for _ in range(Q):
    TYPE, Q1, Q2 = input().split()
    if TYPE == '1':
        Q1 = int(Q1) - 1
        target = acc[ord(S[Q1]) - ord('a')]
        del target[bisect.bisect_left(target, Q1)]
        S[Q1] = Q2
        bisect.insort_left(acc[ord(S[Q1]) - ord('a')], Q1)

    else:
        Q1, Q2 = int(Q1) - 1, int(Q2)
        ans = 0
        for i in range(26):
            target = acc[i]
            if not target:
                continue

            it = bisect.bisect_left(target, Q1)
            if len(target) <= it:
                continue
            if target[it] < Q2:
                ans += 1

        print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc157/tasks/abc157_e
import bisect

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

acc = [[] for _ in range(26)]
for i in range(N):
    acc[ord(S[i]) - ord('a')].append(i)

for _ in range(Q):
    TYPE, Q1, Q2 = input().split()
    if TYPE == '1':
        Q1 = int(Q1) - 1
        del acc[ord(S[Q1]) - ord('a')][bisect.bisect_left(acc[ord(S[Q1]) - ord('a')], Q1)]
        S[Q1] = Q2
        bisect.insort_left(acc[ord(S[Q1]) - ord('a')], Q1)

    else:
        Q1, Q2 = int(Q1) - 1, int(Q2)
        ans = 0
        for i in range(26):
            target = acc[i]
            if not target:
                continue
            it = bisect.bisect_left(target, Q1)
            if len(target) <= it:
                continue
            if target[it] < Q2:
                ans += 1

        print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc157/tasks/abc157_e
import bisect

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

acc = [[] for _ in range(26)]
for i in range(N):
    bisect.insort_left(acc[ord(S[i]) - ord('a')], i)

for _ in range(Q):
    TYPE, Q1, Q2 = input().split()
    if TYPE == '1':
        Q1 = int(Q1) - 1
        del acc[ord(S[Q1]) - ord('a')][bisect.bisect_left(acc[ord(S[Q1]) - ord('a')], Q1)]
        S[Q1] = Q2
        bisect.insort_left(acc[ord(S[Q1]) - ord('a')], Q1)

    else:
        Q1, Q2 = int(Q1) - 1, int(Q2)
        ans = 0
        for i in range(26):
            target = acc[i]
            if not target:
                continue
            it = bisect.bisect_left(target, Q1)
            if len(target) <= it:
                continue
            if target[it] < Q2:
                ans += 1

        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
S = list(input())
Q = int(input())
for i in range(Q):
    a, b, c = map(str, input().split())
    if a == "1":
        S[int(b)-1] = c
    else:
        print(len(collections.Counter(S[int(b)-1:int(c)])))

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc157/tasks/abc157_e

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

for _ in range(Q):
    TYPE, Q1, Q2 = input().split()
    if TYPE == '1':
        Q1 = int(Q1)
        S[Q1 - 1] = Q2
    else:
        Q1, Q2 = int(Q1), int(Q2)
        print(len(set(S[Q1 - 1:Q2])))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q = int(input())
 
for i in range(q):
    tmp = input().split()
        
    if int(tmp[0]) != 1:
        a,b,c = map(int, tmp)
        
        print(len(set(s[b-1:c])))
        
    else:
        a,b,c = map(str, tmp)
        b = int(b)
        s[b-1] = c

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input().strip())
Qcnt = int(input())

cidx = {}
for i in range(ord("a"), ord("z")+1):
    cidx[chr(i)] = set([])

import bisect

for idx, s in enumerate(S):
    cidx[s].add(idx)

for _ in range(Qcnt):
    Q = list(input().strip().split(" "))
    if Q[0] == "1":
        q_idx = int(Q[1]) - 1
        prev_c = S[q_idx]
        S[q_idx] = Q[2]
        cidx[prev_c].remove(q_idx)
        cidx[Q[2]].add(q_idx)
    else:
        l = int(Q[1])
        r = int(Q[2])
        l -= 1
        cnt = 0
        for alpha in range(ord("a"), ord("z")+1):
            tmp = sorted(list(cidx[chr(alpha)]))
            lid = bisect.bisect_left(tmp, l)
            rid = bisect.bisect_left(tmp, r)
            if lid < rid:
                cnt += 1
        print(cnt)