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: Runtime Error

Solution code:
from bisect import insort_left,bisect_left

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

a='abcdefghijklmnopqrstuvwxyz'
ch={i:[-1,n+1] for i in a}

for i in range(n):
    insort_left(ch[s[i]],i)
    
for i in range(q):
    m,l,r=input().split()
    if m=='1':
        l=int(l)-1
        x=bisect_left(ch[s[l]],l)
        ch[s[l]].pop(x)
        insort_left(ch[r],l)
    else:
        l,r=int(l)-1,int(r)-1
        res=0
        for i in a:
            y=bisect_left(ch[i],l)
            if y>=len(ch[i]):
                continue
            else:
                if ch[i][y]<=r:
                  res+=1
        print(res)

Submission status: Runtime Error

Solution code:
import bisect
n=int(input())
s=input()
q=int(input())
ch={i:[-1,n+1] for i in 'abcdefghijklmnopqrstuvwxyz'}

for i in range(n):
    bisect.insort(ch[s[i]],i)
    
for i in range(q):
    m,l,r=input().split()
    if m=='1':
        l=int(l)-1
        ch[s[l]].remove(l)
        bisect.insort(ch[r],l)
    else:
        l,r=int(l)-1,int(r)-1
        res=0
        for i in 'abcdefghijklmnopqrstuvwxyz':
            if len(ch[i])>0:
                res+=(ch[i][bisect.bisect_left(ch[i],l)]<=r)
        print(res)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N = int(input())
S = input().strip()
Q = int(input())
T = [set()] * (2 * N)
n = 1
while n < N:
    n *= 2

def update(k, a):
    k += n-1
    T[k] = {a}
    while k > 0:
        k = (k - 1) // 2
        T[k] = T[k*2] ^ T[k*2+1]

def query(a, b, k, l, r):
    # print(a, b, k, l, r)
    if r <= a or b <= l:
        # print('  ', set())
        return set()
    if a <= l and r <= b:
        # print('  ', T[k])
        return T[k]
    else:
        vl = query(a, b, k*2+1, l, (l+r)//2)
        vr = query(a, b, k*2+2, (l+r)//2, r)
        return vl | vr

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

for q in range(Q):
    f, i, c = [x for x in input().strip().split()]
    if f == '1':
        # print(T,T[int(i)-1])
        update(int(i)-1, c)
    elif f == '2':
        # print(int(i)-1, int(c)-1)
        print(len(query(int(i)-1, int(c), 0, 0, n)))

Submission status: Runtime Error

Solution code:
# ABC157e


#print(bin(toBitSet([1, 2, 3, 2])))

# for i in range(97, 123):
#    print(chr(i))


def main():
    import sys
    sys.setrecursionlimit(10**6)
    # 再帰関数を使わない限りPypyで出すこと

    #####segfunc######
    def segfunc(x, y):
        return x | y  # 例としてmin関数を設定

    def init(init_val):  # セグ木にしたい配列を渡す
        # set_val
        for i in range(len(init_val)):
            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, 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 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 res

    #####単位元######
    ide_ele = 0

    n = int(input())
    s = list(input())
    q = int(input())
    # num:n以上の最小の2のべき乗
    num = 2**(n-1).bit_length()  # nは元々の配列の長さ
    seg = [ide_ele] * 2 * num

    def toBitSet(numberSet):
        theSet = 0
        for i in numberSet:
            theSet = theSet | 1 << i
        return theSet

    def alphabetToZeroIndexed(alphabet):
        return ord(alphabet)-97

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

    for _ in range(q):
        a, b, c = input().split()
        b = int(b)
        if int(a) == 1:
            update(b, toBitSet([alphabetToZeroIndexed(c)]))
        else:
            c = int(c)
            print(bin(query(b, c+1)).count('1'))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import collections
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
N = int(input())
S = list(input())
Q = int(input())
alpha = "abcdefghijklmnopqrstuvwxyz"
d = dict()

for x in alpha:
    d[x] = ord(x) - 97


class segment_tree:
    n = 0
    segtree = []

    def __init__(self, A):
        N = len(A)
        self.n = (N-1).bit_length()
        self.n = 1 << self.n
        self.segtree = [0 for i in range(2*self.n)]
        for i in range(N):
            self.segtree[self.n+i-1] = 1 << d[A[i]]
        for i in range(self.n - 2, -1, -1):
            self.segtree[i] = self.segtree[i*2 + 1] | self.segtree[i*2 + 2]

    def update(self, i, x):
        id = self.n+i - 1
        while(id >= 0):
            if id >= self.n or self.n == 1:
                self.segtree[id] = 1 << d[x]
                # print(self.segtree)
            else:
                self.segtree[id] = self.segtree[id *
                                                2 + 1] | self.segtree[id*2 + 2]
                # print(self.segtree[id*2 + 1], self.segtree[id*2+2])
            id = (id - 1) // 2

    def query(self, a, b, k, l, r):
        if r <= a or l >= b:
            return(0)
        if a <= l and r <= b:
            return(self.segtree[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(vl | vr)


def popcount(x):
    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
    x = x + (x >> 8)  # 16bitごと
    x = x + (x >> 16)  # 32bitごと
    x = x + (x >> 32)  # 64bitごと = 全部の合計
    return x & 0x0000007f


ST = segment_tree(S[:-1])
N = (N-1).bit_length()
N = 1 << N

for _ in range(Q):
    t, a, b = input().split()

    if t == "1":
        a = int(a)
        ST.update(a-1, b)
    elif t == "2":
        a = int(a)
        b = int(b)
        ret = ST.query(a-1, b, 0, 0, N)
        print(popcount(ret))
    # print(ST.segtree)

Submission status: Runtime Error

Solution code:
import math
A = ord('a')
N = int(input())
L = 2**int(math.ceil(math.log(N, 2)))
S = [x for x in input()]
Q = int(input())

Seg = [0]*(L*2-1)

def order(c):
    return 1 << (ord(c) - A)

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

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

def update(k, x):
    k += L - 1
    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:
        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)

    return merge(vl, vr)


# read S, and update tree
for i in range(N):
    c = order(S[i])
    update(i, c)
    #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]))
    else:
        l, r = int(i)-1, int(c)
        print(count(find(l, r, 0, 0, L)))

Submission status: Runtime Error

Solution code:
import math
A = ord('a')
N = int(input())
L = 2**int(math.ceil(math.log(N, 2)))
S = [x for x in input()]
Q = int(input())

Seg = [0]*(L*2-1)

def order(c):
    return 1 << (ord(c) - A)

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

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

def update(k, x):
    k += L - 1
    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:
        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)

    return merge(vl, vr)


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

for _ in range(1000):
    s = input()
    if not s:
        break
    q, i, c = s.split()
    if q == '1':
        i = int(i)-1
        if S[i] == c:
            continue
        S[i] = c
        update(i, order(S[i]))
    else:
        l, r = int(i)-1, int(c)
        #print(count(find(l, r, 0, 0, L)), (l, r))
        print(count(find(l, r, 0, 0, L)))

Submission status: Runtime Error

Solution code:
import collections
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
N = int(input())
S = list(input())
Q = int(input())
alpha = "abcdefghijklmnopqrstuvwxyz"
d = dict()

for x in alpha:
    d[x] = ord(x) - 97


class segment_tree:
    n = 0
    segtree = []

    def __init__(self, A):
        N = len(A)
        self.n = (N-1).bit_length()
        self.n = 1 << self.n
        self.segtree = [0 for i in range(2*self.n)]
        for i in range(N):
            self.segtree[self.n+i-1] = 1 << d[A[i]]
        for i in range(self.n - 2, -1, -1):
            self.segtree[i] = self.segtree[i*2 + 1] | self.segtree[i*2 + 2]

    def update(self, i, x):
        id = self.n+i - 1
        while(id >= 0):
            if id >= self.n:
                self.segtree[id] = 1 << d[x]
                # print(self.segtree)
            else:
                self.segtree[id] = self.segtree[id *
                                                2 + 1] | self.segtree[id*2 + 2]
                # print(self.segtree[id*2 + 1], self.segtree[id*2+2])
            id = (id - 1) // 2

    def query(self, a, b, k, l, r):
        if r <= a or l >= b:
            return(0)
        if a <= l and r <= b:
            return(self.segtree[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(vl | vr)


def popcount(x):
    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
    x = x + (x >> 8)  # 16bitごと
    x = x + (x >> 16)  # 32bitごと
    x = x + (x >> 32)  # 64bitごと = 全部の合計
    return x & 0x0000007f


ST = segment_tree(S[:-1])
N = (N-1).bit_length()
N = 1 << N

for _ in range(Q):
    t, a, b = input().split()

    if t == "1":
        a = int(a)
        ST.update(a-1, b)
    elif t == "2":
        a = int(a)
        b = int(b)
        ret = ST.query(a-1, b, 0, 0, N)
        print(popcount(ret))
    # print(ST.segtree)

Submission status: Runtime Error

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]
            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: Runtime Error

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)
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: Runtime Error

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

import bisect

N = int(input())
indexess = [[] for _ in range(26)]

S = list(input())
for i, s in enumerate(S):
    indexess[ord(s) - 97].append(i)


Q = int(input())
for _ in range(Q):
    q1,q2, q3 = input().split()
    q2 = int(q2)

    if q1 == '1':
        s0 = S[q2-1]
        if s0 != q3:
            S[q2-1] = q3
            
            indexes = indexess[ord(s0) - 97]
            del indexes[bisect.bisect_left(indexes, q2-1)+1]
            bisect.insort(indexess[ord(q3) - 97], q2-1)

    else:
        cnt = 0
        q3 = int(q3)
        for indexes in indexess:
            
            if bisect.bisect_left(indexes, q2-1) < bisect.bisect_right(indexes, q3-1):
                cnt += 1

        print(cnt)

Submission status: Runtime Error

Solution code:
import collections
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
N = int(input())
S = list(input())
Q = int(input())
alpha = "abcdefghijklmnopqrstuvwxyz"
d = dict()

for x in alpha:
    d[x] = ord(x) - 97


class segment_tree:
    n = 0
    segtree = []

    def __init__(self, A):
        N = len(A)
        self.n = (N-1).bit_length()
        self.n = 1 << self.n
        self.segtree = [0 for i in range(2*self.n)]
        for i in range(N):
            self.segtree[self.n+i-1] = 1 << d[A[i]]
        for i in range(self.n - 2, -1, -1):
            self.segtree[i] = self.segtree[i*2 + 1] | self.segtree[i*2 + 2]

    def update(self, i, x):
        id = self.n+i - 1
        while(id >= 0):
            if id >= self.n:
                self.segtree[id] = 1 << d[x]
                # print(self.segtree)
            else:
                self.segtree[id] = self.segtree[id *
                                                2 + 1] | self.segtree[id*2 + 2]
                # print(self.segtree[id*2 + 1], self.segtree[id*2+2])
            id = (id - 1) // 2

    def query(self, a, b, k, l, r):
        if r <= a or l >= b:
            return(0)
        if a <= l and r <= b:
            return(self.segtree[k])
        else:
            vl = self.query(a, b, k*2+1, l, (l+r+1)//2)
            vr = self.query(a, b, k*2+2, (l+r+1)//2, r)
            return(vl | vr)


def popcount(x):
    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
    x = x + (x >> 8)  # 16bitごと
    x = x + (x >> 16)  # 32bitごと
    x = x + (x >> 32)  # 64bitごと = 全部の合計
    return x & 0x0000007f


ST = segment_tree(S[:-1])


for _ in range(Q):
    t, a, b = input().split()

    if t == "1":
        a = int(a)
        ST.update(a-1, b)
    elif t == "2":
        a = int(a)
        b = int(b)
        ret = ST.query(a-1, b, 0, 0, N)
        print(popcount(ret))
    # print(ST.segtree)

Submission status: Runtime Error

Solution code:
#####segfunc######
def segfunc(x,y):
    if x == y == None:
        return []
    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 []
    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: Runtime Error

Solution code:
#####segfunc######
def segfunc(x,y):
    if x == y == None:
        return []
    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 []
    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), set([c]))
    else:
        if b == c:
            print(1)
        else:
            print(len(query(int(b)-1,int(c))))

Submission status: Runtime Error

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

num=2**((n-1).bit_length())
st=[[0]*(2*num) for _ in range(26)]

def update(pos,a,x):
  pos+=num
  st[a][pos]=x
  while pos>=0:
    pos=(pos-1)//2
    st[a][pos]=st[a][2*pos+1]|st[a][2*pos+2]
    
def query(l,r):
  ret=0
  for a in range(26):
    tl=l+num
    tr=r+num
    tmp=0
    while tl<tr:
      if tr&1==1:
        tr-=1
        tmp=max(tmp,st[a][tr-1])
      if tl&1==1:
        tmp=max(tmp,st[a][tl-1])
        tl+=1
      tl>>=1
      tr>>=1
    if tmp!=0:
      tmp=1
    ret+=tmp
  return ret

for i in range(n):
  update(i,ord(s[i])-97,1)

q=int(input())
for _ in range(q):
  a,b,c=map(str,input().split())
  a=int(a)
  b=int(b)-1
  if a==1:
    if c==s[b]:
      continue
    update(b,ord(s[b])-97,0)
    update(b,ord(c)-97,1)
    s[b]=c
  elif a==2:
    c=int(c)-1
    print(query(b,c+2))

Submission status: Runtime Error

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

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)
nc = lambda: ord(next(sc)) - ord('a')

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(), nc()
        B[ord(S[i - 1]) - ord('a')].add(i, -1)
        S[i - 1] = c
        B[c].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: Runtime Error

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

num=2**((n-1).bit_length())
st=[[0]*(2*num) for _ in range(26)]

def update(pos,a,x):
  pos+=num
  st[a][pos]=x
  while pos>=0:
    pos=(pos-1)//2
    st[a][pos]=max(st[a][2*pos+1],st[a][2*pos+2])
    
def query(l,r):
  ret=0
  for a in range(26):
    tl=l+num
    tr=r+num
    tmp=0
    while tl<tr:
      if tr&1==1:
        tr-=1
        tmp=max(tmp,st[a][tr-1])
      if tl&1==1:
        tmp=max(tmp,st[a][tl-1])
        tl+=1
      tl>>=1
      tr>>=1
    if tmp!=0:
      tmp=1
    ret+=tmp
  return ret

for i in range(n):
  update(i,ord(s[i])-97,1)

q=int(input())
for _ in range(q):
  a,b,c=map(str,input().split())
  a=int(a)
  b=int(b)-1
  if a==1:
    if c==s[b]:
      continue
    update(b,ord(s[b])-97,0)
    update(b,ord(c)-97,1)
    s[b]=c
  elif a==2:
    c=int(c)-1
    print(query(b,c+2))

Submission status: Runtime Error

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

num=2**((n-1).bit_length())
st=[[0]*(2*num) for _ in range(26)]

def update(pos,a,x):
  pos+=num
  st[a][pos]=x
  while pos>=0:
    pos=(pos-1)//2
    st[a][pos]=max(st[a][2*pos+1],st[a][2*pos+2])
    
def query(l,r):
  ret=0
  for a in range(26):
    tl=l+num
    tr=r+num
    tmp=0
    while tl<tr:
      if tr&1==1:
        tr-=1
        tmp=max(tmp,st[a][tr-1])
      if tl&1==1:
        tmp=max(tmp,st[a][tl-1])
        tl+=1
      tl>>=1
      tr>>=1
    if tmp!=0:
      tmp=1
    print(a,tmp)
    ret+=tmp
  return ret

for i in range(n):
  update(i,ord(s[i])-97,1)

q=int(input())
for _ in range(q):
  a,b,c=map(str,input().split())
  a=int(a)
  b=int(b)-1
  if a==1:
    if c==s[b]:
      continue
    update(b,ord(s[b])-97,0)
    update(b,ord(c)-97,1)
    s[b]=c
  elif a==2:
    c=int(c)-1
    print(query(b,c+2))

Submission status: Runtime Error

Solution code:
import collections
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
N = int(input())
S = list(input())
Q = int(input())
alpha = "abcdefghijklmnopqrstuvwxyz"
d = dict()

for x in alpha:
    d[x] = ord(x) - 97


class segment_tree:
    n = 0
    segtree = []

    def __init__(self, A):
        N = len(A)
        self.n = (N-1).bit_length()
        self.n = 2 ** self.n
        self.segtree = [0 for i in range(2*self.n)]
        for i in range(N):
            self.segtree[self.n+i-1] = 1 << d[A[i]]
        for i in range(self.n - 2, -1, -1):
            self.segtree[i] = self.segtree[i*2 + 1] | self.segtree[i*2 + 2]

    def update(self, i, x):
        id = self.n+i - 1
        while(id >= 0):
            if id >= self.n:
                self.segtree[id] = 1 << d[x]
                # print(self.segtree)
            else:
                self.segtree[id] = self.segtree[id *
                                                2 + 1] | self.segtree[id*2 + 2]
                # print(self.segtree[id*2 + 1], self.segtree[id*2+2])
            id = (id - 1) // 2

    def query(self, a, b, k, l, r):
        if r <= a or l >= b:
            return(0)
        if a <= l and r <= b:
            return(self.segtree[k])
        else:
            vl = self.query(a, b, k*2+1, l, (l+r+1)//2)
            vr = self.query(a, b, k*2+2, (l+r+1)//2, r)
            return(vl | vr)


def popcount(x):
    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
    x = x + (x >> 8)  # 16bitごと
    x = x + (x >> 16)  # 32bitごと
    x = x + (x >> 32)  # 64bitごと = 全部の合計
    return x & 0x0000007f


ST = segment_tree(S[:-1])


for _ in range(Q):
    t, a, b = input().split()

    if t == "1":
        a = int(a)
        ST.update(a-1, b)
    elif t == "2":
        a = int(a)
        b = int(b)
        ret = ST.query(a-1, b, 0, 0, N)
        # print(ST.segtree)
        print(popcount(ret))

Submission status: Runtime Error

Solution code:
import collections
import sys
input = sys.stdin.readline
N = int(input())
S = list(input())
Q = int(input())
alpha = "abcdefghijklmnopqrstuvwxyz"
d = dict()

for x in alpha:
    d[x] = ord(x) - 97


class segment_tree:
    n = 0
    segtree = []

    def __init__(self, A):
        N = len(A)
        self.n = (N-1).bit_length()
        self.n = 2 ** self.n
        self.segtree = [0 for i in range(2*self.n)]
        for i in range(N):
            self.segtree[self.n+i-1] = 1 << d[A[i]]
        for i in range(self.n - 2, -1, -1):
            self.segtree[i] = self.segtree[i*2 + 1] | self.segtree[i*2 + 2]

    def update(self, i, x):
        id = self.n+i - 1
        while(id >= 0):
            if id >= self.n:
                self.segtree[id] = 1 << d[x]
                # print(self.segtree)
            else:
                self.segtree[id] = self.segtree[id *
                                                2 + 1] | self.segtree[id*2 + 2]
                # print(self.segtree[id*2 + 1], self.segtree[id*2+2])
            id = (id - 1) // 2

    def query(self, a, b, k, l, r):
        if r <= a or l >= b:
            return(0)
        if a <= l and r <= b:
            return(self.segtree[k])
        else:
            vl = self.query(a, b, k*2+1, l, (l+r+1)//2)
            vr = self.query(a, b, k*2+2, (l+r+1)//2, r)
            return(vl | vr)


def popcount(x):
    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
    x = x + (x >> 8)  # 16bitごと
    x = x + (x >> 16)  # 32bitごと
    x = x + (x >> 32)  # 64bitごと = 全部の合計
    return x & 0x0000007f


ST = segment_tree(S[:-1])


for _ in range(Q):
    t, a, b = input().split()

    if t == "1":
        a = int(a)
        ST.update(a-1, b)
    elif t == "2":
        a = int(a)
        b = int(b)
        ret = ST.query(a-1, b, 0, 0, N)
        # print(ST.segtree)
        print(popcount(ret))

Submission status: Runtime Error

Solution code:
NN = 19
NN = 5
X = [0] * ((1<<NN+1)-1)
 
def popcount(x):
    x -= (x >> 1) & 0x55555555
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x += x >> 8
    x += x >> 16
    return x & 0x3f

def update(a, x):
    i = (1<<NN) - 1 + a
    X[i] = x
    while True:
        i = (i-1) // 2
        X[i] = X[2*i+1] | X[2*i+2]
        if i == 0:
            break

def rangeor(a, b):
    l = a + (1<<NN)
    r = b + (1<<NN)
    x = 0
    while l < r:
        if l%2:
            x |= X[l-1]
            l += 1
        if r%2:
            r -= 1
            x |= X[r-1]
        l >>= 1
        r >>= 1
    return x

N = int(input())
A = [ord(a) - 97 for a in input()]
for i, a in enumerate(A):
    X[(1<<NN) + i] = 1 << a
for i in range((1<<NN)-1)[::-1]:
    X[i] = X[i*2+1] | X[i*2+2]

Q = int(input())
for _ in range(Q):
    a, b, c = input().rstrip().split()
    if a == "1":
        b = int(b)
        c = ord(c) - 97
        update(b, 1<<c)
    else:
        b, c = int(b), int(c)
        print(popcount(rangeor(b, c+1)))
        print([i for i in range(26) if rangeor(b, c+1)>>i & 1])

Submission status: Runtime Error

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:
            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: Runtime Error

Solution code:
#####segfunc######
def segfunc(x,y):
    if type(x) is int:
        return x+y
    res = len(set([x,y]))
    if x == None:
        res -= 1
    if y == None:
        res -= 1
    return res
def init(init_val):
    #set_val
    for i in range(len(init_val)):
        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,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 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 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, c)
    else:
        if b == c:
            print(1)
        else:
            print(query(int(b)-1,int(c)-1))

Submission status: Runtime Error

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

num=2**(n-1).bit_length()
st=[set() for _ in range(2*num)]

def update1(pos,x):
  pos+=num
  st[pos].add(x)
  while pos>=0:
    pos=(pos-1)//2
    st[pos]=st[2*pos+1]|st[2*pos+2]
    
def update2(pos,x):
  pos+=num
  st[pos].discard(x)
  while pos>=0:
    pos=(pos-1)//2
    st[pos]=st[2*pos+1]|st[2*pos+2]
    st[pos].discard(x)
    
def query(l,r):
  tl=l+num
  tr=r+num
  ret=set()
  while tl<tr:
    if tr&1==1:
      tr-=1
      ret=ret|st[tr-1]
    if tl&1==1:
      ret=ret|st[tl-1]
      tl+=1
    tl=tl//2
    tr=tr//2
  return len(ret)

for i in range(n):
  update1(i,s[i])

q=int(input())
for _ in range(q):
  a,b,c=map(str,input().split())
  a=int(a)
  b=int(b)-1
  if a==1:
    if c==s[b]:
      continue
    update2(b,s[b])
    s[b-1]=c
    update1(b,c)
    print(st)
  elif a==2:
    c=int(c)-1
    print(query(b,c))