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:
# AtCoder Beginner Contest 157
# E - Simple String Queries
# https://atcoder.jp/contests/abc157/tasks/abc157_e
from bisect import bisect_left, insort_left
from collections import defaultdict


_, S, _, *Q = open(0).read().split()
S = list(S)
Q = tuple(zip(*[iter(Q)]*3))

D = defaultdict(list)

for i, s in enumerate(S):
    D[s].append(i)

for q, *x in Q:
    if int(q) == 1:
        i, c = x
        i = int(i) - 1

        s, S[i] = S[i], c

        j = bisect_left(D[s], i)
        D[s].pop(j)

        insort_left(D[c], i)

    else:
        l, r = map(int, x)
        l -= 1
        r -= 1
        cnt = 0
        for L in D.values():
            i = bisect_left(L, l)
            if i == len(L):
                continue
            if L[i] <= r:
                cnt += 1

        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self,orig,func,unit):
        _len= len(orig)
        self.func = func
        self.size = 1 << (_len-1).bit_length()
        self.tree = [unit] * self.size + orig + [unit] *(self.size-_len)
        self.unit = unit
        
        for i in range(self.size -1,0,-1):
            self.tree[i] = func(self.tree[i*2], self.tree[i*2+1])
            
    def update(self, i, v):
        i+=self.size
        self.tree[i] = v
        while i:
            i//=2
            self.tree[i]=self.func(self.tree[i*2],self.tree[i*2+1])
    
    def find(self,l,r):
        l+=self.size
        r+=self.size
        ret=self.unit
        while l<r:
            if l&1:
                ret = self.func(ret,self.tree[l])
                l+=1
            if r&1:
                r-=1
                ret=self.func(ret,self.tree[r])
            l//=2
            r//=2
        return ret
import sys
input=sys.stdin.readline
input()
def lam(x,y):
  return x|y
seg = SegmentTree([set(x) for x in input()[:-1]],lam, set())
ans = []
for _ in range(int(input())):
  f, x, y = input().split()
  if f == "1":
    seg.update(int(x) - 1, set(y))
  else:
    ans.append(len(seg.find(int(x) - 1, int(y))))
print(*ans)

Submission status: Time Limit Exceeded

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

from collections import Counter
ans = []
for _ in range(q):
    a, b, c = input().split()
    if a == '1':
        s[int(b)-1] = c
    else:
        dic = Counter(s[int(b)-1:int(c)])
        ans.append(len(dic))

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
#セグ木
from collections import deque
def f(L, R): return L|R # merge
def g(old, new): return old^new  # update
zero = 0 #零元

class segtree:
    def __init__(self, N, z):
        self.M = 1
        while self.M<N: self.M *= 2
        self.dat = [z] * (self.M*2-1)
        self.ZERO = z

    def update(self, x, idx, l=0, r=-1):
        if r==-1: r = self.M
        idx += self.M-1
        self.dat[idx] = g(self.dat[idx], x)
        while idx > 0:
            idx = (idx-1)//2
            self.dat[idx] = f(self.dat[idx*2+1], self.dat[idx*2+2])

    def query(self, a, b=-1, idx=0, l=0, r=-1):
        if r==-1: r = self.M
        if b==-1: b = self.M
        q = deque([])
        q.append([l, r, 0])
        ret = self.ZERO
        while len(q):
            tmp = q.popleft()
            L = tmp[0]
            R = tmp[1]
            if R<=a or b<=L: continue
            elif a<=L and R<=b:
                ret = f(ret, self.dat[tmp[2]])
            else:
                q.append([L, (L+R)//2, tmp[2]*2+1])
                q.append([(L+R)//2, R, tmp[2]*2+2])
        return ret
n = int(input())
s = list(input())
q = int(input())
seg = segtree(n+1, 0)

for i in range(n):
    num = ord(s[i]) - ord("a")
    seg.update((1<<num), i)
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1
    if a == "1":
        pre = ord(s[b]) - ord("a")
        now = ord(c) - ord("a")
        seg.update((1<<pre), b)
        seg.update((1<<now), b)
        s[b] = c
    else:
        q = seg.query(b, int(c))
        bin(q).count("1")
        print(bin(q).count("1"))

Submission status: Time Limit Exceeded

Solution code:
#セグ木

from collections import deque
def f(L, R): return L + R # merge
def g(old, new): return new  # update
zero = 0 #零元
class segtree:
    def __init__(self, N, z):
        self.M = 1
        while self.M<N: self.M *= 2
        self.dat = [z] * (self.M*2-1)
        self.ZERO = z

    def update(self, x, idx, l=0, r=-1):
        if r==-1: r = self.M
        idx += self.M-1
        self.dat[idx] = g(self.dat[idx], x)
        while idx > 0:
            idx = (idx-1)//2
            self.dat[idx] = f(self.dat[idx*2+1], self.dat[idx*2+2])

    def query(self, a, b=-1, idx=0, l=0, r=-1):
        if r==-1: r = self.M
        if b==-1: b = self.M
        q = deque([])
        q.append([l, r, 0])
        ret = self.ZERO
        while len(q):
            tmp = q.popleft()
            L = tmp[0]
            R = tmp[1]
            if R<=a or b<=L: continue
            elif a<=L and R<=b:
                ret = f(ret, self.dat[tmp[2]])
            else:
                q.append([L, (L+R)//2, tmp[2]*2+1])
                q.append([(L+R)//2, R, tmp[2]*2+2])
        return ret
n = int(input())
s = list(input())
q = int(input())
l = []
for _ in range(26): l.append(segtree(n+1, 0))
for i in range(n):
    num = ord(s[i]) - ord("a")
    l[num].update(1, i)
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1
    if a == "1":
        pre = ord(s[b]) - ord("a")
        now = ord(c) - ord("a")
        l[pre].update(0, b)
        l[now].update(1, b)
        s[b] = c
    else:
        c = int(c)
        cnt = 0
        for i in range(26):
            q = l[i].query(b, c)
            if q > 0: cnt += 1
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#セグ木
from collections import deque
def f(L, R): return L + R # merge
def g(old, new): return new  # update
zero = 0 #零元
class segtree:
    def __init__(self, N, z):
        self.M = 1
        while self.M<N: self.M *= 2
        self.dat = [z] * (self.M*2-1)
        self.ZERO = z

    def update(self, x, idx, l=0, r=-1):
        if r==-1: r = self.M
        idx += self.M-1
        self.dat[idx] = g(self.dat[idx], x)
        while idx > 0:
            idx = (idx-1)//2
            self.dat[idx] = f(self.dat[idx*2+1], self.dat[idx*2+2])

    def query(self, a, b=-1, idx=0, l=0, r=-1):
        if r==-1: r = self.M
        if b==-1: b = self.M
        q = deque([])
        q.append([l, r, 0])
        ret = self.ZERO
        while len(q):
            tmp = q.popleft()
            L = tmp[0]
            R = tmp[1]
            if R<=a or b<=L: continue
            elif a<=L and R<=b:
                ret = f(ret, self.dat[tmp[2]])
            else:
                q.append([L, (L+R)//2, tmp[2]*2+1])
                q.append([(L+R)//2, R, tmp[2]*2+2])
        return ret
n = int(input())
s = list(input())
q = int(input())
l = []
for _ in range(26): l.append(segtree(n+1, 0))
for i in range(n):
    num = ord(s[i]) - ord("a")
    l[num].update(1, i)
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1
    if a == "1":
        pre = ord(s[b]) - ord("a")
        now = ord(c) - ord("a")
        l[pre].update(0, b)
        l[now].update(1, b)
        s[b] = c
    else:
        c = int(c)
        cnt = 0
        for i in range(26):
            q = l[i].query(b, c)
            if q > 0: cnt += 1
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
s = list(input())
for i in range(int(input())):
    q, l, r = input().split()
    q = int(q)
    l = int(l) - 1
    if q == 1:
        if s[l] != r:
            s[l] = r
    else:
        print(len(set(s[l:int(r)])))

Submission status: Time Limit Exceeded

Solution code:
from string import ascii_lowercase
import sys


def input():
    return sys.stdin.readline().strip()


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
        self.k_init = 2 ** (self.n - 1).bit_length()

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

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


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

bits = {c: BIT(n) for c in ascii_lowercase}
[bits[c].add(i, 1) for i, c in enumerate(s, 1)]
queries = (input().split() for _ in range(q))

ans = []
for q_type, *q in queries:
    if q_type == '1':
        iq = int(q[0])
        cq = q[1]
        for c in ascii_lowercase:
            if bits[c].sum(iq) - bits[c].sum(iq - 1) == 1:
                bits[c].add(iq, -1)
                break
        bits[cq].add(iq, 1)
    else:
        l, r = map(int, q)
        cnt = 0
        for c in ascii_lowercase:
            if bits[c].sum(r) - bits[c].sum(l - 1) > 0:
                cnt += 1
        ans.append(cnt)
[print(i) for i in ans]

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect, insort
def main():
    n = int(input())
    s = list(input())
    q = int(input())
    _is = {chr(i):[] for i in range(ord("a"), ord("a")+27)}
    for i, si in enumerate(s, 1):
        _is[si].append(i)
    for _ in range(q):
        t, i, c = input().split()
        i = int(i)
        if t == "1":
            index = bisect_left(_is[s[i-1]], i)
            _is[s[i-1]].pop(index)
            insort(_is[c], i)
            s[i-1] = c
        else:
            c = int(c)
            cnt = 0
            for _isi in _is.values():
                if _isi:
                    is_in = bisect(_isi, c)-bisect_left(_isi, i)
                    if is_in:
                        cnt += 1
            print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect, insort
def main():
    n = int(input())
    s = list(input())
    q = int(input())
    _is = {chr(i):[] for i in range(ord("a"), ord("a")+27)}
    for i, si in enumerate(s, 1):
        _is[si].append(i)
    for _ in range(q):
        t, i, c = input().split()
        i = int(i)
        if t == "1":
            index = bisect_left(_is[s[i-1]], i)
            del _is[s[i-1]][index]
            insort(_is[c], i)
            s[i-1] = c
        else:
            c = int(c)
            cnt = 0
            for _isi in _is.values():
                if _isi:
                    is_in = bisect(_isi, c)-bisect_left(_isi, i)
                    if is_in:
                        cnt += 1
            print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect, insort
def main():
    n = int(input())
    s = list(input())
    q = int(input())
    _is = {chr(i):[] for i in range(ord("a"), ord("a")+27)}
    for i, si in enumerate(s, 1):
        _is[si].append(i)
    for _ in range(q):
        t, i, c = input().split()
        i = int(i)
        if t == "1":
            _is[s[i-1]].remove(i)
            insort(_is[c], i)
            s[i-1] = c
        else:
            c = int(c)
            cnt = 0
            for _isi in _is.values():
                if _isi:
                    is_in = bisect(_isi, c)-bisect_left(_isi, i)
                    if is_in:
                        cnt += 1
            print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r, i=0):
        j = i - (1 << ((i + 1).bit_length() - 1))+1
        length = 1 << (self.logn - (i + 1).bit_length() + 1)
        ll = j * length
        rr = (j + 1) * length
        if l <= ll and rr <= r:
            return self.b[i]
        elif rr <= l or r <= ll:
            return self.one
        else:
            return self.func(self.get_segment(l, r, i * 2 + 1),
                             self.get_segment(l, r, i * 2 + 2))


def get_int(s):
    abc = "abcdefghijklmnopqrstuvwxyz"
    return 1<<abc.index(s)


seg = SegmentTree([get_int(i) for i in s], int.__or__, 0)

for _ in range(q):
    q, i, j = input().split()
    if q == "1":
        seg.update(int(i) - 1, get_int(j))
    else:
        aa = seg.get_segment(int(i) - 1, int(j))
        ans = 0
        for i in range(26):
            if (aa >> i) & 1 == 1:
                ans += 1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect, insort
def main():
    n = int(input())
    a = ord("a")
    orda = lambda x: ord(x)-a
    s = list(map(orda, list(input())))
    q = int(input())
    _is = [[] for _ in range(26)]
    for i, si in enumerate(s, 1):
        _is[si].append(i)
    
    for _ in range(q):
        t, i, c = input().split()
        i = int(i)
        if t == "1":
            if s[i-1] == c:
                continue
            _is[s[i-1]].remove(i)
            insort(_is[ord(c)-a], i)
            s[i-1] = ord(c)-a
        else:
            c = int(c)
            cnt = 0
            for _isi in _is:
                if _isi:
                    is_in = bisect(_isi, c)-bisect_left(_isi, i)
                    if is_in:
                        cnt += 1
            print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect, insort
def main():
    n = int(input())
    a = ord("a")
    orda = lambda x: ord(x)-a
    s = list(map(orda, list(input())))
    q = int(input())
    _is = [[] for _ in range(26)]
    for i, si in enumerate(s, 1):
        _is[si].append(i)
    
    for _ in range(q):
        t, i, c = input().split()
        i = int(i)
        if t == "1":
            _is[s[i-1]].remove(i)
            insort(_is[ord(c)-a], i)
            s[i-1] = ord(c)-a
        else:
            c = int(c)
            cnt = 0
            for j in range(26):
                is_in = bisect(_is[j], c)-bisect_left(_is[j], i)
                if is_in:
                    cnt += 1
            print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r, i=0):
        j = i - (1 << ((i + 1).bit_length() - 1))+1
        length = 1 << (self.logn - (i + 1).bit_length() + 1)
        ll = j * length
        rr = (j + 1) * length
        if l <= ll and rr <= r:
            return self.b[i]
        elif rr <= l or r <= ll:
            return self.one
        else:
            return self.func(self.get_segment(l, r, i * 2 + 1),
                             self.get_segment(l, r, i * 2 + 2))


seg = SegmentTree([set(i) for i in s], set.union, set())

for _ in range(q):
    q, i, j = input().split()
    if q == "1":
        seg.update(int(i) - 1, set(j))
    else:
        print(len(seg.get_segment(int(i)-1, int(j))))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = ord("a")
    orda = lambda x: ord(x)-a
    s = list(map(orda, list(input())))
    q = int(input())
    bits = [BIT(n) for _ in range(26)]
    for i, si in enumerate(s, 1):
        bits[si].add(i, 1)
    for _ in range(q):
        t, i, c = input().split()
        i = int(i)
        if t == "1":
            bits[s[i-1]].add(i, -1)
            bits[ord(c)-a].add(i, 1)
            s[i-1] = ord(c)-a
        else:
            c = int(c)
            cnt = 0
            for bit in bits:
                is_in = bit.sum_(c) - bit.sum_(i-1)
                if is_in:
                    cnt += 1
            print(cnt)
            
            
class BIT:
    __slots__ = ["length", "data"]
    def __init__(self, length):
        self.data = [0]*(length+1)
        self.length = length
    
    def add(self, i, x):
        while i < self.length+1:
            self.data[i] += x
            i += i&-i
    
    def sum_(self, i):
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i&-i
        return x


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

from math import ceil

class Segtree:
    def __init__(self, begin, size, s):
        self.begin = begin
        self.size = size
        self.counter = [0 for i in range(26)]
        for c in s[begin - 1:begin + size - 1]:
            ci = ord(c) - ord("a")
            self.counter[ci] += 1
        if size == 1:
            self.left = None
            self.right = None
            self.ci = ci
        else:
            sl = ceil(size / 2.0)
            sr = size - sl
            self.left = Segtree(begin, sl, s)
            self.right = Segtree(begin + sl, sr, s)

    def change_ith_to_c(self, i1, ci):
        if self.size == 1:
            prev = self.ci
            self.ci = ci
        else:
            sl = ceil(self.size / 2.0)
            child = self.left if i1 <= self.begin + sl - 1 else self.right
            prev = child.change_ith_to_c(i1, ci)
        self.counter[prev] -= 1
        self.counter[ci] += 1
        return prev

    def qt2(self, l, r):
        if l == self.begin and r == self.begin + self.size - 1:
            return {ci for ci in range(26) if self.counter[ci]}
        sl = ceil(self.size / 2.0)
        center = self.begin + sl - 1  # End of left
        if r <= center:
            return self.left.qt2(l, r)
        elif l > center:
            return self.right.qt2(l, r)
        else:
            return self.left.qt2(l, center) | self.right.qt2(center + 1, r)

    def __repr__(self):
        return "[{} {} {} {}]".format(self.begin, self.begin + self.size - 1,
            repr(self.left), repr(self.right))

def main():
    n = int(input())
    s = input()
    st = Segtree(1, n, s)
    q = int(input())
    for i in range(q):
        t, l, r = input().split()
        if t == "1":
            ci = ord(r) - ord("a")
            st.change_ith_to_c(int(l), ci)
        else:
            print(len(st.qt2(int(l), int(r))))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

from math import ceil

class Segtree:
    def __init__(self, begin, size, s):
        self.begin = begin
        self.size = size
        self.counter = [0 for i in range(26)]
        for c in s[begin - 1:begin + size - 1]:
            ci = ord(c) - ord("a")
            self.counter[ci] += 1
        if size == 1:
            self.left = None
            self.right = None
            self.ci = ci
        else:
            sl = ceil(size / 2.0)
            sr = size - sl
            self.left = Segtree(begin, sl, s)
            self.right = Segtree(begin + sl, sr, s)

    def change_ith_to_c(self, i1, ci):
        if self.size == 1:
            prev = self.ci
            self.ci = ci
        else:
            sl = ceil(self.size / 2.0)
            child = self.left if i1 <= self.begin + sl - 1 else self.right
            prev = child.change_ith_to_c(i1, ci)
        self.counter[prev] -= 1
        self.counter[ci] += 1
        return prev

    def qt2(self, l, r):
        if self.size == 1:
            return {self.ci}
        sl = ceil(self.size / 2.0)
        center = self.begin + sl - 1  # End of left
        if r <= center:
            return self.left.qt2(l, r)
        elif l > center:
            return self.right.qt2(l, r)
        elif l == self.begin and r == self.begin + self.size - 1:
            return {ci for ci in range(26) if self.counter[ci]}
        else:
            return self.left.qt2(l, center) | self.right.qt2(center + 1, r)

    def __repr__(self):
        return "[{} {} {} {}]".format(self.begin, self.begin + self.size - 1,
            repr(self.left), repr(self.right))

def main():
    n = int(input())
    s = input()
    st = Segtree(1, n, s)
    q = int(input())
    for i in range(q):
        t, l, r = input().split()
        if t == "1":
            ci = ord(r) - ord("a")
            st.change_ith_to_c(int(l), ci)
        else:
            print(len(st.qt2(int(l), int(r))))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

from math import ceil

class Segtree:
    def __init__(self, begin, size, s):
        self.begin = begin
        self.size = size
        self.counter = [0 for i in range(26)]  # ttk
        for c in s[begin - 1:begin + size - 1]:
            ci = ord(c) - ord("a")
            self.counter[ci] += 1
        if size == 1:
            self.left = None
            self.right = None
            self.ci = ci
        else:
            sl = ceil(size / 2.0)
            sr = size - sl
            self.left = Segtree(begin, sl, s)
            self.right = Segtree(begin + sl, sr, s)

    def change_ith_to_c(self, i1, ci):
        if self.size == 1:
            assert i1 == self.begin
            prev = self.ci
            self.ci = ci
        else:
            sl = ceil(self.size / 2.0)
            child = self.left if i1 <= self.begin + sl - 1 else self.right
            prev = child.change_ith_to_c(i1, ci)
        self.counter[prev] -= 1
        self.counter[ci] += 1
        return prev

    def qt2(self, l, r):
        assert self.begin <= l
        assert r <= self.begin + self.size - 1
        if self.size == 1:
            return {self.ci}
        sl = ceil(self.size / 2.0)
        center = self.begin + sl - 1  # End of left
        if r <= center:
            return self.left.qt2(l, r)
        elif l > center:
            return self.right.qt2(l, r)
        elif l == self.begin and r == self.begin + self.size - 1:
            return {ci for ci in range(26) if self.counter[ci]}
        else:
            return self.left.qt2(l, center) | self.right.qt2(center + 1, r)

    def __repr__(self):
        return "[{} {} {} {}]".format(self.begin, self.begin + self.size - 1,
            repr(self.left), repr(self.right))

def main():
    n = int(input())
    s = input()
    st = Segtree(1, n, s)
    q = int(input())
    for i in range(q):
        t, l, r = input().split()
        if t == "1":
            ci = ord(r) - ord("a")
            st.change_ith_to_c(int(l), ci)
        else:
            print(len(st.qt2(int(l), int(r))))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

from math import ceil

class Segtree:
    def __init__(self, begin, size, s):
        self.begin = begin
        self.size = size
        self.counter = [0 for i in range(26)]  # ttk
        for c in s[begin - 1:begin + size - 1]:
            ci = ord(c) - ord("a")
            self.counter[ci] += 1
        if size == 1:
            self.left = None
            self.right = None
            self.ci = ci
        else:
            sl = ceil(size / 2.0)
            sr = size - sl
            self.left = Segtree(begin, sl, s)
            self.right = Segtree(begin + sl, sr, s)

    def change_ith_to_c(self, i1, ci):
        if self.size == 1:
            assert i1 == self.begin
            prev = self.ci
            self.ci = ci
        else:
            sl = ceil(self.size / 2.0)
            child = self.left if i1 <= self.begin + sl - 1 else self.right
            prev = child.change_ith_to_c(i1, ci)
        self.counter[prev] -= 1
        self.counter[ci] += 1
        return prev

    def qt2(self, l, r):
        assert self.begin <= l
        assert r <= self.begin + self.size - 1
        if self.size == 1:
            return {self.ci}
        sl = ceil(self.size / 2.0)
        center = self.begin + sl - 1  # End of left
        if r <= center:
            return self.left.qt2(l, r)
        elif l > center:
            return self.right.qt2(l, r)
        else:
            return self.left.qt2(l, center) | self.right.qt2(center + 1, r)

    def __repr__(self):
        return "[{} {} {} {}]".format(self.begin, self.begin + self.size - 1,
            repr(self.left), repr(self.right))

def main():
    n = int(input())
    s = input()
    st = Segtree(1, n, s)
    q = int(input())
    for i in range(q):
        t, l, r = input().split()
        if t == "1":
            ci = ord(r) - ord("a")
            st.change_ith_to_c(int(l), ci)
        else:
            print(len(st.qt2(int(l), int(r))))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    S = list(input())
    
    n = ceil(N**0.5)
    
    count = [Counter(S[i*n : i*n+n]) for i in range(n)]
    
    for i in range(int(input())):
        a, l, r = input().split()
        l = int(l)-1
        
        if a == '1':
            idx = l // n
            count[idx][S[l]] -= 1
            S[l] = r
            count[idx][r] += 1
            
        else:
            r = int(r)-1
            
            l_idx = l // n
            r_idx = r // n
                        
            if l_idx == r_idx: ans = set(S[l:r+1])                
            else:
                ans = set()

                l_idx += 1
                r_idx -= 1
                
                while l_idx <= r_idx:
                    ans |= {key for key, value in count[l_idx].items() if value}
                    l_idx += 1
                    
                while True:
                    ans.add(S[l])
                    l += 1
                    if not l % n: break
                    
                while True:
                    ans.add(S[r])
                    if not r % n: break
                    r -= 1
                                        
            print(len(ans))
            
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left, insort_left

def main():
    N = int(input())
    S = list(input().split()[0])
    
    alp = 'abcdefghijklmnopqrstuvwxyz'
    
    count = {a:[] for a in alp}
    
    for idx, s in enumerate(S): count[s].append(idx+1)
    
    for i in range(int(input())):
        n, l, r = input().split()
        l = int(l)
        
        if n == '1':
            idx = bisect_left(count[S[l-1]], l)
            del count[S[l-1]][idx]
            
            insort_left(count[r], l)
            S[l-1] = r
            
        else:
            ans = 0
            
            for c in count.values():
                if not c: continue
                idx = bisect_left(c, l)
                if len(c) <= idx: continue
                elif c[idx] <= int(r): ans += 1
                                
            print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#単位元を設定
ide = 0

class SegmentTree:
	def __init__(self,n):
        #セグ木の頂点はindex == 1から。index == 0は無視すること。
        #つまり、STtable[0]は無視。頂点はSTtable[1]。
		self.n = n
		tmp = 0
		while True:
			if 2 ** tmp >= self.n:
				break
			tmp += 1
		self.STtable = [ide] * (2*2**tmp)
		self.STtable_size = len(self.STtable)

	def update(self,i,a):
        #更新のためのインデックスの指定は0_indexedで。
		a_bit = 1 << ord(a)-97
		i += self.STtable_size//2
		self.STtable[i] = a_bit
		while i > 0:
			i //= 2
			self.STtable[i] = self.STtable[i*2] | self.STtable[i*2+1]

	def find(self,a,b,k=1,l=0,r=None):
        #kは頂点番号。初期値は1にすること。
		#[a,b)の最小を返す。
		#[l,r)からです。
        #初期値のrは、self.STtable_size//2にすると、ちょうど要素数と同じ値になって[l,r)のrになる。
        #問題に適するように範囲を指定するように注意。大体[l,r]で指定されている。
		if r == None:
			r = self.STtable_size//2        
		if a >= r or b <= l:
			return ide
		elif a <= l and b >= r:
			return self.STtable[k]
		else:
			mid = (l+r)//2
			if b <= mid:
				return self.find(a,b,2*k,l,mid)
			elif a >= mid:
				return self.find(a,b,2*k+1,mid,r)
			else:
				v1 = self.find(a,mid,2*k,l,mid)
				v2 = self.find(mid,b,2*k+1,mid,r)
			return v1 | v2

N = int(input())
solve = SegmentTree(N)
S = input()
for i in range(N):
	solve.update(i,S[i])
Q = int(input())
ans = []
for _ in range(Q):
	a,b,c = map(str, input().split())
	if a == '1':
		solve.update(int(b)-1,c)
	else:
		tmp = solve.find(int(b)-1,int(c))
		cnt = 0
		for i in range(26):
			if tmp >> i & 1 == 1:
				cnt += 1
		ans.append(cnt)

for a in ans:
	print(a)