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;

// 変数ダンプ先。coutかcerr
#define DUMPOUT cerr

// 提出時はコメントアウト
#define DEBUG_

// #define int long long // intで書いたけど心配なときにlong longに変換する
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

/* cpp template {{{ */

/* short */
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)
#define X real()
#define Y imag()

/* REPmacro */
#define REPS(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define REP(i, n) REPS(i, 0, n)
#define RREP(i, n) REPS(i, 1, n + 1)
#define DEPS(i, a, n) for (ll i = (a); i >= (ll)(n); --i)
#define DEP(i, n) DEPS(i, n, 0)
#define EACH(i, n) for (auto&& i : n)

/* debug */
#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';

/* alias */
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
using D = double;
using P = complex<D>;
using vs = vector<string>;
template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

/* const */
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;
const D EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

/* func */
inline bool inside(int y, int x, int H, int W) {return y >= 0 && x >= 0 && y < H && x < W;}
inline int in() {int x; cin >> x; return x;}
inline ll IN() {ll x; cin >> x; return x;}
inline vs split(const string& t, char c) {vs v; stringstream s(t); string b; while(getline(s, b, c)) v.eb(b); return v;}
template <typename T> inline bool chmin(T& a, const T& b) {if (a > b) a = b; return a > b;}
template <typename T> inline bool chmax(T& a, const T& b) {if (a < b) a = b; return a < b;}
template <typename T, typename S> inline void print(const pair<T, S>& p) {cout << p.first << " " << p.second << endl;}
template <typename T> inline void print(const T& x) {cout << x << '\n';}
template <typename T, typename S> inline void print(const vector<pair<T, S>>& v) {for (auto&& p : v) print(p);}
template <typename T> inline void print(const vector<T>& v, string s = " ") {REP(i, v.size()) cout << v[i] << (i != (ll)v.size() - 1 ? s : "\n");}
// clang-format on
/* }}} */

#ifdef DEBUG_
#define DEB
#else
// DEB と打つとデバッグ時以外はコメントアウトになる
#define DEB /##/
#endif

// 変数ダンプ用マクロ。デバッグ時以外は消滅する
// 引数はいくつでもどんな型でも可（ストリーム出力演算子があればOK）
#define dump(...) DEB DUMPOUT<<"  "; \
DUMPOUT<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"<<endl; \
DUMPOUT<<"    "; \
dump_func(__VA_ARGS__)

// デバッグ用変数ダンプ関数
void dump_func() {
    DUMPOUT << endl;
}
template <class Head, class... Tail>
void dump_func(Head&& head, Tail&&... tail)
{
    DUMPOUT << head;
    if (sizeof...(Tail) == 0) {
        DUMPOUT << " ";
    }
    else {
        DUMPOUT << ", ";
    }
    dump_func(std::move(tail)...);
}

// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec) {
    os << "{";
    for (int i = 0; i<vec.size(); i++) {
        os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}

int acount[5000005][26];
int ac[26];
int acl[26];
int acr[26];

signed main() {
    ll N; cin >> N;
    char S[N]; cin >> S;
    char Scopy[N];
    ll Q; cin >> Q;

    REP(i, 26) {
        acount[0][i] = 0;
    }

    REP(i, N) {
        REP(j, 26) {
            ac[j] = acount[i][j];
        }
        ac[S[i]-'a'] += 1;
        REP(j, 26) {
            acount[i+1][j] = ac[j];
        }
    }

    vector<pair<int, char>> qvec;
    int qtype;
    int i;
    char c;
    int l, r;
    REP(q, Q) {
        cin >> qtype;
        if (qtype == 1) {
            cin >> i >> c;
            qvec.push_back(make_pair(i, c));
        } else {
            cin >> l >> r;
            REP(i, 26) {
                acl[i] = acount[l-1][i];
            }
            REP(i, 26) {
                acr[i] = acount[r][i];
            }
            REP(i, 26) {
                ac[i] = acr[i] - acl[i];
            }
            REP(i, N) {
                Scopy[i] = S[i];
            }
            for(auto x: qvec){
                i = x.Fi;
                c = x.Se;
                if (l <= i && i <= r && Scopy[i-1] != c) {
                    ac[Scopy[i-1] - 'a']--;
                    ac[c - 'a']++;
                    Scopy[i-1] = c;
                }
            }
            int alpha_count = 0;
            REP(i, 26) {
                if(ac[i] > 0) {
                    alpha_count++;
                }
            }
            cout << alpha_count << endl;
        }
    }
}

// https://github.com/kurokoji/.cpp-Template/wiki テンプレートについて
// http://www.creativ.xyz/dump-cpp-652 dump()について
// https://gist.github.com/rigibun/7905920 色々

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
Q = int(input())
for _ in range(Q):
  t, i, c = map(str, input().split())
  t = int(t)
  i = int(i)
  if t==1 and S[i-1]!=c:
    S.insert(i-1, c)
    S.pop(i)
  elif t==2:
    c = int(c)
    print(len(set(S[i-1:c])))

Submission status: Runtime Error

Solution code:
import collections

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

uq = [0]*(N+1)
r_uq = [0]*(N+1)
d = {}
for i in range(len(S)):
  d[S[i]] = 1
  uq[i+1] = len(d)
uq[0] = 0

MAX = len(d)

d = {}
r_S = S[::-1]
for i in range(len(r_S)):
  d[r_S[i]] = 1
  r_uq[i+1] = len(d)
r_uq[0] = 0

#print(uq)
#print(r_uq)
r_uq = r_uq[::-1]

for i in range(Q):
  q = list(input().split())
  if q[0] == '1':
    S[int(q[1])-1] = q[2]
    MAX = collections.Counter(S)
  else:
    s = S[(int(q[1])):(int(q[2])+1)]
    
    print(MAX - uq[(int(q[1])-1)] - r_uq[(int(q[2]))])

Submission status: Runtime Error

Solution code:
n = int(input())
S = str(input())
Q = int(input())
alp = 'abcdefghijklmnopqrstuvwxyz'
for i in range(Q):
  t,m,p = map(str,input().split())
  t = int(t)
  m = int(m)
  C = [0] * 26
  ans = 0
  if t == 2:
    p = int(p)
    St = S[m-1:p]
    for i in St:
      if C[alp.index(i)] == 0:
        ans += 1
        C[alp.index(i)] = 1
    print(ans)
  else:
    St = list(S)
    St[m-1] = p
    S = St
    print(S)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
from collections import defaultdict

N = int(input())
S = input()
Q = int(input())
X = [input().split() for _ in range(Q)]

d = defaultdict(list)
for i in range(N):
    d[S[i]].append(i + 1)
    
ss = list(S)
for t, i, c in X:
    if t == "1":
        i = int(i)
        
        # Delete index
        d[ss[i - 1]].remove(i)
        ss[i - 1] = c

        # Insert index
        d[c].insert(bisect_left(d[c], i), i)
    else:
        l = int(i)
        r = int(c)
        
        res = 0
        for key in d:
            l_idx = bisect_left(d[key], l)
            r_idx = bisect_left(d[key], r)
            res += int((l_idx < r_idx) or (l_idx == 0 and l <= d[key][l_idx] <= r))

        print(res)

Submission status: Runtime Error

Solution code:
N=int(input())
S=list(input())
Q=int(input())
for _ in range(Q-1):
    R=list(input().split())
    if int(R[0])==1:
        S[int(R[1])]=R[2]
    if int(R[0])==2:
        print(len(set(S[int(R[1]):int(R[2])])))

Submission status: Runtime Error

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

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

for i in range(Q)
    t, a, b = map(int, input().split())
    if t == 1:
        s[a] = b
    else:
        sub_s = s[a:b+1]
        print(len(set(sub_s)))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Jan 24 14:37:00 2020

@author: matsui
"""

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

L=0
query=[]
for i in range(Q):
    q=input().split()
    L+=int(q[0])
    query.append(q)


abc=[chr(i) for i in range(97,123) ]

if L<N*1.5:
    for i in range(Q):
    #q=input().split()
    q=query[i]
    if int(q[0])==1:
        S[int(q[1])-1] = q[2]

    if int(q[0])==2:
        txt=S[int(q[1]):int(q[2])+1]
        dp=[0]*26
        for s in txt:
            index=abc.index(s)
            dp[index]+=1
        ans=0
        for a in dp:
            if a!=0: ans+=1
        print(ans)


else:
    import numpy as np
    dp=np.zeros([N+1,26])

    for i in range(1,N+1):
        index=abc.index(S[i-1])
        dp[i,:]=dp[i-1,:]
        dp[i,index]+=1

    for i in range(Q):
        #q=input().split()
        q=query[i]
        if int(q[0])==1:
            if S[int(q[1])-1] != q[2]:
                index1=abc.index(S[int(q[1])-1])
                index2=abc.index(q[2])
                for j in range(int(q[1]),N+1): 
                    dp[j,index1]-=1
                    dp[j,index2]+=1

        if int(q[0])==2:
            res=dp[int(q[2]),:]-dp[int(q[1])-1,:]
            ans=0
            for a in res:
                if a!=0: ans+=1
            print(ans)

Submission status: Runtime Error

Solution code:
import math
import collections

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


def bit_add(A,a,w): #リストAのa番目にwを足す
    ind = a

    while len(A) > ind:
        A[ind] += w
        lsb = ind & (-ind)
        # print(ind)
        ind += lsb

    return

def bit_sum(A, a):  # リストAのa番目までの和を取る
    s = 0
    ind = a
    while ind != 0:
        s += A[ind]
        lsb = ind & (-ind)
        ind -= lsb

    return s
# cs = set(list(S))
li = {}
for c in "abcdefghijklmnopqrstuvwxyz":
    li[c] = [0] * (N + 1)

for i in range(1,N + 1):
    char = S[i - 1]
    bit_add(li[char],i,1)

# li → 1 スタート
# S → 0スタート
Q = int(input())
queries = [input().split() for _ in range(Q)]
for query in queries:
    a,b,c = query
    a = int(a)
    b = int(b)
    if a == 1: # 書き換え
        i = b

        c_org = S[i - 1] # 元の文字
        # li[c_org][i] -= 1
        S[i - 1] = c
        bit_add(li[c_org], i,  -1)#元の文字をbiマイナス
        bit_add(li[c], i, 1) #新たな文字をbiプラス

    if a == 2:
        ans = 0
        l = b
        r = int(c)
        for c in "abcdefghijklmnopqrstuvwxyz":
            temp = li[c]
            r_sum = bit_sum(temp,r)
            l_sum = bit_sum(temp,l - 1)
            diff = r_sum-l_sum
            if diff > 0: # ある文字
                ans += 1
        print(ans)

Submission status: Runtime Error

Solution code:
import math
def main():
    N = int(input())
    S = input()
    S = [ord(i) - ord('a') for i in S]
    Q = int(input())
    n = int(math.sqrt(N))
    L = [[0] * 26 for _ in range(1 + N//n)]
    t = 0
    for i, v in enumerate(S):
        L[t][v] += 1
        if i % n == n-1:
            t += 1
    for _ in range(Q):
        a, b, c = input().split()
        if a == '1':
            x = S[int(b)-1]
            L[int(b)//n][x] -= 1
            L[int(b)//n][ord(c)-ord('a')] += 1
        else:
            i = int(b) - 1
            r = [0] * 26
            x = i // n
            if i % n == 0 and i + t < int(c):
                r = L[x]
            while True:
                if i % n == 0:
                    break
                else:
                    r[S[i]] += 1
                    i += 1
            while i < int(c):
                if i + t < int(c):
                    x += 1
                    r = [p + q for p, q in zip(r, L[x])]
                    i += t
                else:
                    r[S[i]] += 1
                    i += 1
            print(sum(1 if i > 0 else 0 for i in r))
main()

Submission status: Runtime Error

Solution code:
n = int(input())
s = list(input())
q = int(input())
ds = [[0]*26]
dq = dict()

for i in range(n):
    d = ds[i].copy()
    d[ord(s[i]) - ord('a')] += 1
    ds += [d]


def list_sub(l1, l2):
    ret = []
    for i in range(min(len(l1), len(l2))):
        ret += [l1[i] - l2[i]]
    return ret


def list_add(l1, l2):
    ret = []
    for i in range(min(len(l1), len(l2))):
        ret += [l1[i] + l2[i]]
    return ret


def list_len(l):
    ret = 0
    for x in l:
        if x > 0:
            ret += 1
    return ret

ans = []
for i in range(q):
    a,b,c = input().split()

    if a == '1':
        b = int(b) - 1
        if b not in dq:
            dq[b] = [0] * 26
        er = s[b]
        dq[b][ord(c) - ord('a')] += 1
        dq[b][ord(er) - ord('a')] -= 1
        s[b] = c

    if a == '2':
        b = int(b) - 1
        c = int(c) - 1
        d = list_sub(ds[c+1], ds[b])

        l = sorted(list(dq.items()))
        for k,v in l:
            if c < k:
                break
            if k < b:
                d = list_sub(d, v)
            else:
                d = list_add(d, v)
        ans += [list_len(d)]
for x in ans:
    print(x)

Submission status: Runtime Error

Solution code:
from collections import  Counter

n=int(input())
s=input()
q=int(input())
cnt=[]
for i in range(q):
    #print(s)
    f=list(map(str,input().split()))
    if int(f[0])==1:
        s=s[:int(f[1])-1]+str(f[2])+s[int(f[1]):]
    elif int(f[0])==2:
        l=int(f[1])
        r=int(f[2])
        tmp=s[l-1:r]
        cnt.append(tmp)

for i in range(len(cnt)):
    tm = Counter(cnt[i])
    ans = len(tm.keys())
    print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import numpy as np


def count_substr(s, l, r):
    cnt = 0
    for row in s:
        if l == 0:
            if row[r] > 0:
                cnt += 1
        else:
            if row[r] - row[l-1] > 0:
                cnt += 1
    return cnt


n = int(input())
s = list(input())
sc = np.zeros((26, n), dtype=int)
base = ord('a')
s = list(map(lambda x: ord(x)-base, s))

sc[0][s[0]] = 1
for i, c in enumerate(s[1:]):
    ii = i+1
    for j in range(26):
        if j == c:
            sc[j][ii] = sc[j][i] + 1
        else:
            sc[j][ii] = sc[j][i]

q = int(input())
for _ in range(q):
    i, j, k = input().split()
    i = int(i)
    if i == 1:
        iq = int(j) - 1
        cq = ord(k) - base
        old = s[iq]
        sc[cq, iq:] += 1
        sc[old, iq:] -= 1
    else:
        lq = int(j) - 1
        rq = int(k) - 1
        print(count_substr(sc, lq, rq))

Submission status: Runtime Error

Solution code:
from functools import lru_cache

class UnionFind(object):
    "https://www.kumilog.net/entry/union-find"
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

N, M, K = map(int, input().split(" "))


uf = UnionFind(N)
fr = {}
for _ in range(M):
    a, b = map(int, input().split(" "))
    a -= 1
    b -= 1
    uf.union(a, b)
    if fr.get(a) is not None:
        fr[a] += 1
    else:
        fr[a] = 1

    if fr.get(b) is not None:
        fr[b] += 1
    else:
        fr[b] = 1

bl = {}
for _ in range(K):
    c, d = map(int, input().split(" "))
    c -= 1
    d -= 1
    if not uf.is_same(c, d):
        continue

    if bl.get(c) is not None:
        bl[c] += 1
    else:
        bl[c] = 1

    if bl.get(d) is not None:
        bl[d] += 1
    else:
        bl[d] = 1


for i in range(N):
    s = uf.get_size(i) - 1

    s -= bl.get(i, 0)

    s -= fr.get(i, 0)
    print(s)

Submission status: Runtime Error

Solution code:
import sys
def case1(li, x, c):
    if li[x-1] != c:
        li[x-1] = c
    return li


def case2(li, start, end):
    s = set(li[start-1:end])
    sys.stdout.write(len(s))


i = int(input())  # skip this
char_list = [x for x in input()]
Q = int(input())

for i in range(Q):
    tokens = [int(x) if x.isdigit() else x for x in sys.stdin.readline().split()]
    if tokens[0] == 1:
        char_list = case1(char_list, tokens[1], tokens[2])
    elif tokens[0] == 2:
        case2(char_list, tokens[1], tokens[2])

Submission status: Runtime Error

Solution code:
# ABC157e


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

    #####segfunc######
    def segfunc(x, y):
        return x.union(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 = set()

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

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

    for _ in range(q):
        a, b, c = input().split()
        b = int(b)
        if int(a) == 1:
            update(b, set(c))
        else:
            c = int(c)
            print(len(query(b, c+1)))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
s = list(input())
q = int(input())
ds = [[0]*26]
dq = dict()

for i in range(n):
    d = ds[i].copy()
    d[ord(s[i]) - ord('a')] += 1
    ds += [d]


def list_sub(l1, l2):
    ret = []
    for i in range(min(len(l1), len(l2))):
        ret += [l1[i] - l2[i]]
    return ret


def list_add(l1, l2):
    ret = []
    for i in range(min(len(l1), len(l2))):
        ret += [l1[i] + l2[i]]
    return ret


def list_len(l):
    ret = 0
    for x in l:
        if x > 0:
            ret += 1
    return ret

ans = []
for i in range(q):
    a,b,c = input().split()

    if a == '1':
        b = int(b) - 1
        if b not in dq:
            dq[b] = [0] * 26
        er = s[b]
        dq[b][ord(c) - ord('a')] += 1
        dq[b][ord(er) - ord('a')] -= 1
        s[b] = c

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 = [()] * (2 * N)

n = 1
while n < N:
    n *= 2

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

def query(a, b, k, l, r):
    if r <= a or b <= l:
        return ()
    if a <= l and r <= b:
        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-1, n-1+N):
    update(i-n-1, S[i-n-1])

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

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
INF = float("inf")

# Binary Indexed Tree
class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N+1)
    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x
    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

N = int(input())
S = list(input())
Q = int(input())
bit = [BIT(N) for i in range(26)]
for i in range(N):s
    bit[ord(S[i])-97].add(i+1, 1)
for i in range(Q):
    q, x, y = input().split()
    q = int(q)
    if q == 1:
        i = int(x)-1
        bit[ord(S[i])-97].add(i+1, -1)
        S[i] = y
        bit[ord(y)-97].add(i+1, 1)
    else:
        l, r, ans = int(x), int(y), 0
        for i in range(26):
            ans += (bit[i].sum(r)-bit[i].sum(l-1))> 0
        print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2000)

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())
 
 
n, m, k = map(int,input().split())
friends=[0]*n
uf = UnionFind(n)
for i in range(m):
    a, b = map(int,input().split())
    uf.union(a-1, b-1)
    friends[a-1]+=1
    friends[b-1]+=1
 
nowlist=list(uf.all_group_members().values())
 
koho=[0]*n
group=[0]*n
number=1
pp=0
for i in range(n):
    if friends[i]>0:
        group[i]=uf.find(i)
        koho[i]=uf.size(i)
    else:
        group[i]=9999999+pp
        koho[i]=1
        pp+=1

for i in range(k):
    c, d = map(int,input().split())
    if group[c-1]==group[d-1]:
        koho[c-1]-=1
        koho[d-1]-=1
 
for i in range(n):
    print(koho[i]-friends[i]-1, end=" ")

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
n = int(input())
s = input()
quenum = int(input())
q = []
for i in range(quenum):
    q.append(input().split())

N0 = 2**(n-1).bit_length()
INF = 2**31-1
data = [set()]*(2*N0)
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = data[2*k+1]  | data[2*k+2]
def query(l, r):
    L = l + N0; R = r + N0
    s = set()
    while L < R:
        if R & 1:
            R -= 1
            s = s | data[R-1]

        if L & 1:
            s = s |  data[L-1]
            L += 1
        L >>= 1; R >>= 1
    return s

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

for que in q:
    if que[0] == "1":
        update(int(que[1])-1,set([que[2]]))
    else:
        print(len(query(int(que[1])-1,int(que[2]))))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	S = input()
	S = S[:-1]
	Q = inputInt()

	for i in range(Q):
		print(S)
		Oo = input()
		Oo = Oo[:-1]
		O = Oo.split()
		o1 = int(O[0])
		o2 = int(O[1])
		if o1 == 1:
			o3 = O[2]
			S1 = S[:o2-1]
			S2 = S[o2:]
			S = S1 + o3 + S2
		else:
			o3 = int(O[2])
			tmp = S[o2-1:o3]
			c = collections.Counter(tmp)
			print(len(c))

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

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 = [()] * (2 * N)

n = 1
while n < N:
    n *= 2

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

def query(a, b, k, l, r):
    if r <= a or b <= l:
        return ()
    if a <= l and r <= b:
        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-1, n-1+N):
    update(i-n-1, S[i-n-1])

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

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
from collections import defaultdict

N = int(input())
S = input()
Q = int(input())
X = [input().split() for _ in range(Q)]

d = defaultdict(list)
for i in range(N):
    d[S[i]].append(i + 1)

for t, i, c in X:
    if t == "1":
        i = int(i)
        
        # Delete index
        for key in d:
            if i in d[key]:
                d[key].remove(i)

        # Insert index
        d[c].insert(bisect_left(d[c], i), i)
    else:
        l = int(i)
        r = int(c)
        
        res = 0
        for key in d:
            l_idx = bisect_left(d[key], l)
            r_idx = bisect_left(d[key], r)
            res += int((l_idx < r_idx) or (l_idx == 0 and l <= d[key][l_idx] <= r))

        print(res)