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:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
class SegmentTree:
    def segfunc(self,x,y):
        #ここに評価
        po = [0 for i in range(26)]
        for i in range(26):
            po[i] = x[i]+y[i]
        return po

    #nは総数、initがlist,ide_eleが元
    def __init__(self,n,init,ide_ele):
        self.n = n
        self.ide_ele = ide_ele
        self.num = 2**(n-1).bit_length()
        self.seg = [ide_ele for i in range(2*self.num)]
        for i in range(n):
            self.seg[i+self.num-1] = init[i]
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2])
    
    
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1],self.seg[2*k+2])
    
    def query(self,p,q):
        if q <= p:
            return [1 if i == 0 else 0 for i in range(26)]
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p > 1:
            if p & 1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q & 1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p //= 2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

def solver():
    n = onem()
    s = input().split()[0]
    po = onem()

    abc = [[0 for i in range(26)] for j in range(n)]

    for i in range(n):
        ppp = s[i]
        abc[i][ord(s[i]) - ord('a')] += 1

    Se = SegmentTree(n,abc,[0 for i in range(26)])



    for i in range(po):
        a,b,c = input().split()
        a = int(a)
        b = int(b)
        if a == 1:
            ppp = [0] * 26
            ppp[ord(c) - ord('a')] = 1
            Se.update(b-1,ppp)      
        else:
            c = int(c)
            op = Se.query(b-1,c)
            co = 0
            for i in range(26):
                if op[i] >= 1:
                    co += 1
            print(co)


if __name__ == "__main__":
    solver()

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
class SegmentTree:
    def segfunc(self,x,y):
        #ここに評価
        po = [0 for i in range(26)]
        for i in range(26):
            po[i] = x[i]+y[i]
        return po

    #nは総数、initがlist,ide_eleが元
    def __init__(self,n,init,ide_ele):
        self.n = n
        self.ide_ele = ide_ele
        self.num = 2**(n-1).bit_length()
        self.seg = [ide_ele for i in range(2*self.num)]
        for i in range(n):
            self.seg[i+self.num-1] = init[i]
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2])
    
    
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1],self.seg[2*k+2])
    
    def query(self,p,q):
        if q <= p:
            return [1 if i == 0 else 0 for i in range(26)]
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p > 1:
            if p & 1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q & 1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p //= 2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res


n = onem()
s = input().split()[0]
po = onem()

abc = [[0 for i in range(26)] for j in range(n)]

for i in range(n):
    ppp = s[i]
    abc[i][ord(s[i]) - ord('a')] += 1

Se = SegmentTree(n,abc,[0 for i in range(26)])



for i in range(po):
    a,b,c = input().split()
    a = int(a)
    b = int(b)
    if a == 1:
        ppp = [0 for j in range(26)]
        ppp[ord(c) - ord('a')] = 1
        Se.update(b-1,ppp)      
    else:
        c = int(c)
        op = Se.query(b-1,c)
        co = 0
        for i in range(26):
            if op[i] >= 1:
                co += 1
        print(co)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

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

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

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

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

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

Submission status: Time Limit Exceeded

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

# import numpy as np
# import scipy as scp

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

times = q

strlis = list(s)

def qtype1(strlis,i,c):
    i = int(i)
    if i == len(strlis):
        strlis.pop()
        strlis.append(c)
    elif len(strlis) >= 2:
        strlis = strlis[:i-1] + list(c) + strlis[i:]
    else:
        strlis[i-1] = c
    # print(strlis)
    return strlis

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

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

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

Submission status: Time Limit Exceeded

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

# import numpy as np
# import scipy as scp

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

times = q

strlis = list(s)

def qtype1(i,c):
    i = int(i)
    strlis[i-1] = c

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
import collections

def main():
    n = int(input())

    s = input()

    q = int(input())

    li = [x for x in s]

    d = [[] for i in range(26)]

    for i, x in enumerate(s):
        d[ord(x) - 97].append(i)


    for _ in range(q):
        a, *x = input().split()

        if a == "1":
            i = int(x[0]) - 1
            c = x[1]
            o = ord(li[i]) - 97
            on = ord(c) - 97
            index = bisect.bisect_left(d[o], i)
            d[o].pop(index)
            d[on].insert(bisect.bisect_left(d[on], i), i)
            li[i] = c
        else:
            l = int(x[0]) - 1
            r = int(x[1]) - 1
            cnt = 0
            for v in d:
                if len(v) == 0:
                    continue
                index = bisect.bisect_left(v, l)
                if index == len(v):
                    continue
                if v[index] <= r:
                    cnt += 1
            print(cnt)

main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import collections

def main():
    n = int(input())

    s = input()

    q = int(input())

    li = [x for x in s]

    d = {}
    d = collections.defaultdict(lambda:[])

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

    for i, x in enumerate(s):
        d[x].append(i)


    for _ in range(q):
        a, *x = input().split()

        if a == "1":
            i = int(x[0]) - 1
            c = x[1]
            index = bisect.bisect_left(d[li[i]], i)
            d[li[i]].pop(index)
            d[c].insert(bisect.bisect_left(d[c], i), i)
            li[i] = c
        else:
            l = int(x[0]) - 1
            r = int(x[1]) - 1
            cnt = 0
            for v in d.values():
                index = bisect.bisect_left(v, l)
                if index == len(v):
                    continue
                if v[index] <= r:
                    cnt += 1
            print(cnt)

main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

def main():
    n = int(input())

    s = input()

    q = int(input())

    li = [x for x in s]

    d = {}

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

    for i, x in enumerate(s):
        d[x].append(i)


    for _ in range(q):
        a, *x = input().split()

        if a == "1":
            i = int(x[0]) - 1
            c = x[1]
            index = bisect.bisect_left(d[li[i]], i)
            d[li[i]].pop(index)
            d[c].insert(bisect.bisect_left(d[c], i), i)
            li[i] = c
        else:
            l = int(x[0]) - 1
            r = int(x[1]) - 1
            cnt = 0
            for v in d.values():
                if len(v) == 0:
                    continue
                index = bisect.bisect_left(v, l)
                if index == len(v):
                    continue
                if v[index] <= r:
                    cnt += 1
            print(cnt)

main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())

s = input()

q = int(input())

li = [x for x in s]

d = {}

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

for i, x in enumerate(s):
    d[x].append(i)


for _ in range(q):
    a, *x = input().split()

    if a == "1":
        i = int(x[0]) - 1
        c = x[1]
        index = bisect.bisect_left(d[li[i]], i)
        d[li[i]].pop(index)
        d[c].insert(bisect.bisect_left(d[c], i), i)
        li[i] = c
    else:
        l = int(x[0]) - 1
        r = int(x[1]) - 1
        cnt = 0
        for v in d.values():
            if len(v) == 0:
                continue
            index = bisect.bisect_left(v, l)
            if index == len(v):
                continue
            if v[index] <= r:
                cnt += 1
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())

s = input()

q = int(input())

li = [x for x in s]

d = {}

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

for i, x in enumerate(s):
    d[x].append(i)


for _ in range(q):
    a, *x = input().split()

    if a == "1":
        i = int(x[0]) - 1
        c = x[1]
        d[li[i]].remove(i)
        d[c].insert(bisect.bisect_left(d[c], i), i)
        li[i] = c
    else:
        l = int(x[0]) - 1
        r = int(x[1]) - 1
        cnt = 0
        for v in d.values():
            if len(v) == 0:
                continue
            index = bisect.bisect_left(v, l)
            if index == len(v):
                continue
            if v[index] <= r:
                cnt += 1
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import collections

n = int(input())

s = input()

q = int(input())

d = collections.defaultdict(lambda : [])
li = [x for x in s]

for i, x in enumerate(s):
    d[x].append(i)


for _ in range(q):
    a, *x = input().split()

    if a == "1":
        i = int(x[0]) - 1
        c = x[1]
        d[li[i]].remove(i)
        d[c].insert(bisect.bisect_left(d[c], i), i)
        li[i] = c
    else:
        l = int(x[0]) - 1
        r = int(x[1]) - 1
        cnt = 0
        for v in d.values():
            index = bisect.bisect_left(v, l)
            if index == len(v):
                continue
            if v[index] <= r:
                cnt += 1
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input=sys.stdin.readline
n=int(input())
ss=input()
s=[]
for i in ss:
  s.append(ord(i)-ord('a'))
q=int(input())
bit=np.array([[0]*(n+1) for _ in range(26)])
#print(bit)
def upd(at,by,char):
  while at<=n:
    bit[char][at]+=by
    at+=at&-at
def qry(at,char):
  ret=0
  while at>0:
    #print(at,char,end=" inside \n")
    ret+=bit[char][at]
    at-=at&-at
  return ret
for i in range(n):
  upd(i+1,1,s[i])
for _ in range(q):
  t,l,r=input().split()
  t=int(t)
  if t==1:
    # print(t,l,r,end=" inside if")
    i=int(l)
    cq=ord(r)-ord('a')
    prev=s[i-1]
    if prev==cq:
      continue
    upd(i,-1,prev)
    curr=cq
    upd(i,1,curr)
    s[i-1]=cq
    #change ith character to cq  
  else:
    #    print(t,l,r,end=" inside else")
    l=int(l)
    r=int(r)
    ans=0
    for i in range(26):
      if qry(r,i)-qry(l-1,i)>0:
        ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
ss=input()
s=[]
for i in ss:
  s.append(ord(i)-ord('a'))
q=int(input())
bit=[[0]*(n+1) for _ in range(26)]
#print(bit)
def upd(at,by,char):
  while at<=n:
    bit[char][at]+=by
    at+=at&-at
def qry(at,char):
  ret=0
  while at>0:
    #print(at,char,end=" inside \n")
    ret+=bit[char][at]
    at-=at&-at
  return ret
for i in range(n):
  upd(i+1,1,s[i])
for _ in range(q):
  t,l,r=input().split()
  t=int(t)
  if t==1:
    # print(t,l,r,end=" inside if")
    i=int(l)
    cq=ord(r)-ord('a')
    prev=s[i-1]
    if prev==cq:
      continue
    upd(i,-1,prev)
    curr=cq
    upd(i,1,curr)
    s[i-1]=cq
    #change ith character to cq  
  else:
    #    print(t,l,r,end=" inside else")
    l=int(l)
    r=int(r)
    ans=0
    for i in range(26):
      if qry(r,i)-qry(l-1,i)>0:
        ans+=1
    print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

#print(seg_trees[1])
#modify(0, 1, seg_trees[1])
#print(seg_trees[1])
#print(get_sum(0, 3, 0, 0, N2, seg_trees[1]))
#print(get_sum(1, 6, 0, 0, N2, seg_trees[1]))
for query in queries:
  type_, i, q = query
  if type_ == "1":
    i = int(i) - 1
    pos = ord(q) - ord("a")
    old = ord(string[i]) - ord("a")
    string[i] = q
    modify_diff(i, 1, seg_trees[pos])
    modify_diff(i, -1, seg_trees[old])
  else:
    l = int(i) - 1
    r = int(q)
    counts = 0
    for i in range(26):
      ret = get_sum(l, r, 0, 0, N2, seg_trees[i])
      counts += (1 if ret > 0 else 0)
    print(counts)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)


class SegTree:
    def __init__(self, s):

        N = len(s)

        self.default = set([None])

        # 簡単のために要素数を2のべき乗にしておく
        _n = N
        self.n = 1
        while (self.n < _n):
            self.n = self.n * 2

        self.tree = [self.default for _ in range(2 * self.n - 1)]

        for i, c in enumerate(s):
            self.update(i, c)

    def update(self, i, x):
        i = i + self.n - 1
        if x in self.tree[i]:
            return
        else:
            self.tree[i] = set([x])

        # 親を更新
        while (i > 0):
            i = (i - 1) // 2
            l = self.tree[i * 2 + 1]
            r = self.tree[i * 2 + 2]
            self.tree[i] = l | r

    def query(
        self,
        query_start,
        query_end,  # exclusive
        i_parent=0,
        parent_start=0,
        parent_end=None  # exclusive
    ):
        if parent_end is None:
            parent_end = self.n
        if (query_end <= parent_start
                or parent_end <= query_start):  # クエリとレンジが重ならない
            return self.default
        elif (query_start <= parent_start
              and parent_end <= query_end):  # クエリがレンジを完全に含む
            return self.tree[i_parent]
        else:
            return self.query(query_start, query_end, 2 * i_parent + 1,
                           parent_start, (parent_start + parent_end) // 2) | \
                self.query(query_start, query_end, 2 * i_parent + 2,
                           (parent_start + parent_end) // 2, parent_end)


def resolve():
    N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    Q = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ

    # N, D = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # h_list = [int(x) for x in sys.stdin.readline().split()]  # 複数int

    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    # v_list = [int(sys.stdin.readline().split()[0]) for _ in range(N)]
    grid = [[x for x in sys.stdin.readline().split()]
            for _ in range(Q)]  # int grid

    seg = SegTree(S)

    for _type, a, b in grid:
        if _type == '1':
            a = int(a) - 1
            seg.update(a, b)

        else:
            a = int(a) - 1
            b = int(b) - 1
            retset = seg.query(a, b + 1)
            if None in retset:
                print(len(retset) - 1)
            else:
                print(len(retset))


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7"""
        output = """3
1
5"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7"""
        output = """3
1
5"""
        self.assertIO(input, output)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
from functools import reduce
size=int(N**.5+(1-1e-9))
a=[0]*N
b=[0]*size
f=lambda v: reduce(lambda x,y:x|y,v,0)
def init(v):
    a=v
    b=[f(a[j*size:(j+1)*size]) for j in range(size)]
    return a,b
def update(i,v):
    a[i]=v
    j=i//size
    b[j]=f(a[j*size:(j+1)*size])
def r_query(l,r):
    L,R=0--l//size,r//size
    if L>=R:
        return f(a[l:r])
    else:
        return f(a[l:L*size]+b[L:R]+a[R*size:r])
def c(n):
    r=0
    while n:
        r+=n&1
        n>>=1
    return r

o=lambda c:ord(c)-ord('a')
bit=[2**i for i in range(26)]
S=input()
Q=int(input())
XYZ=[input().split() for i in range(Q)]
a,b=init([bit[o(c)] for c in S])
for x,y,z in XYZ:
    if x=='1':
        update(int(y)-1,bit[o(z)])
    else:
        print(c(r_query(int(y)-1,int(z))))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
ss=input()
s=[]
for i in ss:
  s.append(ord(i)-ord('a'))
q=int(input())
bit=[[0]*(n+1) for _ in range(26)]
#print(bit)
def upd(at,by,char):
  while at<=n:
    bit[char][at]+=by
    at+=at&-at
def qry(at,char):
  ret=0
  while at>0:
    #print(at,char,end=" inside \n")
    ret+=bit[char][at]
    at-=at&-at
  return ret
for i in range(n):
  upd(i+1,1,s[i])
for _ in range(q):
  t,l,r=input().split()
  t=int(t)
  if t==1:
    # print(t,l,r,end=" inside if")
    i=int(l)
    cq=ord(r)-ord('a')
    prev=s[i-1]
    upd(i,-1,prev)
    curr=cq
    upd(i,1,curr)
    s[i-1]=cq
    #change ith character to cq  
  else:
    #    print(t,l,r,end=" inside else")
    l=int(l)
    r=int(r)
    ans=0
    for i in range(26):
      if qry(r,i)-qry(l-1,i)>0:
        ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(sys.stdin.readline().strip())
s = list(sys.stdin.readline().strip())
q = int(sys.stdin.readline().strip())
for i in range(q):
    a, b ,c = sys.stdin.readline().strip().split()
    if a =="1":
        i = int(b)
        s[i-1] = c
    else:
        l, r = int(b), int(c)
        chars = set(s[l-1:r])
        print(len(chars))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = str(input())
S = []
for x in s:
    S.append(x)
q = int(input())
Q = []
for _ in range(q):
    num, first, second = map(str, input().split())
    num = int(num)
    first = int(first)
    if num == 2:
        second = int(second)
    Q.append([num, first, second])
# print(Q)

for i in range(q):
    # print(S)
    if Q[i][0] == 2:
        now = S[Q[i][1]-1:Q[i][2]]
        set_now = set(now)
        print(len(set_now))
    else:
        S[Q[i][1]-1] = Q[i][2]

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
s = list(str(input().rstrip()))
q = int(input())


class SSQ:
    def __init__(self, n, e):
        # 単位元
        self.e = e
        # num_min:n以上の最小の2のべき乗
        self.num_min = 2**(n-1).bit_length()
        self.seg_min = [self.e]*2*self.num_min

    def update(self, k, x):
        k += self.num_min-1
        self.seg_min[k] = x
        while k:
            k = (k-1)//2
            self.seg_min[k] = self.seg_min[k*2+1] or self.seg_min[k*2+2]

    def query(self, p, q):
        q += 1
        if q <= p:
            return self.e
        p += self.num_min-1
        q += self.num_min-2
        res = self.e
        while q-p > 1:
            if p & 1 == 0:
                res = res or self.seg_min[p]
            if q & 1 == 1:
                res = res or self.seg_min[q]
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = res or self.seg_min[p]
        else:
            res = res or self.seg_min[p] or self.seg_min[q]
        return res

ssqs = [SSQ(n, False) for i in range(26)]

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

out = []
for i in range(q):
    com, x, y = list(input().split())
    if com == '1':
        idx = int(x) - 1
        pre_alph = ord(s[idx]) - ord('a')
        ssqs[pre_alph].update(idx, False)
        s[idx] = y
        alph = ord(y) - ord('a')
        ssqs[alph].update(idx, True)
    else:
        x, y = int(x) - 1, int(y) - 1
        cnt = 0
        for i in range(26):
            cnt += 1 if ssqs[i].query(x, y) else 0
        out.append(str(cnt))
print("\n".join(out))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
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 LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

class SegmentTree:
	def __init__(self,N,S):
		self.N = N
		self.tree = [0]*(2*N-1)
		for i,s in enumerate(S):
			self.update(i,s)
	def update(self,i, x):
		i += self.N-1
		self.tree[i] = 1<<int(ord(x)-97)
		while (i > 0):
			i = (i-1) // 2
			self.tree[i] = self.tree[i*2+1] | self.tree[i*2+2]
	def query(self,a,b,k,l,r):
		if(r<=a or b<=l): return 0
		if (a<=l and r<=b) : return self.tree[k]
		else:
			c1 = self.query( a, b, 2 * k + 1, l, (l+r) // 2)
			c2 = self.query( a, b, 2 * k + 2, (l+r) // 2, r)
			return c1 | c2

def count_one_by_shift(num):
	num = (num & 0x55555555) + ((num & 0xAAAAAAAA) >> 1) 
	num = (num & 0x33333333) + ((num & 0xCCCCCCCC) >> 2)
	num = (num & 0x0F0F0F0F) + ((num & 0xF0F0F0F0) >> 4)
	num = (num & 0x00FF00FF) + ((num & 0xFF00FF00) >> 8)
	num = (num & 0x0000FFFF) + ((num & 0xFFFF0000) >> 16)
	return num

def main():
	n = II()
	S = IS()
	N = 1
	while N < n: N*=2
	st = SegmentTree(N,S)
	Q = II()
	ans = []
	for _ in range(Q):
		op, x, y = sys.stdin.readline().split()
		op = int(op)
		if op==1:
			x=int1(x);
			st.update(x,y)
		else:
			x,y=int1(x),int1(y)
			ans.append(count_one_by_shift(st.query(x,y+1,0,0,N)))
	printV(ans)


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:

class SegTree(object):
    """docstring for SegTree."""
    def __init__(self, l, _n):
        n = 1
        while n<_n:
            n *= 2
        self.n = n
        self.dat = [set() for _ in range(2*n)]
        for i in range(_n):
            self.dat[i+n-1].add(l[i])
        self.init(0)

    def init(self, i):
        if i>=self.n-1:
            return self.dat[i]
        self.dat[i] = self.init(self.left(i)) | self.init(self.right(i))
        return self.dat[i]

    def par(self, i):
        return (i-1)//2

    def left(self, i):
        return 2*i+1

    def right(self, i):
        return 2*i+2

    def update(self, i, x):
        i += self.n-1
        self.dat[i] = x
        while i>0:
            i = self.par(i)
            self.dat[i] = self.dat[self.left(i)] | self.dat[self.right(i)]

    def q(self,a,b,k,l,r):
        if r<=a or b<=l:
            return set()
        if a<=l and r<=b:
            return self.dat[k]
        return self.q(a,b,self.left(k),l,(l+r)//2) | self.q(a,b,self.right(k),(l+r)//2,r)

    def query(self,a,b):
        return self.q(a,b,0,0,self.n)

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

seg = SegTree(s,n)

for i in range(q):
    if ql[i][0]=="1":
        seg.update(int(ql[i][1])-1, set([ql[i][2]]))
    else:
        r = seg.query(int(ql[i][1])-1, int(ql[i][2]))
        print(len(r))

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
s = list(input())
q = int(input())
for x in range(q):
    i, a, b = map(str, input().split())
    if i == '1':
        s[int(a) - 1] = b
    else:
        c = collections.Counter(s[int(a) - 1: int(b)])
        print(len(c))

Submission status: Time Limit Exceeded

Solution code:
n1 = int(input())
s = input()
#print(s)
n2 = int(input())
L1,L2 = [],[]
for i in range(n2):
    a,b,c = map(str,input().split())
    if int(a) == 1:
        s = s[:int(b)-1] + c + s[int(b):]
        #print(s)
    elif int(a) == 2:
        s1 = s[int(b)-1:int(c)]
        #print(s1)
        print(len(set(list(s1))))