Problem: 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).

Submission attempts (in order):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


class SegmentTree:
    def __init__(self, A):
        self.n = 2**(len(A)-1).bit_length()
        self.identity = set()
        self.seg = [self.identity] * (2 * self.n)
        
        for i, a in enumerate(A):
            self.seg[self.n-1+i] = set(a)
        for i in range(self.n-2,-1,-1):
            self.seg[i] = self.seg[2*i+1] | self.seg[2*i+2]

            
    def update(self, k, a):
        k += self.n - 1
        self.seg[k] = set(a)
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.seg[k*2+1] | self.seg[k*2+2]

            
    def query(self, a, b):
        if b == a:
        	return 1
        a += self.n - 1
        b += self.n - 2
        res = self.identity
        while b - a > 1:
            if a & 1 == 0:
                res = res | self.seg[a]
            if b & 1 == 1:
                res = res | self.seg[b]
                b -= 1
            a = a // 2
            b = (b - 1) // 2
        if a == b:
            res = res | self.seg[a]
        else:
            res = res | self.seg[a] | self.seg[b]
        
        return len(res)


def main():
    N = int(readline())
    s = readline().strip()
    seg = SegmentTree(list(s))
    print(seg.seg)

    Q = int(readline())
    for _ in range(Q):
        q, a, b = map(str, readline().split())
        if q == "1":
            seg.update(int(a)-1, b)
        else:
            print(seg.query(int(a)-1, int(b)))


if __name__ == "__main__":
    main()


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


def string_to_number(a):
    return 1 << (ord(a) - 97)

class SegmentTree:
    def __init__(self, A):
        self.n = 2**(len(A)-1).bit_length()
        self.identity = 0
        self.seg = [self.identity] * (2 * self.n)
        
        for i, a in enumerate(A):
            self.seg[self.n-1+i] = string_to_number(a)
        for i in range(self.n-2,-1,-1):
            self.seg[i] = self.seg[2*i+1] | self.seg[2*i+2]

            
    def update(self, k, a):
        k += self.n - 1
        self.seg[k] = string_to_number(a)
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.seg[k*2+1] | self.seg[k*2+2]

            
    def query(self, a, b):
        if b == a:
        	return 1
        a += self.n - 1
        b += self.n - 2
        res = self.identity
        while b - a > 1:
            if not a & 1:
                res |= self.seg[a]
            if b & 1:
                res |= self.seg[b]
                b -= 2
            a >>= 1
            b -= 1
            b >>= 1
        if a == b:
            res |= self.seg[a]
        else:
            res |= (self.seg[a] | self.seg[b])
        
        return bin(res).count("1")


def main():
    N = int(readline())
    s = readline().strip()
    seg = SegmentTree(list(s))
    print(seg.seg)

    Q = int(readline())
    q = map(str, read().split())
    for t, a, b in zip(*[iter(q)]*3):
        if t == "1":
            seg.update(int(a)-1, b)
        else:
            print(seg.query(int(a)-1, int(b)))


if __name__ == "__main__":
    main()


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


def string_to_number(a):
    return 1 << (ord(a) - 97)

class SegmentTree:
    
    def __init__(self, n, initial=0):
        self.offset = 2**(n-1).bit_length()
        self.initial = initial
        self.seg = [self.initial] * (2 * self.offset)


    def build(self, A):
        
        for i, a in enumerate(A, start=self.offset):
            self.seg[i] = string_to_number(a)
        for i in range(self.offset-1,0,-1):
            self.seg[i] = self.seg[i<<1] | self.seg[(i<<1)+1]

            
    def update(self, k, a):
        k += self.offset
        self.seg[k] = string_to_number(a)
        while k:
            k >>= 1
            self.seg[k] = self.seg[k<<1] | self.seg[(k<<1)+1]

            
    def query(self, a, b):
        a += self.offset
        b += self.offset
        res = self.initial
        while a < b:
            if a & 1:
                res |= self.seg[a]
                a += 1
            if b & 1:
                res |= self.seg[b-1]
            a >>= 1
            b >>= 1
        
        return bin(res).count("1")


def main():
    N,s,Q,*q = read().split()
    seg = SegmentTree(int(N))
    seg.build(s)
    

    for t, a, b in zip(*[iter(q)]*3):
        if t == "1":
            seg.update(int(a)-1, b)
        else:
            print(seg.query(int(a)-1, int(b)))


if __name__ == "__main__":
    main()


Verdicts: Wrong Answer

Wrong Answer

Accepted