Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
C = list(map(int, input().split()))
query = []

for i in range(Q):
  l, r = map(int, input().split())
  query.append((i, l, r))

query.sort(key = lambda x: x[2])

class BIT:
  from operator import add, sub
  X_unit = 0
  X_f = add
  X_f_rev = sub

  def __init__(self, seq):
    N = len(seq)
    self.N = N
    self.X = seq[:]
    for i in range(self.N):
      j = i + ((i+1) & -(i+1))
      if j < self.N:
        self.X[j] = self.X_f(self.X[i], self.X[j])
  
  def set_val(self, i, x):
    while(i < self.N):
      self.X[i] = self.X_f(self.X[i], x)
      i += (i+1) & -(i+1)

  def cum_val(self, i):
    res = self.X_unit
    while(i > -1):
      res = self.X_f(res, self.X[i])
      i -= (i+1) & -(i+1)
    return res
  
  #区間[L, R)
  def fold(self, L, R):
    return self.X_f_rev(self.cum_val(R-1), self.cum_val(L-1))


GJ = [-1]*N
bit = BIT([0]*N)
ans = [0]*Q
st = 0

for i in range(N):
  if GJ[C[i]-1] != -1:
    bit.set_val(GJ[C[i]-1], -1)
  GJ[C[i]-1] = i
  bit.set_val(i, 1)
  while query[st][2] == i+1 and st < Q:
    ans[query[st][0]] = bit.fold(query[st][1]-1, query[st][2])
    st += 1
    if st == Q:
      break

print(*ans, sep="\n")

Fixed submission:
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
C = list(map(int, input().split()))
query = []

for i in range(Q):
  l, r = map(int, input().split())
  query.append((i, l, r))

query.sort(key = lambda x: x[2])

class BIT:
  from operator import add, sub
  X_unit = 0
  X_f = add
  X_f_rev = sub

  def __init__(self, seq):
    N = len(seq)
    self.N = N
    self.X = seq[:]
    for i in range(self.N):
      j = i + ((i+1) & -(i+1))
      if j < self.N:
        self.X[j] = self.X_f(self.X[i], self.X[j])
  
  def set_val(self, i, x):
    while(i < self.N):
      self.X[i] = self.X_f(self.X[i], x)
      i += (i+1) & -(i+1)

  def cum_val(self, i):
    res = self.X_unit
    while(i > -1):
      res = self.X_f(res, self.X[i])
      i -= (i+1) & -(i+1)
    return res

  def fold(self, L, R):
    return self.X_f_rev(self.cum_val(R-1), self.cum_val(L-1))

GJ = [-1]*N
bit = BIT([0]*N)
ans = [0]*Q
st = 0

for i in range(N):
  if GJ[C[i]-1] != -1:
    bit.set_val(GJ[C[i]-1], -1)
  GJ[C[i]-1] = i
  bit.set_val(i, 1)
  if st < Q:
    while query[st][2] == i+1:
      ans[query[st][0]] = bit.fold(query[st][1]-1, query[st][2])
      st += 1
      if st == Q:
        break

print(*ans, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
C = list(map(int, input().split()))
query = []

for i in range(Q):
  l, r = map(int, input().split())
  query.append((i, l, r))

query.sort(key = lambda x: x[2])

class BIT:
  from operator import add, sub, mul, floordiv
  X_unit = 0
  X_f = add
  X_f_rev = sub

  def __init__(self, seq):
    N = len(seq)
    self.N = N
    self.X = seq[:]
    for i in range(self.N):
      j = i + ((i+1) & -(i+1))
      if j < self.N:
        self.X[j] = self.X_f(self.X[i], self.X[j])
  
  def set_val(self, i, x):
    while(i < self.N):
      self.X[i] = self.X_f(self.X[i], x)
      i += (i+1) & -(i+1)

  def cum_val(self, i):
    res = self.X_unit
    while(i > -1):
      res = self.X_f(res, self.X[i])
      i -= (i+1) & -(i+1)
    return res
  
  #区間[L, R)
  def fold(self, L, R):
    return self.X_f_rev(self.cum_val(R-1), self.cum_val(L-1))


GJ = [-1]*N
bit = BIT([0]*N)
ans = [0]*Q
st = 0

for i in range(N):
  if GJ[C[i]-1] != -1:
    bit.set_val(GJ[C[i]-1], -1)
  GJ[C[i]-1] = i
  bit.set_val(i, 1)
  if st < Q:
    while query[st][2] == i+1:
      ans[query[st][0]] = bit.fold(query[st][1]-1, query[st][2])
      st += 1
      if st == Q:
        break

for i in ans:
  print(i)

Fixed submission:
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
C = list(map(int, input().split()))
query = []

for i in range(Q):
  l, r = map(int, input().split())
  query.append((i, l, r))

query.sort(key = lambda x: x[2])

class BIT:
  from operator import add, sub
  X_unit = 0
  X_f = add
  X_f_rev = sub

  def __init__(self, seq):
    N = len(seq)
    self.N = N
    self.X = seq[:]
    for i in range(self.N):
      j = i + ((i+1) & -(i+1))
      if j < self.N:
        self.X[j] = self.X_f(self.X[i], self.X[j])
  
  def set_val(self, i, x):
    while(i < self.N):
      self.X[i] = self.X_f(self.X[i], x)
      i += (i+1) & -(i+1)

  def cum_val(self, i):
    res = self.X_unit
    while(i > -1):
      res = self.X_f(res, self.X[i])
      i -= (i+1) & -(i+1)
    return res

  def fold(self, L, R):
    return self.X_f_rev(self.cum_val(R-1), self.cum_val(L-1))

GJ = [-1]*N
bit = BIT([0]*N)
ans = [0]*Q
st = 0

for i in range(N):
  if GJ[C[i]-1] != -1:
    bit.set_val(GJ[C[i]-1], -1)
  GJ[C[i]-1] = i
  bit.set_val(i, 1)
  if st < Q:
    while query[st][2] == i+1:
      ans[query[st][0]] = bit.fold(query[st][1]-1, query[st][2])
      st += 1
      if st == Q:
        break

print(*ans, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
C = list(map(int, input().split()))

class SegTree:
    X_unit = set()

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = {x}
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X[i << 1] | self.X[i << 1 | 1]

    #区間積[L, R)
    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = vL | self.X[L]
                L += 1
            if R & 1:
                R -= 1
                vR = self.X[R] | vR
            L >>= 1
            R >>= 1
        return len(vL | vR)

seg = SegTree(N)
seg.build(C)

for q in range(Q):
  l, r = map(int, input().split())
  print(seg.fold(l-1, r))

Fixed submission:
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
C = list(map(int, input().split()))
query = []

for i in range(Q):
  l, r = map(int, input().split())
  query.append((i, l, r))

query.sort(key = lambda x: x[2])

class BIT:
  from operator import add, sub
  X_unit = 0
  X_f = add
  X_f_rev = sub

  def __init__(self, seq):
    N = len(seq)
    self.N = N
    self.X = seq[:]
    for i in range(self.N):
      j = i + ((i+1) & -(i+1))
      if j < self.N:
        self.X[j] = self.X_f(self.X[i], self.X[j])
  
  def set_val(self, i, x):
    while(i < self.N):
      self.X[i] = self.X_f(self.X[i], x)
      i += (i+1) & -(i+1)

  def cum_val(self, i):
    res = self.X_unit
    while(i > -1):
      res = self.X_f(res, self.X[i])
      i -= (i+1) & -(i+1)
    return res

  def fold(self, L, R):
    return self.X_f_rev(self.cum_val(R-1), self.cum_val(L-1))

GJ = [-1]*N
bit = BIT([0]*N)
ans = [0]*Q
st = 0

for i in range(N):
  if GJ[C[i]-1] != -1:
    bit.set_val(GJ[C[i]-1], -1)
  GJ[C[i]-1] = i
  bit.set_val(i, 1)
  if st < Q:
    while query[st][2] == i+1:
      ans[query[st][0]] = bit.fold(query[st][1]-1, query[st][2])
      st += 1
      if st == Q:
        break

print(*ans, sep="\n")