Problem p02763 (python)

Fixed submission:
#!python3

import sys

from bisect import bisect, insort_left

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    c0 = ord('a')
    S1 = [[] for i in range(26)]
    for i, c1 in enumerate(S):
        ci = ord(c1) - c0
        S1[ci].append(i)

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            if S[i] == j:
                continue

            c1 = ord(S[i]) - c0
            s1 = S1[c1]
            s1.pop(bisect(s1, i)-1)
            S[i] = j
            c1 = ord(j) - c0
            insort_left(S1[c1], i)
        elif cmd == "2":
            j = int(j) - 1
            num = 0

            for s1 in S1:
                ls = len(s1)
                k = bisect(s1, i-1, 0, ls)

                if k == ls:
                    continue
                if i <= s1[k] <= j:
                    num += 1

            ans.append(num)

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys

iim = lambda: map(int, input().rstrip().split())

def popcnt2(n):
    a = (
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
    )
    ans = 0
    while n:
        ans += a[n&0xff]
        n >>= 8
    return ans

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    c0 = ord('a')
    smap = [1<<(i-c0) for i in range(c0, ord('z')+1)]

    T = [0]*N + [smap[ord(S[i])-c0] for i in range(N)]

    for i in range(N-1, 0, -1):
        i2 = i << 1
        T[i] = T[i2] | T[i2|1]

    ans = []
    #print(T)
    for cmd, i, j in (line.split() for line in sys.stdin.read().split("\n")):
        i = int(i) - 1
        if cmd == "1":
            if S[i] == j:
                continue

            S[i] = j
            i0 = N + i
            T[i0] = smap[ord(j)-c0]
            while i0 > 1:
                i0 = i0 >> 1
                T[i0] = T[i0+i0] | T[i0-~i0]
        elif cmd == "2":
            i += N
            j = int(j) + N

            d1 = 0
            while i < j:
                if i & 1:
                    d1 |= T[i]
                    i += 1
                if j & 1:
                    j -= 1
                    d1 |= T[j]

                i >>= 1; j >>=1

            ans.append(popcnt2(d1))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys

from bisect import bisect, insort_left

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    c0 = ord('a')
    S1 = [[] for i in range(26)]
    for i, c1 in enumerate(S):
        ci = ord(c1) - c0
        S1[ci].append(i)

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            if S[i] == j:
                continue

            c1 = ord(S[i]) - c0
            s1 = S1[c1]
            s1.pop(bisect(s1, i))
            S[i] = j
            c1 = ord(j) - c0
            insort_left(S1[c1], i)
        elif cmd == "2":
            j = int(j) - 1
            num = 0

            for s1 in S1:
                ls = len(s1)
                k = bisect(s1, i-1, 0, ls)

                if k == ls:
                    continue
                if i <= s1[k] <= j:
                    num += 1

            ans.append(num)

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
from functools import reduce
from operator import or_
from collections import defaultdict

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    N=len(S)
    lo, hi = 100, N//2
    md = 1
    while lo < hi:
        md = (lo+hi) // 2
        if md**2 < N:
            lo = md + 1
        else:
            hi = md
    nn = lo
    S1 = [None] * nn

    for i in range(nn):
        sd = S1[i] = defaultdict(int)
        i1 = i * nn
        for j in range(i1, min(N, i1+nn)):
            sd[S[j]] += 1

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            c1 = S[i]
            i1 = i // nn
            S1[i1][c1] -= 1
            S[i] = j
            S1[i1][j] += 1
        elif cmd == "2":
            j = int(j)

            ia, ib = divmod(i, nn)
            ja, jb = divmod(j, nn)

            if ib > 0:
                ia += 1
            if ia < ja:
                ss = set()
                ss = reduce(or_, (k for i1 in range(ia, ja) for k, v in S1[i1].items() if v > 0), ss)

                if ib > 0:
                    for i1 in range(i, i-ib+nn):
                        ss.add(S[i1])
                if jb > 0:
                    for i1 in range(ja*nn, j):
                        ss.add(S[i1])
            else:
                ss = set(S[k] for k in range(i, j))

            ans.append(len(ss))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
from functools import reduce
from operator import or_

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    N=len(S)
    lo, hi = 0, N//2
    md = 1
    while lo < hi:
        md = (lo+hi) // 2
        if md**2 < N:
            lo = md + 1
        else:
            hi = md
    nn = md+1
    S1 = [None] * nn

    for i in range(nn):
        ii = i * nn
        S1[i] = set(S[j] for j in range(ii, min(N, ii+nn)))

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            ii = i // nn
            S[i] = j
            i2 = ii * nn
            S1[ii] = set(S[k] for k in range(i2, min(N, i2+nn)))
        elif cmd == "2":
            j = int(j)
            ia, ib = divmod(i, nn)
            ja, jb = divmod(j, nn)

            if ib > 0:
                ia += 1
            ss = set()
            ss = reduce(or_, (S1[i1] for i1 in range(ia, ja)), ss)

            if ib > 0:
                for i1 in range(i, i-ib+nn):
                    ss.add(S[i1])
            if jb > 0:
                for i1 in range(ja*nn, j):
                    ss.add(S[i1])

            ans.append(len(ss))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
from functools import reduce
from operator import or_

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    lo, hi = 0, N//2
    md = 1
    while lo < hi:
        md = (lo+hi) // 2
        if md**2 < N:
            lo = md + 1
        else:
            hi = md
    nn = md+1
    S1 = [None] * (nn+1)

    for i in range(N//nn):
        ii = i * nn
        S1[i] = set(S[j] for j in range(ii, min(N, ii+nn)))

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            ii = i // nn
            S[i] = j
            i2 = ii * nn
            S1[ii] = set(S[k] for k in range(i2, min(N, i2+nn)))
        elif cmd == "2":
            j = int(j)
            ia, ib = divmod(i, nn)
            ja, jb = divmod(j, nn)

            if ib > 0:
                ia += 1
            ss = set()
            ss = reduce(or_, (S1[i1] for i1 in range(ia, ja)), ss)

            if ib > 0:
                for i1 in range(i, i-ib+nn):
                    ss.add(S[i1])
            if jb > 0:
                for i1 in range(ja*nn, j):
                    ss.add(S[i1])

            ans.append(len(ss))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
from functools import reduce
from operator import or_

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    lo, hi = 0, N//2
    while lo < hi:
        md = (lo+hi) // 2
        if md**2 < N:
            lo = md + 1
        else:
            hi = md
    nn = md+1
    S1 = [None] * (nn+1)

    for i in range(N//nn+1):
        ii = i * nn
        S1[i] = set(S[j] for j in range(ii, min(N, ii+nn)))

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            ii = i // nn
            S[i] = j
            i2 = ii * nn
            S1[ii] = set(S[k] for k in range(i2, min(N, i2+nn)))
        elif cmd == "2":
            j = int(j)
            ia, ib = divmod(i, nn)
            ja, jb = divmod(j, nn)

            if ib > 0:
                ia += 1
            ss = set()
            ss = reduce(or_, (S1[i1] for i1 in range(ia, ja)), ss)

            if ib > 0:
                for i1 in range(i, i-ib+nn):
                    ss.add(S[i1])
            if jb > 0:
                for i1 in range(ja*nn, j):
                    ss.add(S[i1])

            ans.append(len(ss))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()