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 copy
def main():
  N=int(input())
  S=str(input())
  Q=int(input())
  Q1=[]
  Q2=[]
  Q3=[]
  for i in range(Q):
    i1,i2,i3=map(str,input().split())
    Q1+=[i1]
    Q2+=[i2]
    Q3+=[i3]
  Slist=[]
  for i in range(N):
    Slist+=[S[i]]
  tf=[[0 for  i in range(26)] for i in range(N+1)]
  for i in range(N):
    tf[i+1]=copy.copy(tf[i])
    n=ord(Slist[i])-97
    tf[i+1][n]=tf[i][n]+1
  for i in range(Q):
    if int(Q1[i])==1:
      Slist[int(Q2[i])-1]=Q3[i]
      for i in range(N):
        tf[i+1]=copy.copy(tf[i])
        n=ord(Slist[i])-97
        tf[i+1][n]=tf[i][n]+1
    elif int(Q1[i])==2:
      l=int(Q2[i])-1
      r=int(Q3[i])
      t=0
      for i in range(26):
        if tf[r][i]>tf[l][i]:
          t+=1
      print(t)
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import math

class SegmentTree:
	def update(self, i, x):
		i += self.num_leaves-1
		self.nodes[i] = x
		while i > 0:
			i = (i-1) // 2
			self.nodes[i] = self.monoid(self.nodes[i*2+1],self.nodes[i*2+2])
			
	def query(self,a,b,k=0,l=0,r=None):
		if r is None:
			r = self.num_leaves
		if r <= a or b <= l:
			return None
		if a <= l and r <= b:
			return self.nodes[k]
		else:
			vl = self.query(a,b,k*2+1,l,(l+r)//2)
			vr = self.query(a,b,k*2+2,(l+r)//2,r)
			return self.monoid(vl,vr)
		
	def __init__(self, monoid, values):
		self.monoid = lambda x, y : monoid(x, y) if x is not None and y is not None else (x if x is not None else y)
		self.num_leaves = 2**math.ceil(math.log2(len(values)))
		self.nodes = [None for i in range(self.num_leaves*2-1)]
		for i in range(len(values)):
			self.update(i,values[i])

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

n = int(input())
s = input()
q = int(input())
Q = [input().split() for i in range(q)]

values = [int(math.pow(2,(ord(s[i])-ord('a')))) for i in range(n)]

sgt = SegmentTree(func, values)

for i in range(q):
    a,b,c = Q[i]
    b = int(b)
    if a == "1":
        sgt.update(b-1,int(math.pow(2,(ord(c)-ord('a')))))
    else:
        c = int(c)
        val = sgt.query(b-1,c)
        cnt = 0
        while val > 0:
            if val%2 == 1:
                cnt += 1
            val = val//2
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math

class SegmentTree:
	def update(self, i, x):
		i += self.num_leaves-1
		self.nodes[i] = x
		while i > 0:
			i = (i-1) // 2
			self.nodes[i] = self.monoid(self.nodes[i*2+1],self.nodes[i*2+2])
			
	def query(self,a,b,k=0,l=0,r=None):
		if r is None:
			r = self.num_leaves
		if r <= a or b <= l:
			return None
		if a <= l and r <= b:
			return self.nodes[k]
		else:
			vl = self.query(a,b,k*2+1,l,(l+r)//2)
			vr = self.query(a,b,k*2+2,(l+r)//2,r)
			return self.monoid(vl,vr)
		
	def __init__(self, monoid, values):
		self.monoid = lambda x, y : monoid(x, y) if x is not None and y is not None else (x if x is not None else y)
		self.num_leaves = 2**math.ceil(math.log2(len(values)))
		self.nodes = [None for i in range(self.num_leaves*2-1)]
		for i in range(len(values)):
			self.update(i,values[i])

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

n = int(input())
s = input()
q = int(input())
Q = [input().split() for i in range(q)]

values = [2**(ord(s[i])-ord('a')) for i in range(n)]

sgt = SegmentTree(func, values)

for i in range(q):
    a,b,c = Q[i]
    b = int(b)
    if a == "1":
        sgt.update(b-1,2**(ord(c)-ord('a')))
    else:
        c = int(c)
        val = sgt.query(b-1,c)
        cnt = 0
        while val > 0:
            if val%2 == 1:
                cnt += 1
            val = val//2
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def order(c):
    return 1 << (ord(c) - 97)

def count(n):
    return bin(n).count("1")

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

def main():
    N = int(input())
    S = [x for x in input()]
    Q = int(input())
    L = 2**22
    Seg = [0]*(L*2)

    def update(k, x):
        k += L 
        Seg[k] = x
        while k > 0:
            k = (k - 1) // 2
            Seg[k] = merge(Seg[2*k+1], Seg[2*k+2])
        Seg[0] = merge(Seg[1], Seg[2])

    def find(a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            #print("find*", (a,b,k,l,r), "=",count(Seg[k]))
            return Seg[k]
        vl = find(a, b, 2*k+1, l, (l+r)//2)
        vr = find(a, b, 2*k+2, (l+r)//2, r)
        #print("find_", (a,b,k,l,r), "=",count(merge(vl, vr)))
        return merge(vl, vr)

    # read S, and update tree
    for i in range(N):
        update(i, order(S[i]))
        #print("Seg", *[count(x) for x in Seg])
    #print("Seg=", [count(x) for x in Seg])

    for _ in range(Q):
        q, i, c = input().split()
        if q == '1':
            i = int(i)-1
            if S[i] == c:
                continue
            S[i] = c
            update(i, order(S[i]))
            #print("Seg=", [count(x) for x in Seg])
        else:
            l, r = int(i), int(c)
            #print((l,r))
            print(count(find(l, r+1, 0, 0, L)))
main()

Submission status: Time Limit Exceeded

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

for _ in range(Q):
    d, c1, c2 = list(input().split())

    if int(d) == 1:
#        print("{} {}".format(c1, c2))
        S[int(c1) - 1] = c2[0]
#        print(S)
    else:
        print(len(set(S[int(c1)-1:int(c2)])))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
Q = int(input())
q_l = []
for i in range(Q):
  q_l.append( list(input().split())  ) 

for i in range(Q):
  if int(q_l[i][0]) == 1:
    i_q = int(q_l[i][1])
    c_q = q_l[i][2]
    S = S[:i_q-1] + c_q + S[i_q:]

  #if int(q[0]) == 2:
  else:
    l_q = int(q_l[i][1])
    r_q = int(q_l[i][2])
    S_bubun = S[l_q-1:r_q]
    print(len(set(S_bubun)))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def main():
    n = int(input().strip())
    s = list(input().strip())

    bit = [Counter() for _ in range(n + 1)]

    def query(i):
        result = Counter()
        while i:
            result += bit[i]
            i -= i & -i
        return result
    
    def update(i, cnt):
        while i < len(bit):
            bit[i] += cnt
            i += i & -i

    for i, c in enumerate(s, 1):
        update(i, Counter({c: 1}))

    q = int(input().strip())
    for _ in range(q):
        Q = input().strip().split()
        if Q[0] == "1":
            i, c = int(Q[1]), Q[2]
            if s[i - 1] != c:
                update(i, Counter({s[i - 1]: -1, c: 1}))
                s[i - 1] = c
        else:
            cnt = query(int(Q[2])) - query(int(Q[1]) - 1)
            print(len(cnt))


main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def main():
    n = int(input().strip())
    s = list(input().strip())

    bit = [Counter() for _ in range(n + 1)]

    def query(i):
        result = Counter()
        while i:
            result += bit[i]
            i -= i & -i
        return result
    
    def update(i, cnt):
        while i < len(bit):
            bit[i] += cnt
            i += i & -i

    for i, c in enumerate(s, 1):
        update(i, {c: 1})

    q = int(input().strip())
    for _ in range(q):
        Q = input().strip().split()
        if Q[0] == "1":
            i, c = int(Q[1]), Q[2]
            if s[i - 1] != c:
                update(i, {s[i - 1]: -1, c: 1})
                s[i - 1] = c
        else:
            cnt = query(int(Q[2])) - query(int(Q[1]) - 1)
            print(len(cnt))


main()

Submission status: Time Limit Exceeded

Solution code:
import sys


class SegTreeSet:
    """
    bitフラグで集合を管理するセグメント木

    要素の種類数は特に明示的に与える必要は無いが、まぁ常識の範囲内で
    """

    def __init__(self, n, initial=0):
        """
        :param n: 文字列長
        :param initial: 初期値
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [initial] * (n2 << 1)
        self.initial = initial

    def update(self, i, x):
        """
        i番目の値にxをXOR

        :param i: index(0-indexed)
        :param x: Bit flag for operating bitwise_xor on leaf node
        """
        i += self.offset
        self.tree[i] ^= x
        while i > 1:
            self.tree[i >> 1] = self.tree[i] | self.tree[i ^ 1]
            i >>= 1

    def get_size(self, a, b):
        """
        [a, b)の要素種数を得る

        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.initial

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result |= self.tree[r - 1]
            if l & 1:
                result |= self.tree[l]
                l += 1
            l >>= 1
            r >>= 1

        return bin(result).count('1')


char_mappings = {chr(i + 97): 1 << i for i in range(26)}

n = int(input())
s = input()
s = list(s)
st = SegTreeSet(n)
for i, c in enumerate(s):
    st.update(i, char_mappings[c])
q = int(input())
ans = []
for line in sys.stdin:
    i, j, k = line.rstrip().split()
    if i == '1':
        j = int(j) - 1
        if s[j] == k:
            continue
        b = char_mappings[k] | char_mappings[s[j]]
        st.update(j, b)
        s[j] = k
    else:
        l = int(j) - 1
        r = int(k)
        ans.append(st.get_size(l, r))
print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
#####segfunc######
def segfunc(x,y):
    if x == y == None:
        return set()
    if x == None:
        return y
    if y == None:
        return x
    return x | y
def init(init_val):
    #set_val
    for i in range(len(init_val)):
        seg[i+num-1]=set([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 set()
    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

#####単位元######
n = int(input())
s = list(input())
ide_ele = None
num =2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
init(s[:-1])
q = int(input())
for i in range(q):
    tmp = input()
    a,b,c = tmp[:-1].split()
    if a == "1":
        update(int(b)-1, set([c]))
    else:
        if b == c:
            print(1)
        else:
            print(len(query(int(b)-1,int(c))))

Submission status: Time Limit Exceeded

Solution code:
def swap_char(S, ind, ch):
    S = S[:ind]+ch+S[ind+1:]
    return S

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

query = list(input().split() for _ in range(Q))

one = '1'
two = '2'

for q in query:
    if q[0] == one:
        S = swap_char(S, int(q[1])-1, q[2])
        if DEB: print(S)
    else:
        if DEB: print(S[int(q[1])-1:int(q[2])])
        print(len(set(S[int(q[1])-1:int(q[2])])))

Submission status: Time Limit Exceeded

Solution code:
#####segfunc######
def segfunc(x,y):
    if x == y == None:
        return set()
    if x == None:
        return y
    if y == None:
        return x
    return x | y
def init(init_val):
    #set_val
    for i in range(len(init_val)):
        seg[i+num-1]=set([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 set()
    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

#####単位元######
n = int(input())
s = list(input())
ide_ele = None
num =2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
init(s)
for i in range(int(input())):
    a,b,c = input().split()
    if a == "1":
        update(int(b)-1, set([c]))
    else:
        if b == c:
            print(1)
        else:
            print(len(query(int(b)-1,int(c))))

Submission status: Time Limit Exceeded

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

sc = iter(open(0).read().split())
ni = lambda: int(next(sc))
ns = lambda: next(sc)

N, S, Q = ni(), list(ns()), ni()

B = [BIT(N) for _ in range(26)]
for i, s in enumerate(S, 1):
    B[ord(s) - ord('a')].add(i, 1)

A = []
for _ in range(Q):
    if ni() == 1:
        i, c = ni(), ns()
        B[ord(S[i - 1]) - ord('a')].add(i, -1)
        S[i - 1] = c
        B[ord(c) - ord('a')].add(i, 1)
    else:
        l, r = ni(), ni()
        A.append(sum(b.sum(l - 1) < b.sum(r) for b in B))

print("\n".join(map(str, A)))

Submission status: Time Limit Exceeded

Solution code:
# https://tjkendev.github.io/procon-library/python/range_query/bit.html
# Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
        self.el = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


def main():
    from string import ascii_lowercase
    import sys
    input = sys.stdin.readline

    n = int(input())
    s = [ascii_lowercase.index(c) for c in input().rstrip()]
    q = int(input())

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

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

            prev_ord = s[base1 - 1]
            next_ord = ascii_lowercase.index(next(it))

            bits[prev_ord].add(base1, -1)
            bits[next_ord].add(base1, +1)

            s[base1 - 1] = next_ord

        else:
            # 返答
            start, end = map(int, it)
            res = sum(
                bits[ord].get(start - 1, end) > 0
                for ord in range(26)
            )

            ret.append(res)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
q = int(input())

#seg_tree
def init(n, s):
    num = len(str(bin(n-1))) -2
    seg = [set() for _ in  range(2**(num+1))]
    seg_num = 2**num

    for i in range(n):
        seg[i + seg_num] = set(s[i])

    for i in range(seg_num-1, 0, -1):
        seg[i] = (seg[i*2] | seg[i*2+1])

    return seg, seg_num

def calc_sum(head, tail):
    head += seg_num
    tail += seg_num
    l = []
    while(head <= tail):
        if(head == tail):
            l.append(head)
            break

        if(head % 2 == 1):
            l.append(head)
            head += 1
        head = head //2

        if(tail % 2 == 0):
            l.append(tail)
            tail -= 1
        tail = tail //2

    ans = set()
    for i in l:
        ans = (ans | seg[i])
    ans = len(ans)
    return(ans)

def update(i,s):
    i += seg_num
    seg[i] = {s}
    while(i > 1):
        i = i//2
        seg[i] = (seg[2*i] | seg[2*i+1])

seg,seg_num = init(n,s)

for i in range(q):
    q1,q2,q3 = input().split()
    if(q1 =='1'):
        update(int(q2)-1, q3)
    else:
        q2,q3 = int(q2),int(q3)
        print(calc_sum(q2-1, q3-1))

Submission status: Time Limit Exceeded

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

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

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

query1 = {}
for q in query:
    if q[0] == '1':
        i = int(q[1]) - 1
        c = q[2]
        query1[i] = c
    else:
        list_s = list(S)
        for i in query1:
            list_s[i] = query1[i]
        S = "".join(list_s)
        l = int(q[1]) - 1
        r = int(q[2]) - 1
        print(len(set(S[l:r+1])))
        query1 = {}

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(input())
q=int(input())

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

for i in range(n):
  dct[s[i]].add(i)
  
for i in range(q):
  a, b, c = input().split();
  aa = int(a);
  bb = int(b);
  num = bb-1
  if aa == 1:
    for k, v in dct.items():
      if num in v and c != k:
        dct[c].add(num)
        dct[k].remove(num)
        break
  else:
    res = 0
    st2 = set(list(range(num, int(c))))
    for k, v in dct.items():
      if not st2.isdisjoint(v):
        res = res + 1
    print(res)

Submission status: Time Limit Exceeded

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

tmp = 'abcdefghijklmnopqrstuvwxyz'
n = I()
s = list(input())
cnt = [0]*n
alpha = defaultdict(list)
for i in range(n):
    alpha[s[i]].append(i)

q = I()
f = defaultdict(list)
for _ in range(q):
    num, i, c = input().split()
    i = int(i) - 1
    if int(num) == 1:
        if s[i] == c:
            continue
        r = br(f[s[i]],i)
        f[s[i]] = f[s[i]][:r] + [i] + f[s[i]][r:]
        r = br(alpha[c],i)
        alpha[c] = alpha[c][:r] + [i] + alpha[c][r:]
        s[i] = c
    else:
        cnt = 0
        c = int(c)-1
        for j in range(26):
            l = bl(alpha[tmp[j]],i)
            r = br(alpha[tmp[j]],c)
            L = bl(f[tmp[j]],i)
            R = br(f[tmp[j]],c)
            if r - l - (R - L) > 0:
                cnt += 1
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
import copy
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

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

al=[chr(ord('a') + i) for i in range(26)]
lst={}
erase={}
insert={}
for i in range(26):
    lst[al[i]]=[]
    erase[al[i]]=[]
    insert[al[i]]=[]

for i in range(n):
    lst[s[i]].append(i)

# print(lst)

for i in range(q):
    if query[i][0]=="1":
        one,j,c=query[i]
        j=int(j)
        if s[j-1]!=c:
            erase[s[j-1]].append(j-1)
            erase[s[j-1]].sort()

            insert[c].append(j-1)
            insert[c].sort()
            s=s[:j-1]+c+s[j:]
    else:
        two,l,r=query[i]
        ans=0
        l=int(l)
        r=int(r)
        for i in range(26):
            tmp=0
            tmp+=bisect.bisect_right(lst[al[i]],r-1)-bisect.bisect_left(lst[al[i]],l-1)
            tmp-=bisect.bisect_right(erase[al[i]],r-1)-bisect.bisect_left(erase[al[i]],l-1)
            tmp+=bisect.bisect_right(insert[al[i]],r-1)-bisect.bisect_left(insert[al[i]],l-1)
            if tmp>0:
                ans+=1
        print(ans)
    # print(s)
    # print(erase)
    # print(insert)

Submission status: Time Limit Exceeded

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

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

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

query1 = {}
for q in query:
    if q[0] == '1':
        i = int(q[1]) - 1
        c = q[2]
        query1[i] = c
    else:
        for i in query1:
            S = S[:i] + query1[i] + S[i+1:]
        query1 = {}
        l = int(q[1]) - 1
        r = int(q[2]) - 1
        print(len(set(S[l:r+1])))

Submission status: Time Limit Exceeded

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

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


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

    #評価関数（という言い方であっている？）
    def segfunc(x,y):
        return x|y


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

    #k番目の値をxに更新
    def update(k,x):
        k += num-1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

            
    #[p,q)の区間に対するクエリへの応答
    def query(p,q):
        if q<=p:
            return ide_ele
        p += num-1
        q += num-2
        res=ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res,seg[p])
            if q&1 == 1:
                res = segfunc(res,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res,seg[p])
        else:
            res = segfunc(segfunc(res,seg[p]),seg[q])
        return len(res)


    #####単位元######
    ide_ele = set([])
    """
    ex)
    最小値のセグ木 → +inf
    　　和のセグ木 → 0
    　　積のセグ木 → 1
    　　gcdのセグ木 → 0
"""
     #num:n以上の最小の2のべき乗
    num =2**(N-1).bit_length()
    seg=[ide_ele]*2*num
    init(S)



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

main()

Submission status: Time Limit Exceeded

Solution code:
import string
import numpy
L = len(string.ascii_lowercase)


class BIT:

    def __init__(self, N):
        self.bit = numpy.zeros((N + 1, L), dtype=numpy.int32)
        self.N = N

    def sum_all(self, i, j):
        s = numpy.zeros(L, dtype=numpy.int32)
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        while j > 0:
            s -= self.bit[j]
            j -= j & -j
        return s

    def add(self, i, x, c):
        c = ord(c) - ord('a')
        while i <= self.N:
            self.bit[i][c] += x
            i += i & -i

def solve(N, S, Q, query):
    bits = BIT(N)

    for i, c in enumerate(S):
        bits.add(i + 1, 1, c)

    ans = []
    for q, i, cr in query:
        if q == "1":
            i = int(i)
            if S[i-1] != cr:
                bits.add(i, -1, S[i-1])
                bits.add(i, 1, cr)
                S[i-1] = cr
        else:
            l = int(i)
            r = int(cr)
            diff = bits.sum_all(r, l-1)
            print(str(numpy.count_nonzero(diff)))

if __name__ == "__main__":
    N = int(input())
    S = list(input())
    Q = int(input())

    query = []
    for _ in range(Q):
        query.append(tuple(input().split(" ")))
    solve(N, S, Q, query)

Submission status: Time Limit Exceeded

Solution code:
import string
import numpy
L = len(string.ascii_lowercase)


class BIT:

    def __init__(self, N):
        self.bit = numpy.zeros((N + 1, L), dtype=numpy.int32)
        self.N = N

    def sum_all(self, i):
        s = numpy.zeros(L, dtype=numpy.int32)
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x, c):
        c = ord(c) - ord('a')
        while i <= self.N:
            # if i % 2 == 0:
            self.bit[i][c] += x
            i += i & -i
            # print(i)
            # i = (i - 1) // 2

def solve(N, S, Q, query):
    bits = BIT(N)

    for i, c in enumerate(S):
        bits.add(i + 1, 1, c)

    ans = []
    for q, i, cr in query:
        if q == "1":
            i = int(i)
            if S[i-1] != cr:
                bits.add(i, -1, S[i-1])
                bits.add(i, 1, cr)
                S[i-1] = cr
        else:
            l = int(i)
            r = int(cr)
            diff = bits.sum_all(r) - bits.sum_all(l)
            k = ord(S[l-1]) - ord('a')
            diff[k] += 1
            print(str(numpy.count_nonzero(diff)))

if __name__ == "__main__":
    N = int(input())
    S = list(input())
    Q = int(input())

    query = []
    for _ in range(Q):
        query.append(tuple(input().split(" ")))
    solve(N, S, Q, query)

Submission status: Time Limit Exceeded

Solution code:
class segmentTreeCharCount():
    dat = []
    lenTreeList = -1
    targetChar = None
    depthTreeList = 0
    lenPaddingEntry = 0
    unitDefault = [None, 0]

    def __init__(self):
        pass

    def load(self, l, tc):
        self.targetChar = tc
        # len(l)個よりも大きい2の二乗を得る
        self.lenTreeList = 2 ** (len(l) - 1).bit_length()  # len 5 なら 2^3 = 8
        self.depthTreeList = (len(l) - 1).bit_length()  # 木の段数(0 origin)
        # lenPaddingEntryは[1,2,3,4,5]を与えたなら[1,2,3,4,5,None,None,None]として扱ったので3を返す
        self.lenPaddingEntry = 2 ** (len(l) - 1).bit_length() - len(l)  # 何エントリを補完したか

        self.dat = [self.unitDefault] * (self.lenTreeList * 2)
        # 値のロード
        for i in range(len(l)):
            if l[i] == self.targetChar:
                self.dat[self.lenTreeList - 1 + i] = [l[i], 1]
            else:
                self.dat[self.lenTreeList - 1 + i] = [l[i], 0]
        self.build()

    def funcSegmentValueById(self, nodeId):
        l = self.dat[nodeId * 2 + 1]
        r = self.dat[nodeId * 2 + 2]
        return self.funcSegmentValue(l, r, nodeId)

    # 書く計算をおこなう。
    # この際にはこの計算で境界とするl,r位置であるa,bをいれることで、右端と左端のパディングを行う
    def funcSegmentValue(self, lNode, rNode, parentNodeId):
        # print("funcSegmentValue parentNode={0}".format(parentNodeId))
        # print("L:")
        lchar, lcnt = lNode
        # print(lNode)
        # print("R:")
        rchar, rcnt = rNode
        # print(rNode)

        # l, rに含まれる文字の総量
        ncnt = lcnt + rcnt

        res = [None, ncnt]
        # print("Return{0}".format(res))
        return res

    # char=入っているデータ, cnt, consLeft, consRight, consLen
    def build(self):
        for nodeId in range(self.lenTreeList - 2, -1, -1):
            # 重要：このコードはリストを生成しなおすので代入に直すこと！
            self.dat[nodeId] = self.funcSegmentValueById(nodeId)

    def setValue(self, i, a):
        """
        set a to list[i]
        """
        # print("setValue: {0}, {1}".format(i, a))
        nodeId = (self.lenTreeList - 1) + i

        self.dat[nodeId] = a
        if a == self.targetChar:
            self.dat[nodeId] = [a, 1]
        else:
            self.dat[nodeId] = [a, 0]
        # print("after")
        # print(self.dat[nodeId])

        while nodeId != 0:
            nodeId = (nodeId - 1) // 2
            self.dat[nodeId] = self.funcSegmentValueById(nodeId)

    def querySub(self, a, b, nodeId, l, r):
        """
        [a,b) 区間の親クエリに対するノードnodeへ[l, r)の探索をデリゲート
        区間については、dataの添え字は0,1,2,3,4としたときに、
        [0,3)なら0,1,2の結果を返す
        Noneとなる条件: r <= a or b <= l
        """
        # print("querySub: a={0}, b={1}, nodeId={2}, l={3}, r={4}".format(a, b, nodeId, l, r))

        if (r <= a or b <= l):
            cannotAnswer = (r - l)
            # print(" > None") # これは答えられない数を返すべき
            return [None, 0]
        if a <= l and r <= b:
            # print(" > have: {0} [node = {1}]".format(self.dat[nodeId], nodeId))
            # print(" >     : a={0} <= l={1} and r{2} <= b{3}".format(a,l,r,b))
            res = self.dat[nodeId]
            return res

        # print("querySubcalc: a={0}, b={1}, nodeId={2}, l={3}, r={4}".format(a, b, nodeId, l, r))
        resLeft = self.querySub(a, b, 2 * nodeId + 1, l, (l + r) // 2)
        resRight = self.querySub(a, b, 2 * nodeId + 2, (l + r) // 2, r)
        # print("querySubend: a={0}, b={1}, nodeId={2}, l={3}, r={4}".format(a, b, nodeId, l, r))
        # print(" > L")
        # print("  node{0}: {1}".format(2 * nodeId + 1, resLeft))
        # print(" > R")
        # print("  node{0}: {1}".format(2 * nodeId + 2, resRight))
        # print(resRight)
        res = self.funcSegmentValue(resLeft, resRight, nodeId)
        # print(" > res")
        # print(res)
        return res

    def query(self, a, b):
        return self.querySub(a, b, 0, 0, self.lenTreeList)

    def debugGetSliceStr(self, a, b):
        return "".join(list(map(lambda x: x[0], self.dat[self.lenTreeList - 1 + a:self.lenTreeList - 1 + b])))

n = int(input())
s = input()
sl = list(s)
st = []
for i in range(26):
    elem = segmentTreeCharCount()
    c = chr(ord("a") + i)
    elem.load(sl, c)
    st.append(elem)
    #print(elem.query(0, n))
# 0個目が数
#print(st[0].query(0, n)[0])
q = int(input())
for _ in range(q):
    ty, x, y = input().split()
    x = int(x)
    if ty == "1":
        cnum = ord(y[0]) - ord("a") # indexを得る
        for i in range(26):
            st[i].setValue(x - 1, y)
    elif ty == "2":
        x = int(x) - 1
        y = int(y)
        res = 0
        #print("x", x, "y", y)
        for i in range(26):
            cnt = st[i].query(x , y)[1]
            #print(st[i].debugGetSliceStr(x, y))
            #print(i, "cnt", cnt)
            if cnt != 0:
                res += 1
        print(res)
    else:
        print("error")