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: Time Limit Exceeded

Solution code:
n=int(input())
ss=input()
dps=['a']*n
from collections import defaultdict
d=defaultdict(list)
for i in range(n):
    d[ss[i]].append(i)
    dps[i]=ss[i]
sorted(d.items())

Q=int(input())
import bisect
for i in range(Q):
    num,ii,c=input().split()
    #print(d)
    if num=='1':
        if c==dps[int(ii)-1]:
            continue
        idx=bisect.bisect_left(d[c],int(ii)-1)
        d[c].insert(idx,int(ii)-1)
        d[c].sort()
        d[dps[int(ii)-1]].remove(int(ii)-1)
        dps[int(ii)-1]=c
    else:
        l,r=int(ii)-1,int(c)-1
        count=0
        for k,lst in d.items():
            idx=bisect.bisect_left(lst,l)
            idx1=bisect.bisect_right(lst,r)
            count+=((idx1-idx)>0)
            #print(lst,l,r,count)
        print(count)
        pass

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def f(S, alp, a, b):
  out=0
  for nums in alp:
    p=np.searchsorted(nums, a, side='left')
    if p<len(nums) and nums[p]<b:
      out+=1
  return out

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

alp=[[] for i in range(26)]
alphabet='abcdefghijklmnopqrstuvwxyz'
def alp2num(s):
  return alphabet.index(s)

for i in range(N):
  alp[alp2num(S[i])].append(i)

S=list(S)
ans=[]
for _ in range(Q):
  x, y, z=input().split()
  x=int(x)
  y=int(y)
  if x==1:
    alp[alp2num(S[y-1])].remove(y-1)
    t=alp2num(z)
    tmp=np.searchsorted(alp[t], y-1, side='left')
    alp[t]=alp[t][:tmp]+[y-1]+alp[t][tmp:]
    S[y-1]=z
  else:
    z=int(z)
    ans.append(f(S, alp, y-1, z))
    
ans=[str(ans[i]) for i in range(len(ans))]
print('\n'.join(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
Q = int(input())

def count_chars(s):
  d = set()
  for c in s:
    d.add(c)
  return len(d)

for _ in range(Q):
  q, i, cr = input().split()
  i = int(i)
  if q == '1':
    if S[i - 1] != cr:
    	S = S[:i - 1] + cr + S[i:]
  else:  # q == 2
    print(count_chars(S[i - 1:int(cr)]))

Submission status: Time Limit Exceeded

Solution code:
import collections

N = int(input())

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

A = [list(map(str,input().split())) for i in range(Q)]

for i in range(Q):
    #a, b, c = map(str,input().split())
    if A[i][0] == '1':
        S[int(A[i][1])-1] = A[i][2]
    else:
        print(len(collections.Counter(S[int(A[i][1])-1:int(A[i][2])])))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    s = list(input())
    q = int(input())
    qry = []
    for _ in range(q):
        qq  = input().split()
        qry.append(qq)
    for i, query in enumerate(qry):
        if int(query[0]) == 1:
            s[int(query[1])-1] = query[2]
        else:
            tmp = s[int(query[1])-1:int(query[2])]
            print(len(set(tmp)))

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
from fractions import gcd 
from functools import reduce
import sys
sys.setrecursionlimit(200000000)
from inspect import currentframe


# my functions here!
#標準エラー出力
def printargs2err(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' : '+repr(arg) for arg in args),file=sys.stderr)






def printglobals():
    for (symbol, value) in globals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
def printlocals():
    for (symbol, value) in locals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
#入力（後でいじる）
def pin(type=int):
    return map(type,input().split())
     
#input
from collections import Counter 
def resolve():
    N,=pin()
    S=list(input())
    Q,=pin()
    for q in range(Q):
        a,b,c=input().split()
        if a=="1":
            S[int(b)-1]=c
        elif a=="2":
            
            #print(S[int(b)-1:int(c)])
            x = Counter(S[int(b)-1:int(c)])
            values, counts = zip(*x.most_common())
            print(len(values))
            
    #print([["NA","YYMM"],["MMYY","AMBIGUOUS"]][cMMYY][cYYMM])
#if __name__=="__main__":resolve()

"""
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7"""
        output = """3
1
5"""
        self.assertIO(input, output)

if __name__=="__main__":resolve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(str(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]=set(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()

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

init(s)
#print(seg)

for i in range(q):
    t, x, y = map(str, input().split())
    if t == '1':
        i = int(x)-1
        c = set(y)
        update(i, c)
    else:
        l = int(x)-1
        r = int(y)-1
        print(len(query(l, r+1)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
s = []
A = [[] for i in range(26)]
for i in range(N):
    x = S[i]
    s.append(x)
    n = ord(x) - 97
    A[n].append(i)
Q = int(input())
import bisect
for i in range(Q):
    q,a,b = map(str,input().split())
    a = int(a)
    a -= 1
    if q == '1':
        x = s[a]
        s[a] = b
        A[ord(x)-97].remove(a)
        A[ord(b)-97].append(a)
    if q == '2':
        ans = 0
        b = int(b)
        b -= 1
        for i in range(26):
            B = A[i]
            B.sort()
            p = bisect.bisect_left(B,a)
            q = bisect.bisect_right(B,b)
            if q - p > 0:
                ans += 1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict


class SegTree:
    def __init__(self, n, s):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [defaultdict(lambda: 0) for _ in range(n2 << 1)]

        for i, c in enumerate(s):
            x = ord(c) - 97
            i += self.offset
            while i > 0:
                self.tree[i][x] += 1
                i >>= 1
        # print(*(dict(t) for t in self.tree), sep='\n')

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        if x in self.tree[i]:
            return
        y, _ = self.tree[i].popitem()
        self.tree[i][x] = 1
        i >>= 1
        while i > 0:
            sti = self.tree[i]
            sti[x] += 1
            if sti[y] == 1:
                del sti[y]
            else:
                sti[y] -= 1
            i >>= 1

    def get_types(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = set()

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result.update(self.tree[r - 1].keys())
            if l & 1:
                result.update(self.tree[l].keys())
                l += 1
            l >>= 1
            r >>= 1

        return len(result)


n = int(input())
s = input()
st = SegTree(n, s)
q = int(input())
ans = []
for line in sys.stdin:
    i, j, k = line.rstrip().split()
    if i == '1':
        j = int(j) - 1
        k = ord(k) - 97
        st.update(j, k)
    else:
        l = int(j) - 1
        r = int(k)
        ans.append(st.get_types(l, r))
print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
Q = int(input())
ans = []
for i in range(Q):
    a = list(input().split()) 
    if a[0] == "1":
        S[int(a[1])-1] = a[2]
    else:
        ans.append(len(set(S[int(a[1])-1:int(a[2])])))
for j in range(len(ans)):
    print(ans[j])

Submission status: Time Limit Exceeded

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

def main():
    n=int(input())
    s=list(input())
    q=int(input())
    for i in range(q):
        a,b,c=map(str,input().split())
        if a=='1':
            s[int(b)-1]=c
        else:
            print(len(set(s[int(b)-1:int(c)])))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import ceil, log2

def getMid(s, e):
    return s + (e - s) // 2

def getSumUtil(st, ss, se, qs, qe, si):
    if qs <= ss and qe >= se:
        return st[si]

    if se < qs or ss > qe:
        return 0

    mid = getMid(ss, se)

    return getSumUtil(st, ss, mid, qs, qe, 2 * si + 1) + \
           getSumUtil(st, mid + 1, se, qs, qe, 2 * si + 2)

def updateValueUtil(st, ss, se, i, diff, si):
    if i < ss or i > se:
        return

    st[si] = st[si] + diff

    if se != ss:
        mid = getMid(ss, se)
        updateValueUtil(st, ss, mid, i, diff, 2 * si + 1)
        updateValueUtil(st, mid + 1, se, i, diff, 2 * si + 2)

def updateValue(arr, st, n, i, new_val):
    diff = new_val - arr[i]

    arr[i] = new_val

    updateValueUtil(st, 0, n - 1, i, diff, 0)

def getSum(st, n, qs, qe):
    return getSumUtil(st, 0, n - 1, qs, qe, 0)

def constructSTUtil(arr, ss, se, st, si):
    if ss == se:
        st[si] = arr[ss]
        return arr[ss]

    mid = getMid(ss, se)

    st[si] = constructSTUtil(arr, ss, mid, st, si * 2 + 1) + \
             constructSTUtil(arr, mid + 1, se, st, si * 2 + 2)

    return st[si]

def constructST(arr, n):
    x = ceil(log2(n))

    max_size = 2 * (2 ** x) - 1

    st = [0] * max_size

    constructSTUtil(arr, 0, n - 1, st, 0)

    return st

n = int(input())
s = list(input())

arrs = [[0] * n for _ in range(26)]

for i in range(n):
    j = ord(s[i]) - ord('a')

    arrs[j][i] = 1

segs = [constructST(arrs[i], n) for i in range(26)]

for _ in range(int(input())):
    t = input().split()

    if t[0] == '1':
        i, c = t[1:]
        i = int(i) - 1

        cur = ord(s[i]) - ord('a')

        s[i] = c

        new = ord(s[i]) - ord('a')

        updateValue(arrs[cur], segs[cur], n, i, 0)
        updateValue(arrs[new], segs[new], n, i, 1)

    if t[0] == '2':
        l, r = map(int, t[1:])
        l -= 1
        r -= 1

        ans = 0

        for i in range(26):
            x = getSum(segs[i], n, l, r)

            if x > 0:
                ans += 1

        print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())
    query = [input().split() for _ in range(Q)]

    for q in query:
        if q[0] == '1':
            idx = int(q[1]) - 1
            S[idx] = q[2]
        elif q[0] == '2':
            idx1 = int(q[1]) - 1
            idx2 = int(q[2]) - 1
            print(len(set(S[idx1:idx2+1])))

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  n = int(input())
  s = list(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,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()

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

  A = []
  for i in range(n):
    A.append(set(s[i]))
  init(A)
  q = int(input())
  for _ in range(q):
    p,a,b = input().split()
    if p == "1":
      update(int(a)-1,set(b))
    if p == "2":
      print(len(query(int(a)-1,int(b))))
main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

def solve(S,a,b):
    #print("Solve",S[a:b],set(S[a:b]))
    return len(set(S[a:b]))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    N=int(input())
    S=list(input())
    Q=int(input())
    for i in range(Q):
        t,a,b=input().split()
        if t=="2": print(solve(S,int(a)-1,int(b)))
        if t=="1": S[int(a)-1]=b
        #print("#",N,S,i)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
Q = int(input())

for q in range(Q):
  a,b,c = input().split()
  
  if a=="1":
    S = S[:int(b)-1]+c+S[int(b):]
  else:
    print(len(set(S[int(b)-1:int(c)])))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(input())
q=int(input())

for _ in range(q):
    m,l,r=input().split()
    
    if m=='1':
        s[int(l)-1]=r
    else:
        print(len(set(s[int(l)-1:int(r)])))

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  N = int(input())
  s = list(input())
  # N: 処理する区間の長さ
  N0 = 2**(N-1).bit_length()
  id_ele = set()
  data = [id_ele]*(2*N0)
  # a_k の値を x に更新
  def segfunc(x,y):
      return x|y

  def update(k, x):
      k += N0-1
      data[k] = x
      while k >= 0:
          k = (k - 1) // 2
          data[k] = segfunc(data[2*k+1], data[2*k+2])
  # 区間[l, r)の最小値
  def query(l, r):
      L = l + N0; R = r + N0
      s = id_ele
      while L < R:
          if R & 1:
              R -= 1
              s = segfunc(s, data[R-1])

          if L & 1:
              s = segfunc(s, data[L-1])
              L += 1
          L >>= 1; R >>= 1
      return s

  for i in range(N):
    update(i,set(s[i]))
  q = int(input())
  for _ in range(q):
    p,a,b = input().split()
    if p == "1":
      update(int(a)-1,set(b))
    if p == "2":
      print(len(query(int(a)-1,int(b))))
main()

Submission status: Time Limit Exceeded

Solution code:
import sys

class RMQ(): #range minimum query
    def __init__(self, N, V): #create segment tree with initial value V
        d, k = 1, 0
        while d < N:
            d <<= 1
            k += 1
        self.tree = [V for _ in range(2 * d - 1)]
        self.size = d 
    
    def update(self, i, a): #update cell i by value a
        now = self.size - 1 + i
        if self.tree[now] != a:
            self.tree[now] = a
            while now > 0:
                now = (now - 1) // 2
                self.tree[now] = self.tree[2 * now + 1] | self.tree[2 * now + 2]

    def search(self, lower, higher, lbound, hbound, pos): #search minimum value of [lower, higher) init: lbound = 0, hbound = self.size, pos = 0
        if higher <= lbound or hbound <= lower: return 0
        if lower <= lbound and hbound <= higher: return self.tree[pos]
        else:
            left = self.search(lower, higher, lbound, (lbound + hbound) // 2, 2 * pos + 1)
            right = self.search(lower, higher, (lbound + hbound) // 2, hbound, 2 * pos + 2)
            return left | right


def solve():
    input = sys.stdin.readline
    ab = ["a", "b", "c", "d", "e", "f", "g", "h", "i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
    abn = dict()
    for i, st in enumerate(ab): abn[st] = i
    N = int(input())
    S = list(input().strip("\n"))
    SegTree = RMQ(N, 0)
    for i, s in enumerate(S):
        ns = 1 << abn[s]
        SegTree.update(i, ns)
    Q = int(input())
    for _ in range(Q):
        t, l, r = input().strip("\n").split()
        if t == "1": SegTree.update(int(l) - 1, 1 << abn[r])
        elif t == "2": 
            bitans = SegTree.search(int(l) - 1, int(r), 0, SegTree.size, 0)
            ans = 0
            while bitans > 0:
                if bitans & 1 == 1: ans += 1
                bitans >>= 1
            print(ans)
    return 0

if __name__ =="__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(str(input()))
q = int(input())

w = []

for i in range(q):
    x,y,z = map(str,input().split())
    y = int(y)

    if x == "1":
        s[y-1] = z

    else:
        z = int(z)
        tmp = s[y-1:z]
        w.append(len(set(tmp)))

for i in w:
    print(i)

Submission status: Time Limit Exceeded

Solution code:

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

#####segfunc######
def segfunc(x,y):
    return x.union(y)

def init(init_val, seg):
    #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, seg):
    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, seg):
    if q<=p:
        return set()
    p += num-1
    q += num-2
    res=set()
    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

n = n_in()
S = s_in()
Q = n_in()


ide_ele = 0

alphabets = 'abcdefghijklmnopqrstuvwxyz'

# T = {}

# n = 500000
# S = 'a'*nA

num = 2**(n-1).bit_length()
seg = [set() for _ in range(2*num)]
init([set([s]) for s in S] , seg)

for _ in range(Q):
    n, i, j = input().split()
    if int(n) == 1:
        update(int(i)-1, set([j]), seg)
    else:
        print(len(query(int(i)-1, int(j), seg)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = list(input())
# N: 処理する区間の長さ
N0 = 2**(N-1).bit_length()
id_ele = set()
data = [id_ele]*(2*N0)
# a_k の値を x に更新
def segfunc(x,y):
    return x|y

def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = segfunc(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = id_ele
    while L < R:
        if R & 1:
            R -= 1
            s = segfunc(s, data[R-1])

        if L & 1:
            s = segfunc(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(N):
  update(i,set(s[i]))
q = int(input())
for _ in range(q):
  p,a,b = input().split()
  if p == "1":
    update(int(a)-1,set(b))
  if p == "2":
    print(len(query(int(a)-1,int(b))))

Submission status: Time Limit Exceeded

Solution code:
import collections

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

querys = []
for i in range(Q):
    query = list(map(str, input().split()))
    querys.append(query)

for i in range(Q):
    query = querys[i]
    if query[0] == "1":
        qi = int(query[1])
        S = S[:qi-1] + query[2] + S[qi:]
    else:
        rq = int(query[2])
        lq = int(query[1])
        te = S[lq - 1:rq]
        c = collections.Counter(te)
        print(len(c))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
S = list(input())

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1].add(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,x):
    k += num-1
    seg[k] = set([x])
    while k:
        k = (k-1)//2
        seg[k] = seg[k*2+1] | seg[k*2+2]
    
def query(p,q):
    if q<=p:
        return 0
    p += num-1
    q += num-2
    res=set()
    while q-p>1:
        if p&1 == 0:
            res |= seg[p]
        if q&1 == 1:
            res |= seg[q]
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res |= seg[p]
    else:
        res |= (seg[p] | seg[q])
    return len(res)

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

init(S)

Q = int(input())
for _ in range(Q):
    x,y,z = map(str,input().split())
    x = int(x); y = int(y)
    if x == 1:
        update(y-1, z)
    else:
        z = int(z)
        print(query(y-1,z))

Submission status: Time Limit Exceeded

Solution code:
def countChar(s):
  return len(set(s))

n = int(input())
s = input()
q = int(input())

for i in range(q):
  t, l, r = map(str, input().split())
  if t == '2':
    print(countChar(s[int(l)-1:int(r)]))
  elif t == '1':
    s = s[:int(l)-1] + r + s[int(l):]

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

import math


class SegmentTree(object):
    # セグメント木

    def __init__(self, N):
        """サイズNの配列を元にしたセグメント木
        """
        # 単位元
        self.idelem = (0, set())
        # 比較関数

        def f(a, b):
            # a, bはこれまでの個数と、文字セットを保持
            anum, aset = a
            bnum, bset = b
            cset = aset | bset
            cnum = len(cset)
            return (cnum, cset)

        self.func = f

        self.N0 = 1
        while self.N0 < N:
            self.N0 <<= 1
        self.tree = [self.idelem]*(2*self.N0)

    def update(self, k, x):
        """k番目の値をxに更新
        """
        k += self.N0-1
        self.tree[k] = x
        while k > 1:
            k = (k-1)//2
            self.tree[k] = self.func(self.tree[2*k+1], self.tree[2*k+2])

    def query(self, l, r):
        """区間[l, r)の最小値
        """
        l += self.N0-1
        r += self.N0-1
        s = self.idelem
        while l < r:
            if r % 2 == 0:
                r -= 1
                s = self.func(s, self.tree[r])

            if l % 2 == 0:
                s = self.func(s, self.tree[l])
                l += 1
            l //= 2
            r //= 2
        return s

    def __str__(self):
        return str(self.tree[self.N0-1:-1])


def main():
    N = int(input())
    S = input()
    Q = int(input())
    query = [input().split() for i in range(Q)]

    seg = SegmentTree(N)
    for i, c in enumerate(S):
        seg.update(i, (1, {c}))

    for q in query:
        if q[0] == "1":
            seg.update(int(q[1])-1, (1, {q[2]}))
        else:
            ans, _ = seg.query(int(q[1])-1, int(q[2]))
            print(ans)
    pass


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
q = int(input())
for j in range(q):
	q = input().split(" ")
	if q[0] == "1":
		i = int(q[1])
		s = s[:i-1] + q[2] + s[i:]
	elif q[0] == "2":
		l = int(q[1])
		r = int(q[2])
		t = s[l-1:r]
		d = {}
		for i in range(len(t)):
			p = t[i]
			if p not in d:
				d[p] = 1
		print(len(d))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(str(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]=set(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()

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

init(s)
#print(seg)

for i in range(q):
    t, x, y = map(str, input().split())
    if t == '1':
        i = int(x)-1
        c = set(y)
        update(i, c)
    else:
        l = int(x)-1
        r = int(y)-1
        print(len(query(l, r+1)))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
N = int(input())
S = list(input())
Q = int(input())

for i in range(Q):
    m, l, r = map(str,input().split())
    if m == '2':
        print(len(set(S[int(l)-1:int(r)])))
    else:
        S = S[:int(l)-1]+[r]+S[int(l):]

Submission status: Time Limit Exceeded

Solution code:
import string


class BIT:

    def __init__(self, N):
        self.bit = [{c : 0 for c in string.ascii_lowercase} for _ in range(N + 1)]
        self.N = N

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

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

def solve(N, S, Q, query):
    bits = BIT(N)

    for i, c in enumerate(S):
        bits.add(i + 1, 1, c)

    ans = []
    for q, i, cr in query:
        if q == "1":
            i = int(i)
            if S[i-1] != cr:
                bits.add(i, -1, S[i-1])
                bits.add(i, 1, cr)
                S[i-1] = cr
        else:
            l = int(i)
            r = int(cr)
            kinds = 0
            for c in string.ascii_lowercase:
                k = bits.sum(r, c) - bits.sum(l, c)
                if S[l-1] == c:
                    k += 1
                if k > 0:
                    kinds += 1
            ans.append(str(kinds))
    return "\n".join(ans)

if __name__ == "__main__":
    N = int(input())
    S = list(input())
    Q = int(input())

    query = []
    for _ in range(Q):
        query.append(tuple(input().split(" ")))
    print(solve(N, S, Q, query))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
s = input()
q = int(input())
for i in range(q):
    x,y,z = input().split()
    y = int(y)
    if x == '1':
        s = s[:y-1]+z+s[y:]
    else:
        z = int(z)
        print(len(Counter(s[y-1:z])))

Submission status: Time Limit Exceeded

Solution code:
import math

class SegmentTree:
	def update(self, i, x):
		i += self.num_leaves-1
		self.nodes[i] = x
		while i > 0:
			i = (i-1) // 2
			self.nodes[i] = self.monoid(self.nodes[i*2+1],self.nodes[i*2+2])
			
	def query(self,a,b,k=0,l=0,r=None):
		if r is None:
			r = self.num_leaves
		if r <= a or b <= l:
			return None
		if a <= l and r <= b:
			return self.nodes[k]
		else:
			vl = self.query(a,b,k*2+1,l,(l+r)//2)
			vr = self.query(a,b,k*2+2,(l+r)//2,r)
			return self.monoid(vl,vr)
		
	def __init__(self, monoid, values):
		self.monoid = lambda x, y : monoid(x, y) if x is not None and y is not None else x or y
		self.num_leaves = 2**math.ceil(math.log(len(values),2))
		self.nodes = [None for i in range(self.num_leaves*2-1)]
		for i in range(len(values)):
			self.update(i,values[i])

def func(a,b):
    return [a[i] or b[i] for i in range(26)]

n = int(input())
s = input()
q = int(input())
Q = [input().split() for i in range(q)]

values = [[(ord(s[i])-ord('a')) == j for j in range(26)] for i in range(n)]

sgt = SegmentTree(func, values)

for i in range(q):
    a,b,c = Q[i]
    b = int(b)
    if a == "1":
        sgt.update(b-1,[(ord(c)-ord('a')) == j for j in range(26)])
    else:
        c = int(c)
        val = sgt.query(b-1,c)
        print(val.count(True))

Submission status: Time Limit Exceeded

Solution code:
D = [s.split() for s in open(0)]
N = D[0][0]
S = D[1][0]
S = list(S)
Q = D[2][0]
qs =D[3:]

for q in qs:
    if q[0] == "2":
        print(len(set(S[int(q[1]) - 1:int(q[2])])))
    if q[0] == "1":
        S[int(q[1]) - 1] = q[2]

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q = int(input())
for i in range(q):
    n, a, b = input().split()
    if n == '1':
        i = int(a)
        s[i-1] = b
    if n == '2':
        l = int(a)
        r = int(b)
        print(len(set(''.join(s[l-1:r]))))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
s = list(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,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()

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

A = []
for i in range(n):
  A.append(set(s[i]))
init(A)
q = int(input())
for _ in range(q):
  p,a,b = input().split()
  if p == "1":
    update(int(a)-1,set(b))
  if p == "2":
    print(len(query(int(a)-1,int(b))))