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:
#include <bits/stdc++.h>
using namespace std;
typedef long long int llint;
typedef unsigned long long int ullint;
std::string YesNo[] = {"No","Yes"};
#define loop(i,N) for(int i=0; i<(N); i++)
template<typename T>
auto sort_all(T& v) { return std::sort(v.begin(),v.end()); }
template<typename T>
auto sum_all(const T& v) { auto z = v[0]; z = 0;
    return std::accumulate(v.begin(),v.end(),z); }
template<typename T>
auto input( std::size_t N,
            const std::vector<T>& head={},
            const std::vector<T>& tail={}) {
    auto s = head.size();
    auto t = tail.size();
    std::vector<T> v;
    v.reserve(s+N+t);
    v.insert(v.end(), head.begin(), head.end());
    v.resize(s+N);
    loop(i,N) std::cin >> v[s+i];
    v.insert(v.end(), tail.begin(), tail.end());
    return std::move(v);
}
class range {
    typedef int Int;
    Int start, stop, step;
    void initialize() {
        auto sign = (step >= 0) ? 1 : -1;
        stop = start + ((stop-start-sign)/step + 1) * step;
        if ((stop-start) * step <= 0) stop = start;
    }
public:
    range(Int start, Int stop, Int step=1) : start(start), stop(stop), step(step) {
        initialize();
    }
    range(Int stop) : start(0), stop(stop), step(1) { initialize(); }
    struct iterator {
        Int i, step;
        Int& operator*() { return i; }
        iterator& operator++() { i += step; return *this; }
        bool operator!=(const iterator& v) { return i != v.i; }
    };
    iterator begin() { return {start, step}; }
    iterator end()   { return {stop, step}; }
};
template<typename T1, typename T2>
std::pair<T1,T2> operator-(const std::pair<T1,T2>& x)
{
    return std::make_pair(-x.first, -x.second);
}
template<typename T1, typename T2>
std::pair<T1,T2> operator+(
    const std::pair<T1,T2>& x,
    const std::pair<T1,T2>& y)
{
    return std::make_pair(x.first+y.first, x.second+y.second);
}
template<typename T1, typename T2>
std::pair<T1,T2> operator-(const std::pair<T1,T2>& x, const std::pair<T1,T2>& y)
{
    return x + (-y);
}
template<typename T1, typename T2>
std::pair<T1,T2>& operator+=(std::pair<T1,T2>& x, const std::pair<T1,T2>& y)
{
    x.first += y.first;
    x.second += y.second;
    return x;
}
template<typename T1, typename T2>
std::pair<T1,T2>& operator-=(std::pair<T1,T2>& x, const std::pair<T1,T2>& y)
{
    return x += (-y);
}
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& cout, const std::pair<T1,T2>& data)
{
    cout << "(" << data.first << ", " << data.second << ")";
    return cout;
}
template<typename T>
std::ostream& operator<<(std::ostream& cout, const std::vector<T>& data)
{
    cout << "[";
    if (data.size() == 0) {}
    else if (data.size() == 1) { cout << data[0]; } 
    else {
        cout << data[0];
        for (auto itr=data.begin()+1; itr!=data.end(); ++itr) {
            cout << ", " << *itr;
        }
    }
    cout << "]";
    return cout;
}

int bitlen(unsigned long long int n)
{
    int total = sizeof(n) * 8;
    int l = total, r = -1, mid;
    while (l > r+1) {
        mid = (l+r)/2;
        if (n >> mid == 0) {
            l = mid;
        } else {
            r = mid;
        }
    }
    return l;
}
template<typename T>
class SegmentTree
{
private:
// public:
    unsigned int N;
    T nullret = T(-1);
    std::vector<int> node;
    std::vector<T> data;
    std::function<bool(int,int)> comp;
    const std::function<bool(int,int)> defaultcomp = [this](int i, int j) {
        if (j < 0) {
            return true;
        } else if (i < 0) {
            return false;
        } else {
            return data[i] < data[j];
        }
    };

public:
    SegmentTree(unsigned int N_,
                const std::vector<T>& data_ = std::vector<T>(0),
                bool reverse = false,
                std::function<bool(int,int)> comp = nullptr
                ) : data(data_)
    {
        if (comp == nullptr) {
            comp = defaultcomp;
        }
        if (reverse) {
            this->comp = [comp] (int i, int j) { return comp(j,i); };
        } else {
            this->comp = [comp] (int i, int j) { return comp(i,j); };
        }
        
        unsigned int M = std::max((unsigned int)(data.size()), N_);
        N = 1 << std::max(bitlen(M)-1, 0);
        if (N < M) N *= 2;
        node.resize(2*N-1);
        for (auto i=0; i<data.size(); i++) {
            node[N-1+i] = i;
        }
        for (auto i=data.size(); i<N; i++) {
            node[N-1+i] = -1;
        }
        if (data.size() < N) { data.resize(N,T(0)); }

        for (int i=N-2; i>=0; i--) {
            auto left_i = node[2*i+1], right_i = node[2*i+2];
            node[i] = this->comp(left_i, right_i) ? left_i : right_i;
        }
    }

    T setnull(T t) { return nullret = t; }

    const T& at(int i) { return data[i]; }

    void update(int n, const T& v) {
        data[n] = v;
        int i = N - 1 + n;
        node[i] = n;
        while (i > 0) {
            i = (i-1)/2;
            // cout << i << " ";
            int left_i = node[2*i+1], right_i = node[2*i+2];
            // cout << left_i << " " << right_i << " ab" << endl;
            auto new_i = comp(left_i, right_i) ? left_i : right_i;
            // cout << left_i << " " << right_i << " " << new_i << " cd" << endl;
            if (new_i == node[i] && new_i != n) {
                // cout << "break at i=" << i << endl;
                break;
            } else {
                node[i] = new_i;
            }
        }
    }

    void emptify(int n) {
        int i = N - 1 + n;
        node[i] = -1;
        while (i > 0) {
            i = (i-1)/2;
            int left_i = node[2*i+1], right_i = node[2*i+2];
            auto new_i = comp(left_i, right_i) ? left_i : right_i;
            if (new_i == node[i] && new_i != n) {
                break;
            } else {
                node[i] = new_i;
            }
        }
    }

    const T& query(int l=0, int r=-1) {
        auto s = query_index(l, r);
        if (s < 0) { return nullret; } else { return data[s]; }
    }

    int query_index(int l=0, int r=-1) {
        if (r < 0) r = N;
        int L = l + N, R = r + N;
        int s = -1;
        while (L < R) {
            if (R & 1) {
                R -= 1;
                if (comp(node[R-1], s)) s = node[R-1];
            }
            if (L & 1) {
                if (comp(node[L-1], s)) s = node[L-1];
                L += 1;
            }
            L >>= 1; R >>= 1;
        }
        return s;
    }
};

typedef llint Int;

int main(void)
{
    unsigned int N, Q;
    string S;
    cin >> N >> S >> Q;
    vector<SegmentTree<int>> sg(26, SegmentTree<int>(N));
    // loop(i,4) cout << sg[i].data << " " << sg[i].node << endl;
    for (auto i: range(N)) {
        sg[int(S[i]-'a')].update(i,0);
    }
    // loop(i,4) cout << sg[i].data << " " << sg[i].node << endl;
    //cout << "abc" << endl;
    //cout << N << " " << S << " " << Q << endl;

    for (auto q: range(Q)) {
        int k;
        cin >> k;
        //cout << k << " " << s << " " << t << endl;
        //cout << "k=" << k << endl;
        if (k == 1) {
            int i; char c;
            cin >> i >> c;
            //cout << i;
            i--;
            if (S[i] != c) {
                sg[int(c-'a')].update(i,0);
                sg[int(S[i]-'a')].emptify(i);
                S[i] = c;
            }
        } else {
            int l, r;
            cin >> l >> r;
            l--;
            int ans = 0;
            for (auto c: range(26)) {
                if (sg[c].query(l,r) >= 0) {
                    ans += 1;
                }
            }
            cout << ans << endl;
        }
    }

    return 0;
}

Submission status: Runtime Error

Solution code:
import sys
def search(nums, v):
    l = 0
    r = len(nums)
    while l<r:
        mid = (l+r) // 2
        if nums[mid] > v:
            r = mid
        elif nums[mid] < v:
            l = mid + 1
        else:
            return mid
def lowerbound(nums, v):
    l = 0
    r = len(nums)
    while l < r-1:
        mid = (l+r) // 2
        if nums[mid] >= v:
            r = mid
        else:
            l = mid
    return l

n = int(sys.stdin.readline().strip())
s = list(sys.stdin.readline().strip())
q = int(sys.stdin.readline().strip())
pos = dict()
for c in "qwertyuiopasdfghjklzxcvbnm":
    pos[c] = []
for i, c in enumerate(s):
    pos[c].append(i)

for i in range(q):
    a, b ,c = sys.stdin.readline().strip().split()
    if a =="1":
        i = int(b)
        i -= 1
        origin_c = s[i]
        pos[origin_c].pop(search(pos[origin_c], i))
        if pos[c] == []:
            pos[c].append(i)
            continue
        if i < pos[c][0]:
            pos[c] = [i] + pos[c]
        elif i > pos[c][-1]:
            pos[c].append(i)
        else:
            pos[c].insert(lowerbound(pos[c], i), i)
        
    else:
        l, r = int(b), int(c)
        l-=1
        r-=1
        res = 0
        for c in pos:
            if len(pos[c]) < 1 or l > pos[c][-1] or r < pos[c][0]:
                continue
            res += 1
        print(res)

Submission status: Runtime Error

Solution code:
N=int(input())
from functools import reduce
size=int(N**.5+(1-1e-9))
a=[0]*size*size
b=[0]*size
f=lambda x,y:x|y
def init(v):
    a=v
    b=[reduce(f,a[j*size:(j+1)*size]) for j in range(size)]
    return a,b
def update(i,v):
    a[i]=v
    j=i//size
    b[j]=reduce(f,a[j*size:(j+1)*size])
def r_query(l,r):
    L,R=0--l//size,r//size
    if L>=R:
        return reduce(f,a[l:r])
    else:
        return reduce(f,a[l:L*size]+b[L:R]+a[R*size:r])
def c(n):
    r=0
    while n:
        r+=n&1
        n>>=1
    return r

o=lambda c:ord(c)-ord('a')
bit=[2**i for i in range(26)]
S=input()
Q=int(input())
XYZ=[input().split() for i in range(Q)]
a,b=init([bit[o(c)] for c in S])
for x,y,z in XYZ:
    if x=='1':
        update(int(y)-1,bit[o(z)])
    else:
        print(c(r_query(int(y)-1,int(z))))

Submission status: Runtime Error

Solution code:
N=int(input())
from functools import reduce
size=int(N**.5+(1-1e-9))
a=[0]*N
b=[0]*size
f=lambda x,y:x|y
def init(v):
    a=v
    b=[reduce(f,a[j*size:(j+1)*size]) for j in range(size)]
    return a,b
def update(i,v):
    a[i]=v
    j=i//size
    b[j]=reduce(f,a[j*size:(j+1)*size])
def r_query(l,r):
    L,R=0--l//size,r//size
    if L>=R:
        return reduce(f,a[l:r])
    else:
        return reduce(f,a[l:L*size]+b[L:R]+a[R*size:r])
def c(n):
    r=0
    while n:
        r+=n&1
        n>>=1
    return r

o=lambda c:ord(c)-ord('a')
bit=[2**i for i in range(26)]
S=input()
Q=int(input())
XYZ=[input().split() for i in range(Q)]
a,b=init([bit[o(c)] for c in S])
for x,y,z in XYZ:
    if x=='1':
        update(int(y)-1,bit[o(z)])
    else:
        print(c(r_query(int(y)-1,int(z))))

Submission status: Runtime Error

Solution code:
class SegmentTree:
	def __init__(self, n, *, init = None, data = None, merge = None):
		if init != None and data != None:
			raise Error("init and data cannot be specified at a time")
		if init == None and data == None:
			raise Error("one of init or data must be specified")
		self.n = n
		data_table = []
		if data:
			data_table.append((1, data))
		else:
			data_table.append((1, tuple(init(i, i + 1) for i in range(n))))
		
		w = 2
		if merge == None:
			while w <= n:
				data_table.append((w, tuple(init(i, i + w) for i in range(0, ((n - 1) // w + 1) * w, w))))
				w *= 2
		else:
			last_data = data_table[0][1]
			while w <= n:
				if len(last_data) % 2 == 0:
					new_data = tuple(merge(last_data[i * 2], last_data[i * 2 + 1]) for i in range(0, (n - 1) // w + 1))
				else:
					new_data = tuple(merge(last_data[i * 2], last_data[i * 2 + 1]) for i in range(0, (n - 1) // w)) + (last_data[-1], )
				data_table.append((w, new_data))
				last_data = new_data
				w *= 2
		self.data_table = data_table
		
	def data_at(self, i):
		for w, data_list in self.data_table:
			yield data_list[(i + 1) // w - 1]
	
	def data_range(self, s, e = None):
		if e == None:
			e = s
			s = 0
		if s == 0:
			for w, data_list in reversed(self.data_table):
				if e % (w * 2) >= w:
					yield data_list[e // w - 1]
		elif s < e:
			for w, data_list in self.data_table:
				w2 = w * 2
				m = s % w2
				new_s = s + w2 - m
				if new_s > e:
					break
				if m != 0:
					yield data_list[s // w]
					s = new_s
			if s == e:
				return
			for w, data_list in reversed(self.data_table):
				new_s = s + w
				if new_s <= e:
					yield data_list[s // w]
					s = new_s
			
			return
			for w, data_list in self.data_table:
#				print(f"({s} - {e})")
				w2 = w * 2
				m = s % w2
				if m != 0:
					yield data_list[s // w]
					s += w2 - m
					if s == e:
						break
				m = e % w2
				if m != 0:
					yield data_list[e // w - 1]
					e -= m
					if s == e:
						break
	
	def output(self, func):
		for w, data_list in self.data_table:
			print(f"#{w}: " + ", ".join(func(data) for data in data_list))


A = ord("a")
N = int(input())
S = list(map(lambda c: ord(c) - A, input().strip()))
Q = int(input())

def count(s, e):
	counts = [0] * 26
	for i in range(s, min(N, e)):
		counts[S[i]] += 1
	return counts

def merge(count1, count2):
	result = list(count1)
	for i in range(26):
		result[i] += count2[i]
	return result

st = SegmentTree(N, init = count, merge = merge)

for _ in range(Q):
	t, i, q = input().split()
	
	if t == "1":
		i = int(i) - 1
		q = ord(q) - A
		s = S[i]
		for data in st.data_at(i):
			data[s] -= 1
			data[q] += 1
		S[i] = q
	else:
		l = int(i) - 1
		r = int(q)
		result = [0] * 26
		for data in st.data_range(l, r):
			for i in range(26):
				result[i] += data[i]
		
		count = 0
		for i in range(26):
			if result[i] > 0:
				count += 1
#		st.output(lambda data: "".join(chr(A + j) + str(data[j]) if data[j] > 0 else "" for j in range(26)))
		
		print(count)

Submission status: Runtime Error

Solution code:
N=int(input())
S=input()
Q=int(input())
Qu=[input().split() for w in range(Q)]
def Query(a,b,c):
  if a==1:
    P=S[:b]+c+S[b+1:]
    print(S)
    return P
  
  else:
    c=int(c)
    L=S[b-1:c]
    
    print(len(set(L)))
    return S
    
    
for i in range(Q):
  S=Query(int(Qu[i][0]),int(Qu[i][1]),Qu[i][2])

Submission status: Runtime Error

Solution code:
import bisect

n = int(input())
s = list(input())
q = int(input())
l = [[] for i in range(26)]
for i in range(n):
    l[ord(s[i])-ord("a")].append(i)


for i in range(q):
    x,y,z = input().split()
    if int(x) == 1:
        if s[int(y)-1] == z:
            continue
        index = bisect.bisect_left(l[ord(s[int(y)-1])-ord("a")],int(y)-1)
        l[ord(s[int(y)-1])-ord("a")].pop(index)
        index = bisect.bisect_left(l[ord(z)-ord("a")],int(y)-1)
        l[ord(z)-ord("a")].insert(index,int(y)-1)
    if int(x) == 2:
        count = 0
        for j in l:
            index = bisect.bisect_left(j,int(y)-1)
            if index < len(j) and j[index] < int(z):
                count += 1
        print(count)

Submission status: Runtime Error

Solution code:
import bisect

n = int(input())
s = list(input())
q = int(input())
l = [[] for i in range(26)]
for i in range(n):
    l[ord(s[i])-ord("a")].append(i)
print(l)

for i in range(q):
    x,y,z = input().split()
    if int(x) == 1:
        if s[int(y)-1] == z:
            continue
        index = bisect.bisect_left(l[ord(s[int(y)-1])-ord("a")],int(y)-1)
        l[ord(s[int(y)-1])-ord("a")].pop(index)
        index = bisect.bisect_left(l[ord(z)-ord("a")],int(y)-1)
        l[ord(z)-ord("a")].insert(index,int(y)-1)
    if int(x) == 2:
        count = 0
        for j in l:
            index = bisect.bisect_left(j,int(y)-1)
            if index < len(j) and j[index] < int(z):
                count += 1
        print(count)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
n = int(input())
s = input()
N0 = 2**(n-1).bit_length()
INF = 2**31-1
data = [""]*(2*N0)
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = ope(data[2*k+1],data[2*k+2])
def query(l, r):
    L = l + N0; R = r + N0
    s = ""
    while L < R:
        if R & 1:
            R -= 1
            s = ope(s, data[R-1])

        if L & 1:
            s = ope(s,data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
  
def ope(x, y):
    r = []
    if type(x) is str and type(y) is str:
        r = [x, y]
    elif type(x) is str:
        r = [x] + y
    elif type(y) is str:
        r = x + [y]
    else:
        r = x + y

    return list(set(r))

for i in range(len(s)):
    update(i,s[i])

quenum = int(input())
ans=[]
for i in range(quenum):
    que, a, b = input().split()

    if que == "1":
        update(int(a)-1,b)
    else:
        ans.append(str(len(query(int(a)-1,int(b)))-1))
print("\n".join(ans))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
def solve():
  n,m,k = (int(i) for i in input().split())
  uff = UnionFind(n)
  ufb = UnionFind(n)
  query = [0]*n
  query2 = []
  for i in range(m):
    a,b = (int(i)-1 for i in input().split())
    uff.union(a,b)
    query[a] += 1
    query[b] += 1
    query2.append((a,b))
  for i in range(k):
    a,b = (int(i)-1 for i in input().split())
    if uff.same(a,b):
      ufb.union(a,b)
    query2.append((a,b))

  for i in range(n):
    print(uff.size(i)-1-query[i]-(ufb.size(i)-1), end=" ")
solve()

Submission status: Runtime Error

Solution code:
import sys
#input = sys.stdin.buffer.readline
import bisect

def main():
    N = int(input())
    S = list(str(input()))
    
    pos = [[] for _ in range(26)]
    for x,s in enumerate(S):
        num = ord(s)-ord("a")
        pos[num].append(x)
    
    q = int(input())
    for _ in range(q):
        m,a,b = map(str,input().split())
        if m == "1":
            a = int(a)-1
            if S[a] == b:
                continue
            else:
                popind = bisect.bisect_left(pos[ord(S[a])-ord("a")],a)
                pos[ord(S[a])-ord("a")].pop(popind)
                bisect.insort(pos[ord(b)-ord("a")],a)
        else:
            a,b = int(a)-1,int(b)
            count = 0
            for i in range(26):
                aind = bisect.bisect_left(pos[i],a)
                bind = bisect.bisect_left(pos[i],b)
                if bind-aind > 0:
                    count += 1
            print(count)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())
Query=[input.split() for i in range(Q)]

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]=seg[2*i+1]|seg[2*i+2]

def update(k,b):
    k += num-1
    if seg[k]=={b}:
        return ()
    seg[k] = {b}
    while k:
        k = (k-1)>>1
        seg[k] = 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=set()
    while q-p>1:
        if p&1 == 0:
            res = res|seg[p]
        if q&1 == 1:
            res = res|seg[q]
            q -= 1
        p = p>>1
        q = (q-1)>>1
    if p == q:
        res = res|seg[p]
    else:
        res = res|seg[p]|seg[q]
    return res

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

for i in range(N):
    seg[i+num-1]={ord(S[i])}
for k in range(num-2,-1,-1):
    seg[k] = seg[k*2+1]|seg[k*2+2]
for type, i, c in Query:
    if type=="1":
        update(int(i)-1,ord(c))
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)

Submission status: Runtime Error

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())


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,b):
    k += num-1
    if seg[k]==set([b]):
        return ()
    seg[k] = {b}
    while k:
        k = (k-1)>>1
        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>>1
        q = (q-1)>>1
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele =set()

#num:n以上の最小の2のべき乗
n=N
num =2**(n-1).bit_length()
seg=[set() for i in range(2*num)]

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

for q in range(Q):
    t, i, c = input().split()
    if type=="1":
        update(int(i)-1,ord(c))
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left, bisect_right, insort

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
S = '-' + sr()
d = [[] for _ in range(26)]
for i in range(1, N+1):
    s = S[i]
    o = ord(s) - ord('a')
    insort(d[o], i)

Q = ir()
for _ in range(Q):
    q, a, b = sr().split()
    if q == '1':
        a = int(a)
        if S[a] == b:
            continue
        prev = ord(S[a]) - ord('a')
        d[prev].remove(a)
        next = ord(b) - ord('a')
        insort(d[next], a)
    else:
        a = int(a); b = int(b)
        ans = 0
        for alpha in range(26):
            if bisect_right(d[alpha], b) - bisect_left(d[alpha], a) >= 1:
                ans += 1
        print(ans)

# 17

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left, bisect_right, insort
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
S = '-' + sr()
d = defaultdict(list)
for i in range(1, N+1):
    s = S[i]
    insort(d[s], i)

Q = ir()
for _ in range(Q):
    q, a, b = sr().split()
    if q == '1':
        a = int(a)
        if S[a] == b:
            continue
        prev = S[a]
        d[prev].remove(a)
        insort(d[b], a)
    else:
        a = int(a); b = int(b)
        ans = 0
        for alpha in d:
            if bisect_right(d[alpha], b) - bisect_left(d[alpha], a) >= 1:
                ans += 1
        print(ans)

# 17

Submission status: Runtime Error

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())
Query=[input().split() for i in range(Q)]


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,b):
    k += num-1
    if seg[k].pop()==b:
        return()
    seg[k].add(b)
    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 =set()

#num:n以上の最小の2のべき乗
n=N
num =2**(n-1).bit_length()
seg=[set() for i in range(2*num)]

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

for type,i,c in Query:

    if type=="1":
        update(int(i)-1,c)
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)

Submission status: Runtime Error

Solution code:
from typing import List


class SegmentTree:
    def __init__(self, a: List[bool], identity: bool = False):
        self.a = a
        self.n = len(a)
        self.identity = identity
        self.depth = (self.n - 1).bit_length
        self.segment = 1 << self.depth - 1
        self.tree = [identity] * (self.segment * 2 + 1)
        self.tree[self.segment : self.n + self.segment] = a
        for i in range(self.segment - 1, -1, -1):
            self.tree[i] = self.f(self.tree[2*i+1], self.tree[2*i+2])

    def update(self, i: int, x: bool):
        i += self.segment
        self.tree[i] = x
        while i:
            i = (i - 1) // 2
            self.tree[i] = self.f(self.tree[2*i+1], self.tree[2*i+2])

    def query(self, l: int, r: int) -> int:
        """Query at [l, r]

        Args:
            l (int): left
            r (int): right

        Returns:
            int: result
        """
        if l > r:
            return self.identity
        l += self.segment
        r += self.segment
        res = self.identity
        while l <= r:
            if not l & 1:
                res = self.f(self.tree[l], res)
            if r & 1:
                res = self.f(res, self.tree[r])
            l = l // 2
            r = (r - 2) // 2
        return res

    def f(self, x: bool, y: bool) -> bool:
        return x or y
      

n = int(input())
s = input()
q = int(input())
a = ord('a')
alph = [[c == chr(a + i) for c in s] for i in range(26)]
st_list = [SegmentTree(alph[i]) for i in range(26)]

for _ in range(q):
  query = input()
  if query[0] == '1':
    _, i, c = map(int, query.split())
    j = ord(c) - a
    for k, st in enumerate(st_list):
      st.update(i, j == k)
  else:
    _, l, r = map(int, query.split())
    ans = [st.query(l, r) for st in st_list]
    print(sum(ans))

Submission status: Runtime Error

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


class SegmentTree():
    def __init__(self, S):
        self.size = 19
        self.array = [set()] * (2**(self.size + 1) - 1)
        for i, c in enumerate(S):
            self.array[i + 2**self.size - 1] = {c}
        for i in range(2**self.size - 1)[::-1]:
            self.array[i] = self.array[2 * i + 1] | self.array[2 * i + 2]

    def subquery(self, l, r, k, i, j):
        # 区間[i,j)の中で区間[l,r)の文字列の集合を返す
        if j <= l or r <= i:
            return set()
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_set = self.subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_set = self.subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return l_set | r_set

    def query(self, l, r):
        # [l,r)に含まれる文字の種類数
        return len(self.subquery(l, r, 0, 0, 2**self.size))

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = {c}
        while tmp > 0:
            tmp = (tmp - 1) // 2
            self.array[tmp] = self.array[2 * tmp + 1] | self.array[2 * tmp + 2]


N = int(input())
S = [ord(_) - 97 for _ in list(input())]
Q = int(input())
tree = SegmentTree(S)
for q in range(Q):
    t, i, c = input().split()
    if t == '1':
    i = int(i) - 1
    tree.update(i, ord(c) - 97)
    else:
        l, r = int(i) - 1, int(c)
        print(tree.query(l, r))

Submission status: Runtime Error

Solution code:
def main():
  import sys
  from numpy import zeros
  input=sys.stdin.buffer.readline
  n=int(input())+1
  #data=zeros((n*2,26),int)
  data=[zeros(26,int)for _ in range(26)]
  def update(i,x):
    i+=n
    d=data[i]
    d[:]=0
    d[x]=1
    i//=2
    while i:
      data[i]=data[i*2]|data[i*2+1]
      i//=2
  def query(l,r):
    l+=n
    r+=n
    s=zeros(26,int)
    while l<r:
      if l&1:
        s|=data[l]
        l+=1
      if r&1:
        r-=1
        s|=data[r]
      l//=2
      r//=2
    return s.sum()
  for i,c in enumerate(input()[:-1],n):data[i][c-97]=1
  for i in range(n-1,0,-1):data[i]=data[i*2]|data[i-~i]
  s=[]
  for _ in range(int(input())):
    q,a,b=input().split()
    if q[0]>49:s+=query(int(a)-1,int(b)),
    else:update(int(a)-1,b[0]-97)
  print('\n'.join(map(str,s)))
main()

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:[] 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)