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:
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.union(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] = set([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: Time Limit Exceeded

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]==set([b]):
        return ()
    seg[k] = set([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: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, a, identity=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, x):
        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':
    qs = query.split()
    i = int(qs[1])
    j = ord(qs[2]) - a
    for k, st in enumerate(st_list):
      st.update(i-1, j == k)
  else:
    _, l, r = map(int, query.split())
    ans = [st.query(l-1, r-1) for st in st_list]
    print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
s=list(input())
t=np.zeros((26,n+1))
for i in range(n):
    t[ord(s[i])-97][i+1]+=1
t=np.cumsum(t,axis=1)
for i in range(int(input())):
    a,b,c=map(str,input().split())
    if a=="1":
        if s[int(b)-1]!=c:
            t[ord(s[int(b)-1])-97][int(b):]-=1
            t[ord(c)-97][int(b):]+=1
            s[int(b)-1]=c
    else:
        d=0
        b,c=int(b),int(c)
        for j in range(26):
            if t[j][c]!=t[j][b-1]:
                d+=1
        print(d)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N=int(input())
S=list(input())
Q=int(input())
D="abcdefghijklmnopqrstuvwxyz"
def lower_bound(K,s):
  l=0
  r=len(K)-1
  while l<=r:
    mid = (l+r)//2
    if K[mid]==s:
      return True
    elif K[mid]<s:
      l=mid+1
    else:
      r=mid-1
      
  return False
for i in range(Q):
  a,b,c=map(str,input().split())
  a=int(a);b=int(b)-1
  if a==1:
    S[b]=c
  else:
    c=int(c)-1
    print(len(set(S[b:c+1])))

Submission status: Time Limit Exceeded

Solution code:
import bisect
N=int(input())
S=list(input())
Q=int(input())
D="abcdefghijklmnopqrstuvwxyz"
def lower_bound(K,s):
  l=0
  r=len(K)-1
  while l<=r:
    mid = (l+r)//2
    if K[mid]==s:
      return True
    elif K[mid]<s:
      l=mid+1
    else:
      r=mid-1
      
  return False
for i in range(Q):
  a,b,c=map(str,input().split())
  a=int(a);b=int(b)-1
  if a==1:
    S[b]=c
  else:
    c=int(c)-1
    ans=0
    K=sorted(S[b:c+1])
    for j in D:
      if K[0]>j:
        pass
      elif K[-1]<j:
        break
      elif lower_bound(K,j):
        ans+=1
    print(ans)

Submission status: Time Limit Exceeded

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(n*2)]
  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: Time Limit Exceeded

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]


def main():
    N = int(input())
    S = 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, c)
        else:
            l, r = int(i) - 1, int(c)
            print(tree.query(l, r))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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]


def main():
    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))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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)
  def update(i,x):
    i+=n
    data[i]=0
    data[i,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: Time Limit Exceeded

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)
  def update(i,x):
    i+=n
    data[i]=zeros(26,int)
    data[i,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: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
q = int(input())
for i in range(q):
    c, a, b = map(str, input().split())
    if c == "2":
        # print(s[int(a):int(b)+1])
        print(len(set(s[int(a)-1:int(b)])))
    if c == "1":
        grab = [str(i) for i in s]
        # print(grab)
        grab[int(a)-1] = b
        s = "".join(grab)
        continue

Submission status: Time Limit Exceeded

Solution code:
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]


def main():
    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))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input=sys.stdin.buffer.readline
  n=int(input())+1
  data=[[0]*n*2for _ in range(26)]
  def update(i,x):
    i+=n
    for d in data:
      j=i
      if d[j]:
        d[j]=0
        j//=2
        while j:
          d[j]=d[j+j]|d[j-~j]
          j//=2
        break
    d=data[x]
    d[i]=1
    i//=2
    while i:
      d[i]=d[i+i]|d[i-~i]
      i//=2
  def query(l,r):
    l+=n
    r+=n
    s=[0]*26
    while l<r:
      if l&1:
        for i,d in enumerate(data):
          s[i]|=d[l]
        l+=1
      if r&1:
        r-=1
        for i,d in enumerate(data):
          s[i]|=d[r]
      l//=2
      r//=2
    return sum(s)
  for i,c in enumerate(input()[:-1],n):
    data[c-97][i]=1
  for d in data:
    for i in range(n-1,0,-1):
      d[i]=d[i+i]|d[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(' '.join(map(str,s)))
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input=sys.stdin.buffer.readline
  n=int(input())+1
  data=[[0]*n*2for _ in range(26)]
  def update(i,x):
    i+=n
    for d in data:
      j=i
      if d[j]:
        d[j]=0
        j//=2
        while j:
          d[j]=d[j+j]|d[j-~j]
          j//=2
        break
    d=data[x]
    d[i]=1
    i//=2
    while i:
      d[i]=d[i+i]|d[i-~i]
      i//=2
  def query(l,r):
    l+=n
    r+=n
    s=[0]*26
    while l<r:
      if l&1:
        for i,d in enumerate(data):
          s[i]|=d[l]
        l+=1
      if r&1:
        r-=1
        for i,d in enumerate(data):
          s[i]|=d[r]
      l//=2
      r//=2
    return sum(s)
  for i,c in enumerate(input()[:-1]):
    update(i,c-97)
  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: Time Limit Exceeded

Solution code:
class SegmentTree():
    def __init__(self, S):
        # S:英小文字からなる配列
        # tmp = len(S)
        # cnt = 0
        # while tmp // 2 > 0:
        #     tmp //= 2
        #     cnt += 1
        self.size = 19
        # sizeはSの長さ<=2**nをみたす最小のn
        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]


def main():
    N = int(input())
    S = 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, c)
        else:
            l, r = int(i) - 1, int(c)
            print(tree.query(l, r))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree():
    def __init__(self, S):
        # S:英小文字からなる配列
        # tmp = len(S)
        # cnt = 0
        # while tmp // 2 > 0:
        #     tmp //= 2
        #     cnt += 1
        self.size = 19
        # sizeはSの長さ<=2**nをみたす最小のn
        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 = 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, c)
    else:
        l, r = int(i) - 1, int(c)
        print(tree.query(l, r))
# S = ['a', 'b', 'c', 'd', 'b', 'b', 'd']
# tree = SegmentTree(S)
# print(tree.query(2, 6))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree():
    def __init__(self, S):
        # S:英小文字からなる配列
        # tmp = len(S)
        # cnt = 0
        # while tmp // 2 > 0:
        #     tmp //= 2
        #     cnt += 1
        self.size = 20
        # sizeはSの長さ<=2**nをみたす最小のn
        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 = 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, c)
    else:
        l, r = int(i) - 1, int(c)
        print(tree.query(l, r))
# S = ['a', 'b', 'c', 'd', 'b', 'b', 'd']
# tree = SegmentTree(S)
# print(tree.query(2, 6))

Submission status: Time Limit Exceeded

Solution code:
def type1(s, i, c):
  s[int(i) - 1] = c
  return s

def type2(S, l, r):
  rl = []

  for v in S[int(l) - 1:int(r)]:
    if not v in rl:
      rl.append(v)
  
  print(len(rl))
  return s

def run_query(s, query):
  query_funcs = [type1, type2]
  (t, x, y) = query.split(" ")
  return query_funcs[int(t) -1](s, x, y)

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

s = list(S)
for q in range(int(Q)):
  s = run_query(s, input())

Submission status: Time Limit Exceeded

Solution code:
def type1(s, i, c):
  s[int(i) - 1] = c
  return s

def type2(S, l, r):
  rl = []

  for v in S[int(l) - 1:int(r)]:
    if not v in rl:
      rl.append(v)
  
  print(len(rl))
  return s

def run_query(s, query):
  query_funcs = [type1, type2]
  (t, x, y) = query.split(" ")
  return query_funcs[int(t) -1](s, x, y)

N = input()
S = input()
Q = input()
ql = [input() for i in range(int(Q))]

s = list(S)
for q in ql:
  s = run_query(s, q)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree():
    def __init__(self, S):
        # S:英小文字からなる配列
        tmp = len(S)
        cnt = 0
        while tmp // 2 > 0:
            tmp //= 2
            cnt += 1
        self.size = cnt + 1
        # sizeはSの長さ<=2**nをみたす最小のn
        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 = 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, c)
    else:
        l, r = int(i) - 1, int(c)
        print(tree.query(l, r))

Submission status: Time Limit Exceeded

Solution code:
def type1(S, i, c):
  sl = list(S)
  sl[int(i) - 1] = c
  return "".join(sl)

def type2(S, l, r):
  rl = []

  for v in S[int(l) - 1:int(r)]:
    if not v in rl:
      rl.append(v)
  
  print(len(rl))
  return S

def run_query(S, query):
  query_funcs = [type1, type2]
  (t, x, y) = query.split(" ")
  return query_funcs[int(t) -1](S, x, y)

N = input()
S = input()
Q = input()
ql = [input() for i in range(int(Q))]

s = S
for q in ql:
  s = run_query(s, q)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input=sys.stdin.buffer.readline
  n=int(input())+1
  data=[0]*n*2
  def update(i,x):
    i+=n
    data[i]=x
    i//=2
    while i:
      data[i]=data[i*2]|data[i*2+1]
      i//=2
  def query(l,r):
    l+=n
    r+=n
    s=0
    while l<r:
      if l&1:
        s|=data[l]
        l+=1
      if r&1:
        r-=1
        s|=data[r]
      l//=2
      r//=2
    return sum(1for i in range(26)if s&2**i)
  for i,c in enumerate(input()[:-1]):update(i,2**(c-97))
  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,2**(b[0]-97))
  print(*s)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.buffer.readline
n=int(input())+1
data=[0]*n*2
def update(i,x):
  i+=n
  data[i]=x
  i//=2
  while i:
    data[i]=data[i*2]|data[i*2+1]
    i//=2
def query(l,r):
  l+=n
  r+=n
  s=0
  while l<r:
    if l&1:
      s|=data[l]
      l+=1
    if r&1:
      r-=1
      s|=data[r]
    l//=2
    r//=2
  return bin(s).count('1')
for i,c in enumerate(input()[:-1]):update(i,2**(c-97))
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,2**(b[0]-97))
print(*s)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input=sys.stdin.buffer.readline
  n=int(input())+1
  data=[0]*2*n 
  for i,c in enumerate(input()[:-1],n):
    data[i]=2**(c-97)
    i//=2
    while i:
      data[i]=data[i*2]|data[i*2+1]
      i//=2
  for _ in range(int(input())):
    q,a,b=input().split()
    if q[0]>49:
      l,r=int(a)+n-1,int(b)+n
      s=0
      while l<r:
        if l&1:
          s|=data[l]
          l+=1
        if r&1:
          r-=1
          s|=data[r]
        l//=2
        r//=2
      print(sum(1for i in range(26)if s&2**i))
    else:
      i=int(a)+n-1
      data[i]=2**(b[0]-97)
      i//=2
      while i:
        data[i]=data[i*2]|data[i*2+1]
        i//=2
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input=sys.stdin.buffer.readline
  n=int(input())+1
  data=[0]*2*n 
  for i,c in enumerate(input()[:-1],n):
    data[i]=2**(c-97)
    i//=2
    while i:
      data[i]=data[i*2]|data[i*2+1]
      i//=2
  for _ in range(int(input())):
    q,a,b=input().split()
    if q[0]>49:
      l,r=int(a)+n-1,int(b)+n
      s=0
      while l<r:
        if l&1:
          s|=data[l]
          l+=1
        if r&1:
          r-=1
          s|=data[r]
        l//=2
        r//=2
      print(bin(s).count('1'))
    else:
      i=int(a)+n-1
      data[i]=2**(b[0]-97)
      i//=2
      while i:
        data[i]=data[i*2]|data[i*2+1]
        i//=2
main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input=sys.stdin.buffer.readline
  n=int(input())+1
  data=[set()for _ in range(2*n)]
  def update(i,x):
    i+=n
    data[i]={x}
    i//=2
    while i:
      data[i]=data[i*2]|data[i*2+1]
      i//=2
  def query(l,r):
    l+=n
    r+=n
    s=set()
    while l<r:
      if l&1:
        s|=data[l]
        l+=1
      if r&1:
        r-=1
        s|=data[r]
      l//=2
      r//=2
    return len(s)
  for i,c in enumerate(input()[:-1]):update(i,c)
  for _ in range(int(input())):
    q,a,b=input().split()
    if q[0]>49:print(query(int(a)-1,int(b)))
    else:update(int(a)-1,b[0])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input=sys.stdin.buffer.readline
  n=int(input())+1
  data=[set()for _ in range(2*n)]
  def update(i,x):
    i+=n
    data[i]={x}
    i//=2
    while i:
      data[i]=data[i*2]|data[i*2+1]
      i//=2
  def query(l,r):
    l+=n
    r+=n
    s=set()
    while l<r:
      if l&1:
        s|=data[l]
        l+=1
      if r&1:
        r-=1
        s|=data[r]
      l//=2
      r//=2
    return len(s)
  for i,c in enumerate(input()[:-1]):
    update(i,c)
  for _ in range(int(input())):
    q,a,b=input().split()
    if q[0]>49:print(query(int(a)-1,int(b)))
    else:update(int(a)-1,b[0])
main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N = int(input())
S = input().strip()
Q = int(input())
n = 1
while n < N:
    n *= 2
T = [set()] * (2 * n)

def update(k, a):
    k += n-1
    T[k] = {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):
    # print(a, b, k, l, r)
    if r <= a or b <= l:
        # print('  ', set())
        return set()
    if a <= l and r <= b:
        # print('  ', T[k])
        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):
    update(i, S[i])

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