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 numpy as np
n1 = int(input())
s = np.array(list(input()))
#print(s)
n2 = int(input())
for i in range(n2):
    a,b,c = map(str,input().split())
    if int(a) == 1:
        s[int(b)-1] = c
        #print(s)
    elif int(a) == 2:
        s1 = np.array(s[int(b)-1:int(c)])
        #print(s1)
        print(len(set(list(s1))))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:

    def __init__(self, n, fn=lambda x, y: min(x, y), unity=(1 << 31) - 1):
        self.n = 1
        while self.n < n:
            self.n *= 2

        self.arr = [unity] * (2 * self.n - 1)
        self.fn = fn
        self.unity = unity

    def update(self, i, x):
        k = self.n + i - 1
        self.arr[k] = x

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

    def query(self, l, r):
        return self._inner_query(l, r, 0, 0, self.n)

    def _inner_query(self, l, r, k, il, ir):
        if ir <= l or r <= il:
            return self.unity

        elif l <= il and ir <= r:
            return self.arr[k]

        vl = self._inner_query(l, r, k * 2 + 1, il, (il + ir) // 2)
        vr = self._inner_query(l, r, k * 2 + 2, (il + ir) // 2, ir)
        return self.fn(vl, vr)

    def __str__(self):
        return self.arr[0: 2 * self.n].__str__()

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

segs = [SegmentTree(N, lambda x, y: x + y, 0) for _ in range(26)]

L = len(S)

for i in range(L):
    x = ord(S[i]) - 97
    segs[x].update(i, 1)

for i in range(Q):
    m, a, b = input().split()

    if m == "1":
        a = int(a) - 1
        b = ord(b) - 97
        for i in range(26):
            segs[i].update(a, 0)
        segs[b].update(a, 1)
    else:
        a = int(a) - 1
        b = int(b)
        cnt = 0
        for i in range(26):
            cnt += 1 if segs[i].query(a, b) > 0 else 0
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:

    def __init__(self, n, fn=lambda x, y: min(x, y), unity=(1 << 31) - 1):
        self.n = 1
        while self.n < n:
            self.n *= 2

        self.arr = [unity] * (2 * self.n - 1)
        self.fn = fn
        self.unity = unity

    def update(self, i, x):
        k = self.n + i - 1
        self.arr[k] = x

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

    def query(self, l, r):
        return self._inner_query(l, r, 0, 0, self.n)

    def _inner_query(self, l, r, k, il, ir):
        if ir <= l or r <= il:
            return self.unity

        elif l <= il and ir <= r:
            return self.arr[k]

        vl = self._inner_query(l, r, k * 2 + 1, il, (il + ir) // 2)
        vr = self._inner_query(l, r, k * 2 + 2, (il + ir) // 2, ir)
        return self.fn(vl, vr)

    def __str__(self):
        return self.arr[0: 2 * self.n].__str__()

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

segs = [SegmentTree(N, lambda x, y: x + y, 0) for _ in range(26)]

L = len(S)

for i in range(L):
    x = ord(S[i]) - 97
    segs[x].update(i, 1)

for i in range(Q):
    m, a, b = input().split()

    if m == "1":
        a = int(a) - 1
        b = ord(b) - 97
        for i in range(26):
            segs[i].update(a, 0)
        segs[b].update(a, 1)
    else:
        a = int(a) - 1
        b = int(b)
        cnt = 0
        for i in range(26):
            cnt += 1 if segs[i].query(a, b) > 0 else 0
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import sys
input = sys.stdin.readline


class SegmentTrees:
    def __init__(self, target, no_effect):
        size = len(target)
        length = 1
        while length < size:
            length *= 2
        self.tree_size = length * 2 - 1
        self.tree = [no_effect] * self.tree_size
        self.areas = [[0, 0] for _ in range(self.tree_size)]
        self.set_areas()
        self.initialize_tree_by_target(target, no_effect)
        self.target = target

    def set_areas(self):
        def decide_children_areas(node):
            left, right = self.areas[node]
            center = (left+right)//2
            child1 = node * 2 + 1
            child2 = node * 2 + 2
            self.areas[child1] = [left, center]
            self.areas[child2] = [center+1, right]

        self.areas[0] = [0, self.tree_size//2]
        for parent in range(self.tree_size//2):
            decide_children_areas(parent)

    @classmethod
    def initialize_func(cls, value):
        return {value}

    @classmethod
    def merge_func(cls, a, b):
        return a | b

    def merge_child_data(self, node):
        child1 = node * 2 + 1
        child2 = node * 2 + 2
        merged = self.merge_func(self.tree[child1], self.tree[child2])
        return merged

    def initialize_tree_by_target(self, target: list, no_effect=0):
        def calc_leafs():
            initial_leaf = self.tree_size//2
            leafs = range(initial_leaf, initial_leaf+len(target))
            for value, leaf in zip(target, leafs):
                self.tree[leaf] = self.initialize_func(value)

            residue = range(initial_leaf+len(target), self.tree_size)
            for residual_leaf in residue:
                self.tree[residual_leaf] = no_effect

        calc_leafs()
        for parent in range(self.tree_size//2-1, -1, -1):
            self.tree[parent] = self.merge_child_data(parent)

    def update(self, new_data, position):
        leaf = self.tree_size//2 + position
        new = self.initialize_func(new_data)
        if self.tree[leaf] == new:
            return
        self.tree[leaf] = new
        parent = (leaf-1) // 2
        while parent >= 0:
            new = self.merge_child_data(parent)
            if self.tree[parent] == new:
                break
            self.tree[parent] = new
            parent = (parent-1) // 2

    def get_query(self, _from, to):
        def get_tree_data(node):
            left, right = self.areas[node]
            if _from <= left and right <= to:
                result.append(self.tree[node])
                return
            if to < left or right < _from:
                return

            child1 = node * 2 + 1
            child2 = node * 2 + 2
            get_tree_data(child1)
            get_tree_data(child2)

        result = []
        get_tree_data(0)
        ans = reduce(self.merge_func, result)
        ans = len(ans)
        return ans


n = int(input())
S = input().replace('\n', '')
seg_tree = SegmentTrees(target=S, no_effect=set())

Q = int(input())
for _ in range(Q):
    query = input().split()
    if query[0] == '1':
        position, new = int(query[1])-1, query[2]
        seg_tree.update(new, position)

    elif query[0] == '2':
        _from, to = int(query[1])-1, int(query[2])-1
        print(seg_tree.get_query(_from, to))

Submission status: Time Limit Exceeded

Solution code:
class segtree():
    def segfunc(x,y):
        return min(x,y)
    #####単位元######
    ide_ele = -1
    n=1
    init_val=[0]*n
    #num:n以上の最小の2のべき乗
    num =2**(n-1).bit_length()
    seg=[ide_ele]*2*num
    
    def __init__(self,INIT_VAL,SEGFUNC,IDE_ELE):
        self.ide_ele=IDE_ELE
        self.init_val=[i for i in INIT_VAL]
        self.segfunc=SEGFUNC
        self.n=len(self.init_val)
        self.num =2**(self.n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num
 
        #set_val
        for i in range(self.n):
            self.seg[i+self.num-1]=self.init_val[i]    
        #built
        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+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        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 = 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 debug(self):
        print([self.query(i,i+1) for i in range(N)])

N=int(input())
S=list(input())
addfunc=lambda x,y:x+y
Seg=[segtree([0]*N,addfunc,0) for i in range(26)]
for i in range(N):
    Seg[ord(S[i])-97].update(i,1)

Q=int(input())
for line in range(Q):
    query=input().split()
    if query[0]=="1":
        iq=int(query[1])-1
        cq=query[2]
        Seg[ord(S[iq])-97].update(iq,0)
        Seg[ord(cq)-97].update(iq,1)
        S[iq]=cq
    else:
        lq=int(query[1])-1
        rq=int(query[2])
        ans=0
        for i in range(26):
            if Seg[i].query(lq,rq)>0:
                ans+=1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

class SegmentTree():
    def __init__(self, n, init_val, segfunc, unifunc):
        self.n = n
        self.size = 2**(n-1).bit_length()
        self.segfunc = segfunc
        self.unifunc = unifunc

        self.seg = [unifunc() for _ in range(2*self.size)]

        for i in range(self.n):
            self.seg[i+self.size-1] = init_val[i]

        for i in range(self.size-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.size-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])

    def query(self, p, q): # [p, q)
        if q <= p:
            return self.unifunc()
        p += self.size-1
        q += self.size-2
        res = self.unifunc()

        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 = 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 = n_in()
S = s_in()
Q = n_in()


T = SegmentTree(n,
    [set([s]) for s in S],
    lambda x,y: x.union(y),
    lambda: set()
    )

for _ in range(Q):
    n, i, j = input().split()
    if int(n) == 1:
        T.update(int(i)-1, set([j]))
    else:
        print(len(T.query(int(i)-1, int(j))))

Submission status: Time Limit Exceeded

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        # 引数が1つなら一点の値を取得
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

N = INT()
S = [ord(c)-97 for c in input()]
BITs = [BIT(N+1) for i in range(26)]
for i, s in enumerate(S):
    BITs[s].add(i, 1)

Q = INT()
for _ in range(Q):
    q = list(input().split())
    if q[0] == '1':
        _, i, c = q
        i = int(i) - 1
        c = ord(c) - 97
        if S[i] != c:
            prev = S[i]
            S[i] = c
            BITs[prev].add(i, -1)
            BITs[c].add(i, 1)
    else:
        _, l, r = q
        l, r = int(l) - 1, int(r) - 1
        ans = 0
        for c in range(26):
            if BITs[c].get(l, r+1) > 0:
                ans += 1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

alpha = ['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']

def twopowerceil(n):  # return m s.t. m>=n and m=2**p
    for i in range(40):
        m = 2**i
        if m >= n:
            return m
    return -1

#      0
#   1     2
# 3   4  5  6
#       :
# leaf i - n-1+i
# parent   - (i-1)//2
# children - 2*i+1, 2*i+2

def sgtoper(x,y):
    return (x or y)  # min,max,gcd,...

SGTDEFAULT = False # for or ; BIG for min ; ..
  # s.t. sgtoper(x,SGTDEFAULT) = x

# nn = twopowerceil(n)
# tree must be initialized to [SGTDEFAULT]*(2*nn)
def sgtinit(tree,a,n,nn):  # upto N-1, not N
    for i in range(n):
        tree[nn-1+i] = a[i]
    for i in range(nn-2,-1,-1):
        tree[i] = sgtoper(tree[2*i+1], tree[2*i+2])

def sgtget(tree,x,y,nn):
    return sgtgetcore(tree,x,y,0,0,nn)

# x,y: from query  k: suffix at focus l,r: range for k
# right ends (y,r) not included
def sgtgetcore(tree,x,y,k,l,r):
    if r<=x or y<=l:
        return SGTDEFAULT
    if x<=l and r<=y:
        return tree[k]
    vl = sgtgetcore(tree,x,y,2*k+1,l,(l+r)//2)
    vr = sgtgetcore(tree,x,y,2*k+2,(l+r)//2,r)
    return sgtoper(vl, vr)

def sgtupd(tree,i,x,nn):
    k = i+nn-1
    tree[k] = x
    while k>0:
        k = (k-1)//2
        tree[k] = sgtoper(tree[2*k+1], tree[2*k+2])

n = inn()
nn = twopowerceil(n)
tr = {}
for c in alpha:
    tr[c] = [False]*(2*nn)
ss = ins()
s = []
for i in range(n):
    s.append(ss[i])
a = {}
for c in alpha:
    a[c] = [False]*n
for i in range(n):
    a[s[i]][i] = True
for c in alpha:
    sgtinit(tr[c],a[c],n,nn)

#ddprint("tree")
#for c in alpha:
#    ddprint(c)
#    ddprint(tr[c])

q = inn()
for qq in range(q):
    x,y,z = input().split()
    #ddprint(f"x {x} y {y} z {z}")
    if x == '1':
        i = int(y)-1
        c = z
        sgtupd(tr[s[i]], i, False, nn)
        sgtupd(tr[c], i, True, nn)
        s[i] = c
    else:
        l = int(y)
        r = int(z)
        sm = 0
        for c in alpha:
            v = sgtget(tr[c],l-1,r,nn)
            if v:
                sm += 1
        print(sm)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
Q = int(input())
query = [input().split() for _ in range(Q)]

bit = [[0 for _ in range(26)] for _ in range(N + 1)]

def bit_add(i, s, x):
    j = ord(s) - ord("a")
    while i <= N:
        bit[i][j] += x
        i += i & - i
        
def bit_sum(i):
    s = [0] * 26
    while i:
        for j in range(26):
            s[j] += bit[i][j]
        i -= i & -i
    return s
for i in range(1, N + 1):
    s = S[i - 1]
    bit_add(i, s, 1)

for x, y, z in query:
    if x == "1":
        y = int(y)
        bit_add(y, S[y - 1], -1)
        bit_add(y, z, 1)
        S[y - 1] = z
    if x == "2":
        answer = 0
        y, z = int(y) - 1, int(z)
        sum_y = bit_sum(y)
        sum_z = bit_sum(z)
        for i in range(26):
            if sum_z[i] - sum_y[i] > 0:
                answer += 1
        print(answer)

Submission status: Time Limit Exceeded

Solution code:
def ctoi(c):
  return ord(c)-97

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

bits=[[0]*(n+1) for _ in range(26)]

def query(pos):
  ret=[0]*26
  for i in range(26):
    tmp=0
    p=pos
    while p>0:
      tmp+=bits[i][p]
      p-=p&(-p)
    ret[i]=tmp
  return ret

def update(pos,a,x):
  while pos<=n:
    bits[a][pos]+=x
    pos+=pos&(-pos)

for i in range(n):
  update(i+1,ctoi(s[i]),1)

q=int(input())
for _ in range(q):
  flag,a,b=map(str,input().split())
  flag=int(flag)
  a=int(a)
  if flag==1:
    if s[a-1]==b:
      continue
    else:
      update(a,ctoi(s[a-1]),-1)
      update(a,ctoi(b),1)
      s[a-1]=b
  elif flag==2:
    b=int(b)
    cnt1=query(b)
    cnt2=query(a-1)
    ans=0
    for i in range(26):
      if cnt1[i]-cnt2[i]>0:
        ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())


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

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=seg[2*i+1]|seg[2*i+2]

def update(k,b):
    k += num-1
    if seg[k]=={b}:
        return ()
    seg[k] = {b}
    while k:
        k = (k-1)>>1
        seg[k] = seg[k*2+1]|seg[k*2+2]

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=set()
    while q-p>1:
        if p&1 == 0:
            res = res|seg[p]
        if q&1 == 1:
            res = res|seg[q]
            q -= 1
        p = p>>1
        q = (q-1)>>1
    if p == q:
        res = res|seg[p]
    else:
        res = res|seg[p]|seg[q]
    return res

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

for i in range(N):
    seg[i+num-1]={ord(S[i])}
for k in range(num-2,-1,-1):
    seg[k] = seg[k*2+1]|seg[k*2+2]


for q in range(Q):
    type, i, c = input().split()
    if type=="1":
        update(int(i)-1,ord(c))
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())


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

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=seg[2*i+1]|seg[2*i+2]

def update(k,b):
    k += num-1
    if seg[k]=={b}:
        return ()
    seg[k] = {b}
    while k:
        k = (k-1)>>1
        seg[k] = seg[k*2+1]|seg[k*2+2]

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = res|seg[p]
        if q&1 == 1:
            res = res|seg[q]
            q -= 1
        p = p>>1
        q = (q-1)>>1
    if p == q:
        res = res|seg[p]
    else:
        res = res|seg[p]|seg[q]
    return res

ide_ele =set()

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

for i in range(N):
    update(i,ord(S[i]))

for q in range(Q):
    type, i, c = input().split()
    if type=="1":
        update(int(i)-1,ord(c))
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())


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

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,b):
    k += num-1
    if seg[k]=={b}:
        return ()
    seg[k] = {b}
    while k:
        k = (k-1)>>1
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p>>1
        q = (q-1)>>1
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele =set()

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

for i in range(N):
    update(i,ord(S[i]))

for q in range(Q):
    type, i, c = input().split()
    if type=="1":
        update(int(i)-1,ord(c))
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())


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

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,b):
    k += num-1
    if seg[k]==set([b]):
        return ()
    seg[k] = set([b])
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
def subquery(l, r, k, i, j):
        # 区間[i,j)の中で区間[l,r)の文字列の集合を返す
        if j <= l or r <= i:
            return set()
        elif l <= i and j <= r:
            return seg[k]
        else:
            l_set = subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_set = subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return l_set | r_set

def query(l, r):
    # [l,r)に含まれる文字の種類数
    return len(subquery(l, r, 0, 0, num))
ide_ele =set()

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

for i in range(N):
    update(i,ord(S[i]))

for q in range(Q):
    type, i, c = input().split()
    if type=="1":
        update(int(i)-1,ord(c))
    else:
        print(query(int(i)-1,int(c)))
    #print(seg)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())


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

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,b):
    k += num-1
    if seg[k]==set([b]):
        return ()
    seg[k] = {b}
    while k:
        k = (k-1)>>1
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p>>1
        q = (q-1)>>1
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele =set()

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

for i in range(N):
    update(i,ord(S[i]))

for q in range(Q):
    type, i, c = input().split()
    if type=="1":
        update(int(i)-1,ord(c))
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())
Query=[input().split() for i in range(Q)]


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

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,b):
    k += num-1
    if seg[k]==set([b]):
        return ()
    seg[k] = {b}
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p>>1
        q = (q-1)>>1
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele =set()

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

for i in range(N):
    update(i,ord(S[i]))

for type,i,c in Query:

    if type=="1":
        update(int(i)-1,ord(c))
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())
Query=[input().split() for i in range(Q)]


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

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,b):
    k += num-1
    if seg[k]==set([b]):
        return ()
    seg[k] = set([b])
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p>>1
        q = (q-1)>>1
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele =set()

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

for i in range(N):
    update(i,ord(S[i]))

for type,i,c in Query:

    if type=="1":
        update(int(i)-1,ord(c))
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left, bisect_right, insort

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
S = list('-' + sr())
d = [[] for _ in range(26)]
for i in range(1, N+1):
    s = S[i]
    o = ord(s) - ord('a')
    insort(d[o], i)

Q = ir()
for _ in range(Q):
    q, a, b = sr().split()
    if q == '1':
        a = int(a)
        if S[a] == b:
            continue
        prev = ord(S[a]) - ord('a')
        d[prev].remove(a)
        next = ord(b) - ord('a')
        insort(d[next], a)
        S[a] = b
    else:
        a = int(a); b = int(b)
        ans = 0
        for alpha in range(26):
            if bisect_right(d[alpha], b) - bisect_left(d[alpha], a) >= 1:
                ans += 1
        print(ans)

# 17

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())
Query=[input().split() for i in range(Q)]


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

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,b):
    k += num-1
    if seg[k]==set([b]):
        return ()
    seg[k] = set([b])
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p>>1
        q = (q-1)>>1
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele =set()

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

for i in range(N):
    update(i,S[i])

for type,i,c in Query:

    if type=="1":
        update(int(i)-1,c)
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, insort_left


def main():
    n = int(input())
    s = list(input())
    q = int(input())
    qs = [input().split() for _ in range(q)]

    abc = [[] for _ in range(26)]
    for i, e in enumerate(s):
        j = ord(e) - ord("a")
        abc[j].append(i)

    for t, e1, e2 in qs:
        if t == "1":
            i = int(e1) - 1
            c = e2

            let = s[i]

            idx = ord(let) - ord("a")
            popi = bisect_left(abc[idx], i)
            abc[idx].pop(popi)

            idx = ord(c) - ord("a")
            insort_left(abc[idx], i)

            s[i] = c

        else:
            l = int(e1) - 1
            r = int(e2) - 1

            cnt = 0
            for i in range(26):
                li = bisect_left(abc[i], l)
                if li >= len(abc[i]):
                    continue
                if abc[i][li] <= r:
                    cnt += 1

            print(cnt)


if __name__ == "__main__":
    main()