Problem:


Score : 600 points

Problem Statement

We have N colored balls arranged in a row from left to right; the color of the i-th ball from the left is c_i.

You are given Q queries. The i-th query is as follows: how many different colors do the l_i-th through r_i-th balls from the left have?

Constraints

1\leq N,Q \leq 5 \times 10^5

1\leq c_i \leq N

1\leq l_i \leq r_i \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
c_1 c_2 \cdots c_N
l_1 r_1
l_2 r_2
:
l_Q r_Q

Output

Print Q lines. The i-th line should contain the response to the i-th query.

Sample Input 1

4 3
1 2 1 3
1 3
2 4
3 3

Sample Output 1

2
3
1

The 1-st, 2-nd, and 3-rd balls from the left have the colors 1, 2, and 1 - two different colors.

The 2-st, 3-rd, and 4-th balls from the left have the colors 2, 1, and 3 - three different colors.

The 3-rd ball from the left has the color 1 - just one color.

Sample Input 2

10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8

Sample Output 2

1
2
2
1
2
2
6
3
3
3



Sample input:
4 3
1 2 1 3
1 3
2 4
3 3


Sample output:
2
3
1

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class BIT:
    def __init__(self, L):
        self.n = len(L)
        self.bit = [0] * (self.n + 1)

    def update(self, idx, x):
        while idx <= self.n:
            self.bit[idx] += x
            idx += idx & (-idx)

    def query(self, idx):
        res = 0
        while idx > 0:
            res += self.bit[idx]
            idx -= idx & (-idx)
        return res

    def sec_sum(self, left, right):
        return self.query(right) - self.query(left - 1)

    def debug(self):
        print(*[self.sec_sum(i - 1, i) for i in range(1, self.n + 1)])


def resolve():
    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([l, r, i])
    query.sort(key=lambda x: x[1])

    lastAppeared = [0] * (max(C) + 1)
    prev = query[0][1]
    for i in range(prev):
        lastAppeared[C[i]] = i + 1

    bit = BIT(C + [0])
    for num in lastAppeared:
        if num == 0:
            continue
        bit.update(num, 1)

    res = [0] * q
    for L, R, idx in query:
        if R > prev:
            for j in range(prev, R):
                if lastAppeared[C[j]]:
                    num = lastAppeared[C[j]]
                    bit.update(num, -1)
                lastAppeared[C[j]] = j + 1
                num = lastAppeared[C[j]]
                bit.update(num, 1)
            prev = R
        res[idx] = bit.sec_sum(L, R)
    print(*res, sep="\n")


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
clist=list(map(int,input().split()))

lrlist=[]
rllist=[]
for _ in range(Q):
  l,r=map(int,input().split())
  lrlist.append((l-1,r-1))
  rllist.append((r-1,l-1))
rllist.sort()
#print(rllist)

class SegTree:
  #init(init_val, ide_ele): 配列init_valで初期化 O(N)
  def __init__(self, init_val, segfunc, ide_ele):
    #init_val: 配列の初期値
    #segfunc: 区間にしたい操作
    #ide_ele: 単位元
    #n: 要素数
    #num: n以上の最小の2のべき乗
    #tree: セグメント木(1-index)
    n = len(init_val)
    self.segfunc = segfunc
    self.ide_ele = ide_ele
    self.num = 1 << (n - 1).bit_length()
    self.tree = [ide_ele] * 2 * self.num
    # 配列の値を葉にセット
    for i in range(n):
      self.tree[self.num + i] = init_val[i]
    # 構築していく
    for i in range(self.num - 1, 0, -1):
      self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

  #update(k, x): k番目の値をxに更新 O(logN)
  def update(self, k, x):
    #k番目の値をxに更新
    #k: index(0-index)
    #x: update value
    k += self.num
    self.tree[k] = x
    while k > 1:
      self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
      k >>= 1

  #query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
  def query(self, l, r):
    #[l, r)のsegfuncしたものを得る
    #l: index(0-index)
    #r: index(0-index)
    res = self.ide_ele
    l += self.num
    r += self.num
    while l < r:
      if l & 1:
        res = self.segfunc(res, self.tree[l])
        l += 1
      if r & 1:
        res = self.segfunc(res, self.tree[r - 1])
      l >>= 1
      r >>= 1
    return res
  
def segfunc(x,y):
  return x+y #区間和
#ide_ele
ide_ele=0 #区間和
  
dic_rpos={clist[0]:0}
ans_dic={}

seg=SegTree([float("inf")]*N, segfunc, ide_ele)
seg.update(0,1)
r0=0
for r,l in rllist:
  for i in range(r0+1,r+1):
    c=clist[i]
    if c in dic_rpos:
      seg.update(dic_rpos[c],0)
    seg.update(i,1)
    dic_rpos[c]=i
  r0=r
      
  ans=seg.query(l,r+1)
  ans_dic[(l,r)]=ans
  
for l,r in lrlist:
  print(ans_dic[(l,r)])

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
clist=list(map(int,input().split()))

lrlist=[]
rllist=[]
for _ in range(Q):
  l,r=map(int,input().split())
  lrlist.append((l-1,r-1))
  rllist.append((r-1,l-1))
rllist.sort()
#print(rllist)

class SegTree:
  #init(init_val, ide_ele): 配列init_valで初期化 O(N)
  def __init__(self, init_val, segfunc, ide_ele):
    #init_val: 配列の初期値
    #segfunc: 区間にしたい操作
    #ide_ele: 単位元
    #n: 要素数
    #num: n以上の最小の2のべき乗
    #tree: セグメント木(1-index)
    n = len(init_val)
    self.segfunc = segfunc
    self.ide_ele = ide_ele
    self.num = 1 << (n - 1).bit_length()
    self.tree = [ide_ele] * 2 * self.num
    # 配列の値を葉にセット
    for i in range(n):
      self.tree[self.num + i] = init_val[i]
    # 構築していく
    for i in range(self.num - 1, 0, -1):
      self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

  #update(k, x): k番目の値をxに更新 O(logN)
  def update(self, k, x):
    #k番目の値をxに更新
    #k: index(0-index)
    #x: update value
    k += self.num
    self.tree[k] = x
    while k > 1:
      self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
      k >>= 1

  #query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
  def query(self, l, r):
    #[l, r)のsegfuncしたものを得る
    #l: index(0-index)
    #r: index(0-index)
    res = self.ide_ele
    l += self.num
    r += self.num
    while l < r:
      if l & 1:
        res = self.segfunc(res, self.tree[l])
        l += 1
      if r & 1:
        res = self.segfunc(res, self.tree[r - 1])
      l >>= 1
      r >>= 1
    return res
  
def segfunc(x,y):
  return x+y #区間和
#ide_ele
ide_ele=0 #区間和
  
dic_rpos={}
ans_dic={}

seg=SegTree([float("inf")]*N, segfunc, ide_ele)
r0=0
for r,l in rllist:
  for i in range(r0,r+1):
    c=clist[i]
    if c in dic_rpos:
      seg.update(dic_rpos[c],0)
    seg.update(i,1)
    dic_rpos[c]=i
  r0=r
      
  ans=seg.query(l,r+1)
  ans_dic[(l,r)]=ans
  
for l,r in lrlist:
  print(ans_dic[(l,r)])

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
clist=list(map(int,input().split()))

lrlist=[]
rllist=[]
for _ in range(Q):
  l,r=map(int,input().split())
  lrlist.append((l,r))
  rllist.append((r,l))
rllist.sort()
#print(rllist)

#A1～Aiまでの和 O(logN)
def BIT_query(idx):
  res_sum = 0
  while idx > 0:
    res_sum += BIT[idx]
    idx -= idx&(-idx)
  return res_sum
#Ai += x O(logN)
def BIT_update(idx,x):
  while idx <= N:
    BIT[idx] += x
    idx += idx&(-idx)
  return

dic_rpos={clist[0]:1}
ans_dic={}

BIT=[0]*(N+1)
BIT_update(1,1)
r0=1
for r,l in rllist:
  if r0<r:
    for i in range(r0+1,r+1):
      c=clist[i-1]
      if c in dic_rpos:
        BIT_update(dic_rpos[c],-1)
      BIT_update(i,1)
      dic_rpos[c]=i
    r0=r
      
  ans=BIT_query(r)-BIT_query(l-1)
  ans_dic[(l,r)]=ans
  
for l,r in lrlist:
  print(ans_dic[(l,r)])

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
clist=list(map(int,input().split()))

lrlist=[]
rllist=[]
for _ in range(Q):
  l,r=map(int,input().split())
  lrlist.append((l,r))
  rllist.append((r,l))
rllist.sort()
#print(rllist)

#A1～Aiまでの和 O(logN)
def BIT_query(idx):
  res_sum = 0
  while idx > 0:
    res_sum += BIT[idx]
    idx -= idx&(-idx)
  return res_sum
#Ai += x O(logN)
def BIT_update(idx,x):
  while idx <= N:
    BIT[idx] += x
    idx += idx&(-idx)
  return

dic_rpos={clist[0]:1}
ans_dic={}

BIT=[0]*(N+1)
BIT_update(1,1)
r0=1
for r,l in rllist:
  if r0<r:
    for i in range(r0+1,r+1):
      c=clist[i-1]
      if c in dic_rpos:
        BIT_update(dic_rpos[c],-1)
      BIT_update(i,1)
      dic_rpos[c]=i
      
  ans=BIT_query(r)-BIT_query(l-1)
  ans_dic[(l,r)]=ans
  
for l,r in lrlist:
  print(ans_dic[(l,r)])

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        # 引数が1つなら一点の値を取得
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

N, Q = MAP()
A = [a-1 for a in LIST()]

prev = [-1] * N
events = []
bit = BIT(N)
for t, a in enumerate(A):
    s = prev[a]
    if s != -1:
        events.append((t, 0, s))
    prev[a] = t

for i in range(Q):
    l, r = MAP()
    l -= 1; r -= 1
    events.append((r, 1, l, i))

events.sort(key=itemgetter(0, 1))
ans = [0] * Q
for event in events:
    if event[1] == 0:
        t, _, s = event
        bit.add(s, 1)
    else:
        r, _, l, i = event
        total = r - l + 1
        ans[i] = total - bit.get(l, N)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
clist=list(map(int,input().split()))

lrlist=[]
rllist=[]
for _ in range(Q):
  l,r=map(int,input().split())
  lrlist.append((l-1,r-1))
  rllist.append((r-1,l-1))
rllist.sort()
#print(rllist)

class SegTree:
  #init(init_val, ide_ele): 配列init_valで初期化 O(N)
  def __init__(self, init_val, segfunc, ide_ele):
    #init_val: 配列の初期値
    #segfunc: 区間にしたい操作
    #ide_ele: 単位元
    #n: 要素数
    #num: n以上の最小の2のべき乗
    #tree: セグメント木(1-index)
    n = len(init_val)
    self.segfunc = segfunc
    self.ide_ele = ide_ele
    self.num = 1 << (n - 1).bit_length()
    self.tree = [ide_ele] * 2 * self.num
    # 配列の値を葉にセット
    for i in range(n):
      self.tree[self.num + i] = init_val[i]
    # 構築していく
    for i in range(self.num - 1, 0, -1):
      self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

  #update(k, x): k番目の値をxに更新 O(logN)
  def update(self, k, x):
    #k番目の値をxに更新
    #k: index(0-index)
    #x: update value
    k += self.num
    self.tree[k] = x
    while k > 1:
      self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
      k >>= 1

  #query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
  def query(self, l, r):
    #[l, r)のsegfuncしたものを得る
    #l: index(0-index)
    #r: index(0-index)
    res = self.ide_ele
    l += self.num
    r += self.num
    while l < r:
      if l & 1:
        res = self.segfunc(res, self.tree[l])
        l += 1
      if r & 1:
        res = self.segfunc(res, self.tree[r - 1])
      l >>= 1
      r >>= 1
    return res
  
def segfunc(x,y):
  return x+y #区間和
#ide_ele
ide_ele=0 #区間和
  
dic_rpos={}
ans_dic={}

seg=SegTree([float("inf")]*N, segfunc, ide_ele)
r0=0
for r,l in rllist:
  for i in range(r0,r+1):
    c=clist[i]
    if c in dic_rpos:
      seg.update(dic_rpos[c],0)
    seg.update(i,1)
    dic_rpos[c]=i
      
  ans=seg.query(l,r+1)
  ans_dic[(l,r)]=ans
  
for l,r in lrlist:
  print(ans_dic[(l,r)])

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        # 引数が1つなら一点の値を取得
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

N, Q = MAP()
A = [a-1 for a in LIST()]

prev = [-1] * N
events = []
bit = BIT(N)
for t, a in enumerate(A):
    s = prev[a]
    if s != -1:
        events.append((t, 0, s))
    prev[a] = t

for i in range(Q):
    l, r = MAP()
    l -= 1; r -= 1
    events.append((r, 1, l, i))

events.sort(key=itemgetter(1))
events.sort(key=itemgetter(0))
ans = [0] * Q
for event in events:
    if event[1] == 0:
        t, _, s = event
        bit.add(s, 1)
    else:
        r, _, l, i = event
        total = r - l + 1
        ans[i] = total - bit.get(l, N)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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


class Segment_tree():
    def __init__(self, n):
        self.inf = pow(2, 32)
        self.n = n
        self.N = 1
        while self.N < self.n:
            self.N *= 2
        self.size = self.N * 2
        self.size -= 1
        self.N -= 1
        self.segment = [0]*(self.size)
        for i in range(self.N-1, -1, -1):
            self.segment[i] = self.segment[2*i+1]+self.segment[2*i+2]
        
    def undate(self, i, x):
        i += (self.N)
        self.segment[i] = x
        while i > 0:
            i = (i-1)//2
            self.segment[i] = self.segment[2*i+1]+self.segment[2*i+2]
        
    def find(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return self.segment[k]
        else:
            find_l = self.find(a, b, 2*k+1, l, (l+r)//2)
            find_r = self.find(a, b, 2*k+2, (l+r)//2, r)
            return find_l+find_r
    
    def count(self, l, r):
        return self.find(l, r, 0, 0, self.size-self.N)


def main():
    n, q = map(int, input().split())
    c = [int(x) for x in input().split()]
    
    judge = dict()
    key = [-1]*n
    for i in range(n):
        if c[i] in judge:
            key[i] = judge[c[i]]
        judge[c[i]] = i
    
    query = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        query[i] = (r-1, l-1, i)
    
    query.sort()
    
    segment = Segment_tree(n)
    ans = [0]*q
    index = 0
    for i in range(n):
        segment.undate(i, 1)
        if key[i] != -1:
            segment.undate(key[i], 0)
        while True:
            if index == q:
                break
            r, l = query[index][0], query[index][1]
            if r == i:
                ans[query[index][2]] = segment.count(l, r+1)
                index += 1
            else:
                break
        if index == q:
            break
    
    for v in ans:
        print(v)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def input(): return sys.stdin.buffer.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        # 引数が1つなら一点の値を取得
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

N, Q = MAP()
A = [a-1 for a in LIST()]

prev = [-1] * N
events = []
bit = BIT(N)
for t, a in enumerate(A):
    s = prev[a]
    if s != -1:
        events.append((t, 0, s))
    prev[a] = t

for i in range(Q):
    l, r = MAP()
    l -= 1; r -= 1
    events.append((r, 1, l, i))

events.sort()
ans = [0] * Q
for event in events:
    if event[1] == 0:
        t, _, s = event
        bit.add(s, 1)
    else:
        r, _, l, i = event
        total = r - l + 1
        ans[i] = total - bit.get(l, N)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        # 引数が1つなら一点の値を取得
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

N, Q = MAP()
A = [a-1 for a in LIST()]

prev = [-1] * N
events = []
bit = BIT(N)
for t, a in enumerate(A):
    s = prev[a]
    if s != -1:
        events.append((t, 0, s))
    prev[a] = t

for i in range(Q):
    l, r = MAP()
    l -= 1; r -= 1
    events.append((r, 1, l, i))

events.sort()
ans = [0] * Q
for event in events:
    if event[1] == 0:
        t, _, s = event
        bit.add(s, 1)
    else:
        r, _, l, i = event
        total = r - l + 1
        ans[i] = total - bit.get(l, N)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
buf = sys.stdin.buffer
input = buf.readline
class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    def add(self, i, x):
        n, tree = self.n, self.tree
        while i <= n:
            tree[i] += x
            i += i & -i
    def sum(self, i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
def main():
    n, q = map(int, input().split())
    res = [0] * q
    *c, = map(int, input().split())
    q = [(r, l, i) for i, (l, r) in enumerate(zip(*[map(int, buf.read().split())] * 2))]
    q.sort()
    bit = BIT(n + 2)
    add, sum = bit.add, bit.sum
    b = [1] * (n + 1)
    j = 1
    for r, l, i in q:
        while j <= r:
            d = c[j - 1]
            j += 1
            k = b[d]
            b[d] = j
            add(k + 1, 1)
            add(j + 1, -1)
        res[i] = sum(l + 1)
    print(' '.join(map(str, res)))
main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        # 引数が1つなら一点の値を取得
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

N, Q = MAP()
A = [a-1 for a in LIST()]

prev = [-1] * N
events = []
bit = BIT(N)
for t, a in enumerate(A):
    s = prev[a]
    if s != -1:
        events.append((t, 0, s))
    prev[a] = t

for i in range(Q):
    l, r = MAP()
    l -= 1; r -= 1
    events.append((r, 1, l, i))

events.sort()
ans = [0] * Q
for event in events:
    if event[1] == 0:
        t, _, s = event
        bit.add(s, 1)
    else:
        r, _, l, i = event
        total = r - l + 1
        ans[i] = total - bit.get(l, N)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        # 引数が1つなら一点の値を取得
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

    def print(self, N):
        for i in range(N):
            print(self.get(i), end=' ')
        print()

N, Q = MAP()
A = [a-1 for a in LIST()]

prev = [-1] * N
events = []
bit = BIT(N)
for t, a in enumerate(A):
    s = prev[a]
    if s != -1:
        events.append((t, 0, s))
    prev[a] = t

for i in range(Q):
    l, r = MAP()
    l -= 1; r -= 1
    events.append((r, 1, l, i))

events.sort()
ans = [0] * Q
for event in events:
    if event[1] == 0:
        t, _, s = event
        bit.add(s, 1)
    else:
        r, _, l, i = event
        total = r - l + 1
        ans[i] = total - bit.get(l, N)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
def main():
  def add(i,x):
    i+=1
    while i<=n:
      bit[i-1]+=x
      i+=i&-i
  def sum_sub(i):
    a=0
    i+=1
    while i:
      a+=bit[i-1]
      i-=i&-i
    return a
  def sum(i,j):
    a=sum_sub(j+1)
    if i!=0:a-=sum_sub(i-1)
    return a
  n,q,*x=map(int,open(0).read().split())
  a=x[:n]
  queries=[]
  for i in range(q):
    l,r=x[n+i*2:n+(i+1)*2]
    queries.append([r-1,l-1,i])
  ans=[0]*q
  queries.sort()
  queries.append([10*20,0,0])
  lastAppeared=[-1]*n
  bit=[0]*n
  j=0
  for i in range(n):
    if lastAppeared[a[i]-1]!=-1:
      add(lastAppeared[a[i]-1],-1)
      add(i,1)
      lastAppeared[a[i]-1]=i
    else:
      add(i,1)
      lastAppeared[a[i]-1]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=sum(l,r-1)
  print(*ans)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

def main():
    n, q = map(int, input().split())
    c = [int(x) for x in input().split()]
    
    key = [-1]*n
    judge = dict()
    for i in range(n):
        if c[i] in judge:
            key[i] = judge[c[i]]
        judge[c[i]] = i
    
    query = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        query[i] = (r, l, i)
    
    query.sort()
    
    ans = [None]*q
    index = 0
    judge = []
    for i in range(n):
        if index == q:
            break
        if key[i] != -1:
            bisect.insort(judge, key[i])

        while True:
            if index == q:
                break
            r, l = query[index][0], query[index][1]
            if r == i+1:
                ans[query[index][2]] = r-l+1-len(judge)+bisect.bisect_left(judge, l-1)
                index += 1
            else:
                break
    for v in ans:
        print(v)
        
    
    
    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,q,*x=map(int,open(0).read().split())
a=x[:n]
queries=[]
for i in range(q):
  l,r=x[n+i*2:n+(i+1)*2]
  queries.append([r-1,l-1,i])
ans=[0]*q
queries.sort()
queries.append([10*20,0,0])
lastAppeared=[-1]*n
bit=[0]*n
def add(i,x):
  i+=1
  while i<=n:
    bit[i-1]+=x
    i+=i&-i
def sum_sub(i):
  a=0
  i+=1
  while i:
    a+=bit[i-1]
    i-=i&-i
  return a
def sum(i,j):
  a=sum_sub(j+1)
  if i!=0:a-=sum_sub(i-1)
  return a
j=0
for i in range(n):
  if lastAppeared[a[i]-1]!=-1:
    add(lastAppeared[a[i]-1],-1)
    add(i,1)
    lastAppeared[a[i]-1]=i
  else:
    add(i,1)
    lastAppeared[a[i]-1]=i
  while queries[j][0]==i:
    r,l,ind=queries[j]
    j+=1
    ans[ind]=sum(l,r-1)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
buf = sys.stdin.buffer
input = buf.readline
def main():
    def add(i, x):
        while i <= size:
            tree[i] += x
            i += i & -i
    def sum(i):
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
    n, q = map(int, input().split())
    res = [0] * q
    *c, = map(int, input().split())
    q = [(i, l, r) for i, (l, r) in enumerate(zip(*[map(int, buf.read().split())] * 2))]
    q.sort(key=itemgetter(2))
    size = n + 2
    tree = [0] * (size + 1)
    b = [1] * (n + 1)
    j = 1
    for i, l, r in q:
        while j <= r:
            d = c[j - 1]
            j += 1
            k = b[d]
            b[d] = j
            add(k + 1, 1)
            add(j + 1, -1)
        res[i] = sum(l + 1)
    print(' '.join(map(str, res)))
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def position_zip(a,flag):
  j=0
  d={}
  for i in sorted(a):
    if i in d:continue
    d[i]=j
    j+=1
  if flag==1:return d
  return [d[i] for i in a]
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j+1)
    if i!=0:a-=self.sum_sub(i-1)
    return a
n,q,*x=map(int,open(0).read().split())
a=x[:n]
queries=[]
for i in range(q):
  l,r=x[n+i*2:n+(i+1)*2]
  queries.append([r-1,l-1,i])
ans=[0]*q
queries.sort()
queries.append([10*20,0,0])
lastAppeared=[-1]*n
bitt=BinaryIndexedTree(n)
j=0
for i in range(n):
  if lastAppeared[a[i]-1]!=-1:
    bitt.add(lastAppeared[a[i]-1],-1)
    bitt.add(i,1)
    lastAppeared[a[i]-1]=i
  else:
    bitt.add(i,1)
    lastAppeared[a[i]-1]=i
  while queries[j][0]==i:
    r,l,ind=queries[j]
    j+=1
    ans[ind]=bitt.sum(l,r-1)
print(*ans)