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: Accepted

Solution code:
import math


def _hasParents(i):
    return i > 1


def _isLeftChild(i):
    return i % 2 == 0


def _isRightChild(i):
    return i % 2 == 1


def _parentNode(i):
    return i // 2


def _leftChild(i):
    return 2 * i


def _rightChild(i):
    return 2 * i + 1


def _leftSibling(i):
    return i - 1


def _rightSibling(i):
    return i + 1


def _nextPowerOfTwo(n):
    ret = 1
    while ret < n:
        ret *= 2
    return ret


def ancestors(i):
    while _hasParents(i):
        i = _parentNode(i)
        yield i


"""
class Config(NamedTuple, Generic[T, A]):
    mconvert: Callable[[T], A]
    mappend: Callable[[A, A], A]
    mempty: Callable[[], A]
"""
from collections import namedtuple

Config = namedtuple("Config", ["mconvert", "mappend", "mempty"])


class SegmentTree:
    def __init__(self, arr, mconvert, mappend, mempty, minCapacity=1):
        def wrappedMconvert(x):
            if x is not None:
                return mconvert(x)
            else:
                return mempty()

        def wrappedMappend(x, y):
            xEmpty = x == mempty()
            if xEmpty:
                return y
            yEmpty = y == mempty()
            if yEmpty:
                return x
            if xEmpty and yEmpty:
                return mempty()
            return mappend(x, y)

        self.config = Config(
            mconvert=wrappedMconvert, mappend=wrappedMappend, mempty=mempty
        )

        # Init empty tree
        self.MAX_SIZE = _nextPowerOfTwo(max(len(arr), minCapacity))
        self.values = [None] * self.MAX_SIZE
        self.accumulations = [self.config.mempty()] * (2 * self.MAX_SIZE)
        self.numValues = 0

        # Init values
        self.values[: len(arr)] = arr
        self.numValues = len(arr)
        # Init leaf accumulations
        self.accumulations[self.MAX_SIZE : self.MAX_SIZE + len(arr)] = map(
            self.config.mconvert, arr
        )
        # Init parent accumulations
        for parent in range(self.MAX_SIZE - 1, -1, -1):
            self.accumulations[parent] = self.config.mappend(
                self.accumulations[_leftChild(parent)],
                self.accumulations[_rightChild(parent)],
            )

    def query(self, i, j):
        # Inclusive i, exclusive j
        if not (0 <= i <= j <= self.numValues):
            raise IndexError
        if i == j:
            return self.config.mempty()
        leftTotal = self.config.mempty()
        rightTotal = self.config.mempty()
        l = self.MAX_SIZE + i
        r = self.MAX_SIZE + j - 1  # make inclusive both endpoints for calculations
        while l <= r:
            if _isRightChild(l):
                leftTotal = self.config.mappend(leftTotal, self.accumulations[l])
                l = _rightSibling(l)
            l = _parentNode(l)

            if _isLeftChild(r):
                rightTotal = self.config.mappend(self.accumulations[r], rightTotal)
                r = _leftSibling(r)
            r = _parentNode(r)
        return self.config.mappend(leftTotal, rightTotal)

    def append(self, x):
        assert self.numValues + 1 <= self.MAX_SIZE
        self.numValues += 1
        self.__setitem__(self.numValues - 1, x)

    def pop(self, i=None):
        if i is not None:
            raise NotImplementedError
        if not self.numValues:
            raise IndexError
        ret = self.__getitem__(self.numValues - 1)
        self.__delitem__(self.numValues - 1)
        return ret

    def insert(self, i, x):
        raise NotImplementedError


    def __getitem__(self, index):
        if isinstance(index, slice):
            raise NotImplementedError
        if not 0 <= index < self.numValues:
            raise IndexError
        ret = self.values[index]
        assert ret is not None
        return ret


    def __setitem__(self, i, x):
        if isinstance(i, slice):
            raise NotImplementedError
        
        if not 0 <= i < self.numValues:
            raise IndexError
        index = self.MAX_SIZE + i
        self.values[i] = x
        self.accumulations[index] = self.config.mconvert(x)
        for parent in ancestors(index):
            self.accumulations[parent] = self.config.mappend(
                self.accumulations[_leftChild(parent)],
                self.accumulations[_rightChild(parent)],
            )
            parent = _parentNode(parent)


    def __delitem__(self, i):
        if isinstance(i, slice):
            raise NotImplementedError
        if not 0 <= i < self.numValues:
            raise IndexError
        index = self.MAX_SIZE + i
        self.values[i] = None
        self.accumulations[index] = self.config.mempty()
        for parent in ancestors(index):
            self.accumulations[parent] = self.config.mappend(
                self.accumulations[_leftChild(parent)],
                self.accumulations[_rightChild(parent)],
            )
        self.numValues -= 1

    def __len__(self):
        return self.numValues


def charToBitmask(c):
    return 1 << (ord(c) - ord("a"))


def popcount(n):
    # Python doesn't have __builtin_popcount
    return bin(n).count("1")


N, = list(map(int, input().split()))
S = [charToBitmask(c) for c in input().rstrip()]
Q, = list(map(int, input().split()))
queries = []
for i in range(Q):
    queries.append(input().split())


segTree = SegmentTree(S, lambda x: x, lambda mask1, mask2: mask1 | mask2, lambda: 0)
out = []
for query in queries:
    if query[0] == "1":
        _, i, c = query
        i = int(i) - 1
        segTree[i] = charToBitmask(c)
    elif query[0] == "2":
        _, l, r = query
        l = int(l) - 1
        r = int(r) - 1
        mask = segTree.query(l, r + 1)

        out.append(str(popcount(mask)))
print("\n".join(out))

Submission status: Accepted

Solution code:
class SegmentTree():
    def __init__(self,arr,func=min,ie=2**63):
        self.n = 2**(len(arr)-1).bit_length()
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2*self.n)]
        for i in range(len(arr)):
            self.tree[self.n+i-1] = arr[i]
        for i in range(self.n-1)[::-1]:
            self.tree[i] = func(self.tree[2*i+1],self.tree[2*i+2])

    def set(self,index,x):
        index += self.n-1
        tree = self.tree
        func = self.func
        tree[index] = x
        while index:
            index = (index-1)//2
            tree[index] = func(tree[2*index+1],tree[2*index+2])

    def query(self,left,right):
        ie = self.ie
        tree = self.tree
        func = self.func
        if right <= left:
            return ie
        left += self.n-1
        right += self.n-2
        tmp_l = self.ie
        tmp_r = self.ie
        while right-left>1:
            if left & 1 == 0:
                tmp_l = func(tmp_l,tree[left])
            if right & 1 == 1:
                tmp_r = func(tree[right],tmp_r)
                right -= 1
            left = left//2
            right = (right-1)//2
        if left == right:
            tmp_l = func(tmp_l,tree[left])
        else:
            tmp_l = func(func(tmp_l,tree[left]),tree[right])
        return func(tmp_l,tmp_r)

import sys
input = sys.stdin.readline

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

A = []
for i in range(N):
    A.append(set([ord(S[i])-97]))

def func(x,y):
    return x|y
ie = set()

st = SegmentTree(A,func,ie)

ans = []

for _ in range(Q):
    q,x,y = input().split()
    q = int(q)
    if q == 1:
        st.set(int(x)-1,set([ord(y)-97]))
    else:
        ans.append(len(st.query(int(x)-1,int(y))))

print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
S = list(input())[: -1]
Q = int(input())

class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)

fwks = [BIT(N + 1) for _ in range(26)]
a = ord("a")
for i in range(N):
  j = ord(S[i]) - a
  #print(j)
  fwks[j].add(i + 1, 1)
for _ in range(Q):
  q, x, y = input().split()
  q = int(q)
  if q == 1:
    x = int(x)
    for i in range(26):
      if fwks[i].get(x): fwks[i].add(x, -1)
    fwks[ord(y) - a].add(x, 1)
  else:
    x = int(x)
    y = int(y)
    res = 0
    #print(x, y)
    for i in range(26):
      res += fwks[i].get(x - 1, y) > 0
    print(res)

Submission status: Accepted

Solution code:
class BinaryIndexedTree():
    def __init__(self, N):
        self.N = N
        self.arr = [0] * (N+1)

    def query(self, i):
        ret = 0
        i += 1
        while i:
            ret += self.arr[i]
            lsb = i & (-i)
            i -= lsb
        return ret

    def add(self, i, v):
        i += 1
        while i < self.N+1:
            lsb = i & (-i)
            self.arr[i] += v
            i += lsb

    def search(self, x):
        lo = -1
        hi = self.N
        while lo < hi:
            mid = (lo+hi)//2
            if self.query(mid) < x:
                lo = mid + 1
            else:
                hi = mid
        return lo


def c2i(c):
    return ord(c) - ord('a')


def main():
    N = int(input())
    S = list(input())
    bits = [BinaryIndexedTree(N) for _ in range(26)]
    for i, c in enumerate(S):
        bits[c2i(c)].add(i, 1)
    Q = int(input())
    for _ in range(Q):
        t, x, y = input().split()
        if t == "1":
            i = int(x) - 1
            bits[c2i(S[i])].add(i, -1)
            bits[c2i(y)].add(i, 1)
            S[i] = y
        else:
            l, r = int(x), int(y)
            ans = 0
            for i in range(26):
                cs = bits[i].query(r-1)
                if l-2 >= 0:
                    cs -= bits[i].query(l-2)
                if cs >= 1:
                    ans += 1
            print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools, operator
N = int(input())
S = [ord(s) - 97 for s in input()]
Q = int(input())
Query = [input().split() for _ in range(Q)]
cntraw = [[0] * (N + 1) for _ in range(26)]
for i, v in enumerate(S):
    cntraw[v][i + 1] = 1


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        res = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                res = f(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = f(dat[r], res)
            l >>= 1
            r >>= 1
        return res


sts = [SegmentTree(cntraw[i], f=operator.add, ti=0) for i in range(26)]
for query in Query:
    if query[0] == '1':
        i, c = query[1:]
        i = int(i)
        for st in sts:
            st.update(i, 0)
        sts[ord(c) - 97].update(i, 1)
    else:
        l, r = [int(_) for _ in query[1:]]
        r += 1
        print(sum(st.query(l, r) > 0 for st in sts))

Submission status: Accepted

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


class BIT:
    def __init__(self, size):
        self.bit = [0]*(size+1)
        self.size = size

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

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.bit[i] += x
            i += i & -i


N = int(input())
S = list(input().rstrip())
bits = [BIT(N) for _ in range(26)]
for i in range(N):
    bits[ord(S[i])-ord('a')].add(i, 1)
Q = int(input())
for _ in range(Q):
    t, x, y = input().split()
    if t == '1':
        i = int(x) - 1
        c = y
        bits[ord(S[i])-ord('a')].add(i, -1)
        bits[ord(c)-ord('a')].add(i, 1)
        S[i] = c
    else:
        l = int(x) - 1
        r = int(y) - 1
        ans = 0
        for i in range(26):
            cnt = bits[i].sum(r) - (bits[i].sum(l-1) if l > 0 else 0)
            if cnt > 0:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
def examA():
    N = I()
    ans = N//2 + N%2
    print(ans)
    return

def examB():
    A = [LI()for _ in range(3)]
    N = I()
    B = [I()for _ in range(N)]
    grid = [[False]*3 for _ in range(3)]
    ans = "No"
    for b in B:
        for i in range(3):
            for j in range(3):
                if A[i][j]==b:
                    grid[i][j] = True
    for i in range(3):
        flag = True
        for j in range(3):
            if not grid[i][j]:
                flag = False
        if flag:
            ans = "Yes"
    for i in range(3):
        flag = True
        for j in range(3):
            if not grid[j][i]:
                flag = False
        if flag:
            ans = "Yes"
    flag = True
    for i in range(3):
        if not grid[i][i]:
            flag = False
    if flag:
        ans = "Yes"
    flag = True
    for i in range(3):
        if not grid[i][2-i]:
            flag = False
    if flag:
        ans = "Yes"
    print(ans)
    return

def examC():
    N, M = LI()
    S = [LI()for _ in range(M)]
    ans = [-1]*N
    for s,c in S:
        s -= 1
        if ans[s]!=-1:
            if ans[s]!=c:
                print(-1)
                return
        ans[s] = c
    A = ""
    if ans[0]==0 and N>=2:
        print(-1)
        return
    elif ans[0]==-1 and N>=2:
        ans[0] = 1
    for i in ans:
        if i==-1:
            A += str(0)
        else:
            A += str(i)
    print(A)
    return

def examD():
    class UnionFind():
        def __init__(self, n):
            self.parent = [-1 for _ in range(n)]
            # 正==子: 根の頂点番号 / 負==根: 連結頂点数

        def find(self, x):
            # 要素xが属するグループの根を返す
            if self.parent[x] < 0:
                return x
            else:
                self.parent[x] = self.find(self.parent[x])
                return self.parent[x]

        def unite(self, x, y):
            # 要素xが属するグループと要素yが属するグループとを併合する
            x, y = self.find(x), self.find(y)
            if x == y:
                return False
            else:
                if self.size(x) < self.size(y):
                    x, y = y, x
                self.parent[x] += self.parent[y]
                self.parent[y] = x

        def same(self, x, y):
            # 要素x, yが同じグループに属するかどうかを返す
            return self.find(x) == self.find(y)

        def size(self, x):
            # 要素xが属するグループのサイズ（要素数）を返す
            x = self.find(x)
            return -self.parent[x]

        def is_root(self, x):
            # 要素の根をリストで返す
            return self.parent[x] < 0

        def roots(self):
            # すべての根の要素をリストで返す
            return [i for i, x in enumerate(self.parent) if x < 0]

        def members(self, x):
            # 要素xが属するグループに属する要素をリストで返す
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def group_count(self):
            # グループの数を返す
            return len(self.roots())

        def all_group_members(self):
            # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
            return {r: self.members(r) for r in self.roots()}

    N, M, K = LI()
    uf = UnionFind(N)
    B = [0]*N
    for _ in range(M):
        a, b = LI()
        B[a-1] += 1
        B[b-1] += 1
        uf.unite(a-1,b-1)
    block = []
    for _ in range(K):
        c, d = LI()
        c -= 1
        d -= 1
        if uf.same(c,d):
            B[c] += 1
            B[d] += 1
    ans = [0]*N
    check = [-1]*N
    for i in range(N):
        root = uf.find(i)
        if check[root]==-1:
            size = uf.size(root)
            check[root] = size
        else:
            size = check[root]
        ans[i] += size-1
        ans[i] -= B[i]
        if ans[i]<0:
            ans[i] = 0
    #print(check)
    print(" ".join(map(str,ans)))
    return

def examE():
    # 一点更新、区間取得
    class segment_():
        def __init__(self, A, n, segfunc, ide_ele=0):
            #####単位元######要設定0or1orinf
            self.ide_ele = ide_ele
            ####################
            self.num = 1 << (n - 1).bit_length()
            self.seg = [self.ide_ele] * 2 * self.num
            self.segfunc = segfunc
            # set_val
            for i in range(n):
                self.seg[i + self.num] = A[i]
                # built
            for i in range(self.num - 1, 0, -1):
                self.seg[i] = self.segfunc(self.seg[2 * i], self.seg[2 * i + 1])

        def update(self, k, r):
            k += self.num
            self.seg[k] = r
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        # 値xに1加算
        def update1(self, k):
            k += self.num
            self.seg[k] += 1
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def updateneg1(self, k):
            k += self.num
            self.seg[k] -= 1
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def query(self, p, q):
            # qは含まない
            if q < p:
                return self.ide_ele
            p += self.num;
            q += self.num
            res = self.ide_ele
            while p < q:
                if p & 1 == 1:
                    res = self.segfunc(res, self.seg[p])
                    p += 1
                if q & 1 == 1:
                    q -= 1
                    res = self.segfunc(res, self.seg[q])
                p >>= 1;
                q >>= 1
            return res

    def popcnt0(n):
        c = 0
        for i in range(27):
            c += (n >> i) & 1
        return c
    N = I()
    S = SI()
    Q = I()
    a = ord('a')
    A = [0] * (N+1)
    for i in range(N):
        A[i] = 1<<(ord(S[i]) - a)
    Seg_sum = segment_(A, N+1, lambda a, b: a | b)
    ans = []
    for _ in range(Q):
        q = LSI()
        if q[0]=="1":
            cur = 1<<(ord(q[2])-a)
            Seg_sum.update(int(q[1])-1,cur)
        else:
            cur = Seg_sum.query(int(q[1])-1,int(q[2]))
            ans.append(popcnt0(cur))
            #print(cur)
    #print(A)
    for v in ans:
        print(v)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Accepted

Solution code:

class BinaryIndexedTree:
    def __init__(self, size):
        size = 1 << (size-1).bit_length()
        self.data = [0] * (size+1)
        self.size = size
    
    def add(self, i, w):
        i += 1
        while i <= self.size:
            self.data[i] += w
            i += i & -i

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

    __getitem__ = sum

    def lower_bound(self, v):
        """
        return smallest i such that v < sum(data[:i])
        """

        s,pos = 0,0
        N = self.size
        k = N
        while k > 0:
            i = pos+k
            if i <= N:
                x = s+self.data[i]
                if x < v:
                    s = x
                    pos = i
            k >>= 1
        return pos

N = int(input())
S = input()
S = list(ord(c)-ord('a') for c in S)
bits = tuple(BinaryIndexedTree(N) for _ in range(26))

for i,c in enumerate(S):
    bit = bits[c]
    bit.add(i, 1)


def q1(i, c):
    i = int(i)-1
    bit = bits[S[i]]
    bit.add(i,-1)
    c = ord(c)-ord('a')
    bit = bits[c]
    bit.add(i,1)
    S[i] = c
def q2(l,r):
    l,r = int(l)-1,int(r)
    print(sum(bit.sum(r) > bit.sum(l) for bit in bits))


Q = int(input())
for _ in range(Q):
    q,x,y = input().split()

    if q == '1':
        q1(x,y)
    else:
        q2(x,y)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    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

    N = int(input())
    S = input().rstrip('\n')
    Q = int(input())

    S = [s for s in S]

    bit = [Bit(N) for _ in range(26)]
    for i, s in enumerate(S):
        j = ord(s) - 97
        bit[j].add(i+1, 1)
    for _ in range(Q):
        flg, l, r = input().split()
        if flg == '1':
            i = int(l)
            c = r
            si = S[i-1]
            bit[ord(si)-97].add(i, -1)
            bit[ord(c)-97].add(i, 1)
            S[i-1] = c
        else:
            l = int(l)
            r = int(r)
            ans = 0
            for j in range(26):
                if bit[j].sum(r) - bit[j].sum(l-1):
                    ans += 1
            print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())

ss = list(input())
s = []
for i in range(n):
    s.append(1<<(ord(ss[i])-97))

#####segfunc######
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,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

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

init(s)


def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

q = int(input())

for i in range(q):
    qq,xx,yy = map(str,input().split())
    if qq == '1':
        xx = int(xx)
        update(xx-1,1<<(ord(yy)-97))
    else:
        xx,yy = int(xx),int(yy)
        res = query(xx-1,yy)
        print(popcnt(res))

Submission status: Accepted

Solution code:
N = int(input())
def idx(s):
    return ord(s)-97

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

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

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

d = {}
for i in range(26):
    d[i] = BIT(N)

S = input()
for i in range(N):
    d[idx(S[i])].add(i,1)
S = list(S)
Q = int(input())
for _ in range(Q):
    q = input().split()
    if q[0]=='1':
        i = int(q[1])-1
        s = S[i]
        d[idx(s)].add(i,-1)
        S[i] = q[2]
        d[idx(q[2])].add(i,1)
    else:
        l,r = int(q[1])-1,int(q[2])-1
        res = 0
        for i in range(26):
            c = d[i].sum(r)
            if l!=0:
                c -= d[i].sum(l-1)
            c = min(1,c)
            res += c
        print(res)

Submission status: Accepted

Solution code:

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める

    if a == 0:
        return 0
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret


alp = "abcdefghijklmnopqrstuvwxyz"

al = {}

for i in range(26):
    al[alp[i]] = i

N = int(input())

BITS = [ [0] * (N+1) for i in range(26) ]

S = list(input())

for i in range(N):

    bitadd(i+1,1,BITS[al[S[i]]])

Q = int(input())
for i in range(Q):

    qs,x,y = input().split()
    qs = int(qs)
    
    if qs == 1:
        x = int(x)
        bitadd(x,-1,BITS[al[S[x-1]]])
        bitadd(x,1,BITS[al[y]])
        S[x-1] = y

    else:
        x = int(x)
        y = int(y)

        ans = 0
        for j in range(26):
            ans += min(1 , bitsum(y,BITS[j]) - bitsum(x-1,BITS[j]))

        print (ans)

Submission status: Accepted

Solution code:
class BIT: #0-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length()
        self.n0 = 1<<self.depth
#        self.element = [0]*(n+1)
    def get_sum(self, i): #a_0 + ... + a_{i} #閉区間
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def query(self,l,r): #a_l + ... + a_r 閉区間
        return self.get_sum(r) - self.get_sum(l-1) 
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        # self.element[i] += x
    #def get(self,i): return element[i]        
    def bisect_left(self,w):
        #和が w 以上になる最小の index
        #w が存在しない場合 self.size を返す
        if w <= 0: return 0
        x,k = 0,self.n0
        for _ in range(self.depth):
            k >>= 1
            if x+k <= self.size and self.tree[x+k] < w:
                w -= self.tree[x+k]
                x += k
        return x


# coding: utf-8
# Your code here!

import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n,*a = [int(i) for i in read().split()]
#a = [int(i) for i in readline().split()]
#n = int(input())


n,s,q,*query = read().split()
n = int(n)
q = int(q)

B = [BIT(n) for _ in range(26)]

SS = list(map(lambda x: ord(x)-97,s))
for i,c in enumerate(SS):
    B[c].add(i,1)

for I in range(q):
    l,r,c = query[3*I:3*(I+1)]
    l = int(l)
    r = int(r)-1
    
    if l == 1:
        z = ord(c)-97
        B[SS[r]].add(r,-1)
        B[z].add(r,1)
        SS[r] = z
    else:
        c = int(c)-1
        res = 0
        for i in range(26):
            if B[i].query(r,c):
                res += 1
        print(res)

Submission status: Accepted

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
from operator import or_

n=int(input())
s=input()
li=[1<<ord(x)-97 for x in s[:-1]]
seg=SegmentTree(li,or_,0)
ans=[]
for _ in range(int(input())):
	f,x,y=input().split()
	if f=="1":
		x=int(x)
		seg.update(x-1,1<<ord(y)-97)
	else:
		x=int(x)
		y=int(y)
		z=seg.find(x-1,y)
		cnt=0
		for i in range(26):
			if z & (1<<i):
				cnt+=1
		ans.append(cnt)
print(*ans)