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:
class BIT:
    def __init__(self,n):
        self.size = n
        self.tree = [0]*(n+1)

    def add(self,i,x):
        while i <= self.size:
            self.tree[i] += x
            i += i&-i

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

N,Q = map(int,input().split())
C = list(map(int,input().split()))
LR = []
for i in range(Q):
    l,r = map(int,input().split())
    LR.append((l,r,i))
bit = BIT(N)
#color[i] => 色iが最後に登場したインデックス(1-indexed)
color = [0]*(N+1)

ANS = []
LR.sort(key=lambda x: x[1])
cur = 1
for l,r,i in LR:
    while cur <= r:
        c = C[cur-1]
        if color[c] == 0:
            color[c] = cur
            bit.add(cur,1)
        else:
            bit.add(color[c],-1)
            color[c] = cur
            bit.add(cur,1)
        cur += 1
    ANS.append((bit.sum(r)-bit.sum(l-1),i))
ANS.sort(key=lambda x: x[1])
for a,i in ANS:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    def __init__(self,n):
        self.size = n
        self.tree = [0]*(n+1)

    def add(self,i,x):
        while i <= self.size:
            self.tree[i] += x
            i += i&-i

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

N,Q = map(int,input().split())
C = list(map(int,input().split()))
LR = [list(map(int,input().split()))+[i] for i in range(Q)]
bit = BIT(N)
#color[i] => 色iが最後に登場したインデックス(1-indexed)
color = [0]*(N+1)

ANS = []
LR.sort(key=lambda x: x[1])
cur = 1
for l,r,i in LR:
    while cur <= r:
        c = C[cur-1]
        if color[c] == 0:
            color[c] = cur
            bit.add(cur,1)
        else:
            bit.add(color[c],-1)
            color[c] = cur
            bit.add(cur,1)
        cur += 1
    ANS.append((bit.sum(r)-bit.sum(l-1),i))
ANS.sort(key=lambda x: x[1])
for a,i in ANS:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
n, q = map(int, input().split())
c = [0] + list(map(int, input().split()))
ql = [[] for _ in range(n+1)]
qid = [[] for _ in range(n+1)]
for i in range(q):
    l, r = map(int, input().split())
    ql[r].append(l)
    qid[r].append(i)
bit = Bit(n)
a = [0 for _ in range(n+1)]
ans = [0 for _ in range(q)]
for i in range(1, n+1):
    if a[c[i]] > 0:
        bit.add(a[c[i]], -1)
    bit.add(i, 1)
    a[c[i]] = i
    for j in range(len(ql[i])):
        ans[qid[i][j]] = bit.sum(i) - bit.sum(ql[i][j]-1)
print("\n".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
class Counter:
    def __init__(self):
        self.dict = {}

    def add(self,x):
        if x in self.dict: self.dict[x] += 1
        else: self.dict[x] = 1

    def decrement(self,x):
        self.dict[x] -= 1
        if self.dict[x] <= 0:
            del self.dict[x]

    def get_dict(self):
        return self.dict


class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):

        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])

    def update(self, k, x):
        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

    def query(self, l, r):
        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 main():
    N,Q=mi()
    _C=list(mi())

    C = [None] * N
    for i in range(N):
        C[i] = set([_C[i]])

    def segfunc(x,y):
        return x | y


    seg = SegTree(C,segfunc,set())
    memo = {}
    for q in range(Q):
        l,r = mi()
        l -= 1
        pair = (l,r)
        if pair in memo:
            print(memo[pair])
            continue

        union = seg.query(*pair)
        print(len(union))
        memo[pair] = len(union)




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
class Counter:
    def __init__(self):
        self.dict = {}

    def add(self,x):
        if x in self.dict: self.dict[x] += 1
        else: self.dict[x] = 1

    def decrement(self,x):
        self.dict[x] -= 1
        if self.dict[x] <= 0:
            del self.dict[x]

    def get_dict(self):
        return self.dict


class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):

        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])

    def update(self, k, x):
        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

    def query(self, l, r):
        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 main():
    N,Q=mi()
    _C=list(mi())

    C = [None] * N
    for i in range(N):
        C[i] = set([_C[i]])

    def segfunc(x,y):
        return x | y


    seg = SegTree(C,segfunc,set())
    for q in range(Q):
        l,r = mi()
        union = seg.query(l-1,r)
        print(len(union))




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    query = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        query[i] = [r, l, i]
    query.sort()
    
    bit = BIT(n)
    index = 0
    already = [0]*(n+1)
    ans = [0]*q
    for i in range(n):
        bit.add(i+1, 1)
        if already[c[i]]:
            bit.subtract(already[c[i]], 1)
        already[c[i]] = i+1
        while index < q:
            key = query[index]
            if key[0] == i+1:
                ans[key[2]] = bit.get_sum(key[1]-1, key[0])
                index += 1
            else:
                break

    for a in ans:
        print(a)

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    query = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        query[i] = [r, l, i]
    query.sort()
    
    bit = BIT(n)
    index = 0
    already = dict()
    ans = [0]*q
    for i in range(n):
        bit.add(i+1, 1)
        if c[i] in already:
            bit.subtract(already[c[i]], 1)
        already[c[i]] = i+1
        while index < q:
            key = query[index]
            if key[0] == i+1:
                ans[key[2]] = bit.get_sum(key[1]-1, key[0])
                index += 1
            else:
                break

    for a in ans:
        print(a)
        
    
    
    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
N, Q = map(int, input().split())
c = list(map(int, input().split()))
for i in range(Q):
    l, r = list(map(int, stdin.readline().split()))
    count = 0
    c2 = []
    for j in range(l-1,r):
        if not c[j] in c2:
            c2.append(c[j])
    print(len(c2))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
c = list(map(int, input().split()))
for i in range(Q):
    l, r = list(map(int, input().split()))
    count = 0
    c2 = []
    for j in range(l-1,r):
        if not c[j] in c2:
            c2.append(c[j])
    print(len(c2))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
c = list(map(int, input().split()))
for i in range(Q):
    l, r = list(map(int, input().split()))
    print(len(set(c[(l - 1):r])))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
c = list(map(int, input().split()))
l = []
r = []
for i in range(Q):
    nums = list(map(int, input().split()))
    l.append(nums[0])
    r.append(nums[1])

for i in range(Q):
    li = l[i]
    ri = r[i]
    c2 = c[(li - 1):ri]
    print(len(set(c2)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
class Bit:
    # Binary Indexed Tree
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i + 1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, i) の要素の総和を返す
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        # 足し算と引き算にはaddを使うべき
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])

(n, q), c, *d = [[*map(int, o.split())] for o in open(0)]

d = sorted(enumerate(d), key = lambda x: x[1][1])

B = Bit(n)
ans = [-1] * q
last = [-1] * (n + 1)
ind = 0  # [-, ind) まで確認終了
for i, (l, r) in d:
    for j in range(ind, r):
        if last[c[j]] != -1:
            B.add(last[c[j]], -1)
        B.add(j, 1)
        last[c[j]] = j
    ind = r
    ans[i] = B.sum(r) - B.sum(l - 1)
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n,q=map(int,input().split())
c=list(map(int,input().split()))
ab=[[]for i in range(n)]
lr=[[]for i in range(n)]
num=[-1]*n
for i in range(n):
	if num[c[i]-1]!=-1:
		ab[num[c[i]-1]].append(i)
	num[c[i]-1]=i
for i in range(q):
	l,r=map(int,input().split())
	lr[l-1].append((r-1,i))
ans=[-1]*q
BIT=[0]*n
for i in range(n-1,-1,-1):
	for x in ab[i]:
		x+=1
		while x<=n:
			BIT[x-1]+=1
			x=x+(x&-x)
	for x,y in lr[i]:
		X=x
		x+=1
		ret=0
		while x!=0:
			ret+=BIT[x-1]
			x=x-(x&-x)
		ans[y]=X-i+1-ret
for x in ans:
	print(x)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
class BIT():
    def __init__(self, N):
        self._N = N
        self._bit = [0 for _ in range(N+1)]

    @property
    def bit(self):
        return self._bit

    def add(self, a, w):
        """v[a]に値wを加算する"""
        x = a
        while x <= self._N:
            self._bit[x] += w
            x += x&-x

    def sum(self, a):
        """区間和v[1]+...+v[a]を返す"""
        ret = 0
        x = a
        while x > 0:
            ret += self._bit[x]
            x -= x&-x
        return ret


def solve():
    """ 解説実装 """
    N, Q = list(map(int, input().split()))
    Cs = list(map(int, input().split()))

    # (s,t)の位置を保持するst_listを作っていく
    s_set = set()  # sの座標をとにかく保持する
    st_list = []
    dic = {}  # (s,t)を保持する辞書
    for i, c in enumerate(Cs):
        if not c in dic:
            dic[c] = (i+1, None)  # tは決まっていないのでNoneとする
            continue
        if dic[c][1] is None:
            # はじめて(s,t)が作成された
            dic[c] = (dic[c][0], i+1)
        else:
            # 既に(s,t)が作成されている場合
            dic[c] = (dic[c][1], i+1)
        st_list.append(dic[c])
        s_set.add(dic[c][0])

    # (l,r)の位置を保持するlr_listを作っていく
    lr_list = []
    for q in range(Q):
        l, r = list(map(int, input().split()))
        lr_list.append(((l, r), q))
        s_set.add(l)

    s_list = list(s_set)
    s_list.sort()
    st_list.sort()
    lr_list.sort()
    anss = [-1 for _ in range(Q)]

    # 右から左へ平面走査するとき、座標sの時点で座標t以下の(s,t)が何個あるかを、
    # t_ruiskei[座標t] := 座標t以下の(s,t)の個数
    # で表す
    st_i = len(st_list)-1
    lr_i = len(lr_list)-1
    t_ruiseki = BIT(5*10**5)

    for s in s_list[::-1]:  # 右から左へ走査する
        while st_i >= 0 and st_list[st_i][0] == s:  # ダセェな！
            t_ruiseki.add(st_list[st_i][1], 1)
            st_i -= 1

        # クエリを実行する
        while lr_i >= 0 and lr_list[lr_i][0][0] == s:
            lr, query = lr_list[lr_i]
            l, r = lr
            anss[query] = (r-l+1) - t_ruiseki.sum(r)
            lr_i -= 1

    for q in range(Q):
        print(anss[q])


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
n,q=input().split()
n=int(n)
q=int(q)
clist = list(map(int, input().split()))
slist=[]
for i in range(q):
  l,r=input().split()
  l=int(l)
  r=int(r)
  s=set(clist[l-1:r])
  print(len(s))

Submission status: Time Limit Exceeded

Solution code:
n,q=input().split()
n=int(n)
q=int(q)
clist = list(map(int, input().split()))
slist=[]
for i in range(q):
  l,r=input().split()
  l=int(l)
  r=int(r)
  s=set(clist[l-1:r])
  slist.append(len(s))

for i in slist:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
class BIT():
    def __init__(self, N):
        self._N = N
        self._bit = [0 for _ in range(N+1)]

    @property
    def bit(self):
        return self._bit

    def add(self, a, w):
        """v[a]に値wを加算する"""
        x = a
        while x <= self._N:
            self._bit[x] += w
            x += x&-x

    def sum(self, a):
        """区間和v[1]+...+v[a]を返す"""
        ret = 0
        x = a
        while x > 0:
            ret += self._bit[x]
            x -= x&-x
        return ret


def solve():
    """ 解説実装 """
    N, Q = list(map(int, input().split()))
    Cs = list(map(int, input().split()))

    # (s,t)の位置を保持するst_listを作っていく
    st_list = []
    dic = {}  # (s,t)を保持する辞書
    for i, c in enumerate(Cs):
        if not c in dic:
            dic[c] = (i+1, None)  # tは決まっていないのでNoneとする
            continue
        if dic[c][1] is None:
            # はじめて(s,t)が作成された
            dic[c] = (dic[c][0], i+1)
        else:
            # 既に(s,t)が作成されている場合
            dic[c] = (dic[c][1], i+1)
        st_list.append(dic[c])

    # (l,r)の位置を保持するlr_listを作っていく
    lr_list = []
    for q in range(Q):
        l, r = list(map(int, input().split()))
        lr_list.append(((l, r), q))

    st_list.sort()
    lr_list.sort()
    anss = [-1 for _ in range(Q)]

    # 右から左へ平面走査するとき、座標sの時点で座標t以下の(s,t)が何個あるかを、
    # t_ruiskei[座標t] := 座標t以下の(s,t)の個数
    # で表す
    st_i = len(st_list)-1
    lr_i = len(lr_list)-1
    t_ruiseki = BIT(5*10**5)

    for s in range(5*10**5, -1, -1):  # 右から左へ走査する
        while st_i >= 0 and st_list[st_i][0] == s:  # ダセェな！
            t_ruiseki.add(st_list[st_i][1], 1)
            st_i -= 1

        # クエリを実行する
        while lr_i >= 0 and lr_list[lr_i][0][0] == s:
            lr, query = lr_list[lr_i]
            l, r = lr
            anss[query] = (r-l+1) - t_ruiseki.sum(r)
            lr_i -= 1

    for q in range(Q):
        print(anss[q])


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
class BIT():
    def __init__(self, N):
        self._N = N
        self._bit = [0 for _ in range(N+1)]

    @property
    def bit(self):
        return self._bit

    def add(self, a, w):
        """v[a]に値wを加算する"""
        x = a
        while x <= self._N:
            self._bit[x] += w
            x += x&-x

    def sum(self, a):
        """区間和v[1]+...+v[a]を返す"""
        ret = 0
        x = a
        while x > 0:
            ret += self._bit[x]
            x -= x&-x
        return ret


def solve():
    """ 解説実装 """
    from operator import attrgetter
    import numpy as np

    N, Q = list(map(int, input().split()))
    Cs = list(map(int, input().split()))

    # (s,t)の位置を保持するst_listを作っていく
    st_list = []
    dic = {}  # (s,t)を保持する辞書
    for i, c in enumerate(Cs):
        if not c in dic:
            dic[c] = (i+1, None)  # tは決まっていないのでNoneとする
            continue
        if dic[c][1] is None:
            # はじめて(s,t)が作成された
            dic[c] = (dic[c][0], i+1)
        else:
            # 既に(s,t)が作成されている場合
            dic[c] = (dic[c][1], i+1)
        st_list.append(dic[c])

    # (l,r)の位置を保持するlr_listを作っていく
    lr_list = []
    for q in range(Q):
        l, r = list(map(int, input().split()))
        lr_list.append(((l, r), q))

    st_list.sort()
    lr_list.sort()
    anss = [-1 for _ in range(Q)]

    # 右から左へ平面走査するとき、座標sの時点で座標t以下の(s,t)が何個あるかを、
    # t_ruiskei[座標t] := 座標t以下の(s,t)の個数
    # で表す
    st_i = len(st_list)-1
    lr_i = len(lr_list)-1
    t_ruiseki = BIT(5*10**5)

    for s in range(5*10**5, -1, -1):  # 右から左へ走査する
        while st_i >= 0 and st_list[st_i][0] == s:  # ダセェな！
            t_ruiseki.add(st_list[st_i][1], 1)
            st_i -= 1

        # クエリを実行する
        while lr_i >= 0 and lr_list[lr_i][0][0] == s:
            lr, query = lr_list[lr_i]
            l, r = lr
            anss[query] = (r-l+1) - t_ruiseki.sum(r)
            lr_i -= 1

    for q in range(Q):
        print(anss[q])


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    class BIT:
        def __init__(self,n):
            self.tree = [0] * (n+1)
            self.size = n
        
        def add(self,i,x):
            while i <= self.size:
                self.tree[i] += x
                i += i&-i
        
        def get(self,i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i&-i
            return s


    N,Q = map(int,input().split())
    C = list(map(int,input().split()))
    LR = [list(map(int,input().split()))+[i] for i in range(Q)]
    LR.sort(key=lambda x: x[1])
    bit = BIT(N)
    stone = [0]*(N+1)
    cur = 1
    ans = [0]*(Q)
    for l,r,i in LR:
        for j in range(cur,r+1):
            c = C[j-1]
            if stone[c]:
                bit.add(stone[c],-1)
            stone[c] = j
            bit.add(stone[c],1)
        ans[i] = bit.get(r)-bit.get(l-1)
    for a in ans:
        print(a)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    class BIT:
        def __init__(self,n):
            self.tree = [0] * (n+1)
            self.size = n
        
        def add(self,i,x):
            while i <= self.size:
                self.tree[i] += x
                i += i&-i
        
        def get(self,i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i&-i
            return s


    N,Q = map(int,input().split())
    C = list(map(int,input().split()))
    LR = [list(map(int,input().split()))+[i] for i in range(Q)]
    LR.sort(key=lambda x: x[1])
    bit = BIT(N)
    stone = [0]*(N+1)
    cur = 1
    ans = []
    for l,r,i in LR:
        while cur <= r:
            c = C[cur-1]
            if stone[c]:
                bit.add(stone[c],-1)
            stone[c] = cur
            bit.add(stone[c],1)
            cur += 1
        ans.append([bit.get(r)-bit.get(l-1),i])
    ans.sort(key=lambda x: x[1])
    for a,i in ans:
        print(a)
main()

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    def __init__(self,n):
        self.tree = [0] * (n+1)
        self.size = n
    
    def add(self,i,x):
        while i <= self.size:
            self.tree[i] += x
            i += i&-i
    
    def get(self,i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i&-i
        return s


N,Q = map(int,input().split())
C = list(map(int,input().split()))
LR = [list(map(int,input().split()))+[i] for i in range(Q)]
LR.sort(key=lambda x: x[1])
bit = BIT(N)
stone = [0]*(N+1)
cur = 1
ans = []
for l,r,i in LR:
    while cur <= r:
        c = C[cur-1]
        if stone[c]:
            bit.add(stone[c],-1)
        stone[c] = cur
        bit.add(stone[c],1)
        cur += 1
    ans.append([bit.get(r)-bit.get(l-1),i])
ans.sort(key=lambda x: x[1])
for a,i in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
def input(): return sys.stdin.readline().rstrip()
N, Q = map(int, input().split())
C = list(map(int, input().split()))
ans = [0 for i in range(Q)]
que = []
for i in range(Q):
    l, r = map(int, input().split())
    que.append((i, l, r))

Que = que.copy()

Que.sort(key=lambda x: x[-1])
point_data = defaultdict(list)

before_node = [-1 for i in range(N+1)]
for i, v in enumerate(C):
    if point_data[v]:
        before_node[i+1] = point_data[v][-1]
    point_data[v].append(i+1)

# BIT 木


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

    def Sum(self, i):
        s = 0
        while i:
            s += self.data[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)

    def get(self, i, j):
        return self.Sum(j)-self.Sum(i-1)


ftree = BIT(N)
for i in range(Q):
    querie, l, r = Que[i]
    if i == 0:
        for j in range(1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    else:
        for j in range(Que[i-1][-1]+1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    ans[querie] = ftree.get(l, r)
    
for i in range(Q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, Q = map(int, input().split())
C = list(map(int, input().split()))
ans = [0 for i in range(Q)]
que = []
for i in range(Q):
    l, r = map(int, input().split())
    que.append((i, l, r))


que.sort(key=lambda x: x[-1])
point_data = defaultdict(list)

before_node = [-1 for i in range(N+1)]
for i, v in enumerate(C):
    if point_data[v]:
        before_node[i+1] = point_data[v][-1]
    point_data[v].append(i+1)

# BIT 木


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

    def Sum(self, i):
        s = 0
        while i:
            s += self.data[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)

    def get(self, i, j):
        return self.Sum(j)-self.Sum(i-1)


ftree = BIT(N)
for i in range(Q):
    querie, l, r = que[i]
    if i == 0:
        for j in range(1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    else:
        for j in range(que[i-1][-1]+1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    ans[querie] = ftree.get(l, r)
    
for i in range(Q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, Q = map(int, input().split())
C = list(map(int, input().split()))
ans = [0 for i in range(Q)]
que = []
for i in range(Q):
    l, r = map(int, input().split())
    que.append((i, l, r))

Que = que.copy()

Que.sort(key=lambda x: x[-1])
point_data = defaultdict(list)

before_node = [-1 for i in range(N+1)]
for i, v in enumerate(C):
    if point_data[v]:
        before_node[i+1] = point_data[v][-1]
    point_data[v].append(i+1)

# BIT 木


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)

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

    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


ftree = BIT(N)
for i in range(Q):
    querie, l, r = Que[i]
    if i == 0:
        for j in range(1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    else:
        for j in range(Que[i-1][-1]+1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    ans[querie] = ftree.get(l-1, r)
for i in range(Q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
class BinaryIndexedTree(object):
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N + 1)

    def bit_add(self, index, num):
        while (index <= self.N):
            self.bit[index] += num
            index += index & -index
        return

    def bit_sum(self,index):
        result = 0
        while (index > 0):
            result += self.bit[index]
            index -= index & -index
        return result

    def bit_sum_range(self, l, r):
        if (l == r):
            return 1
        else:
            return self.bit_sum(r) - self.bit_sum(l - 1)

def main():
    from sys import stdin
    N, Q = list(map(int, input().split()))
    c = list(map(int, input().split()))
    readline = stdin.readline
    query = [list(map(int, readline().split())) + [i] for i in range(Q)]
    query_result = [0 for i in range(Q)]
    collar_pos = [-1] * (N + 1)
    bit = BinaryIndexedTree(N)

    sorted_query = sorted(query, key=lambda query: query[1])

    index = 1
    for query in sorted_query:
        while (index <= query[1]):
            # update BIT
            if (collar_pos[c[index-1]] != -1):
                bit.bit_add(collar_pos[c[index-1]], -1)
            bit.bit_add(index, 1)
            # update collar_pos
            collar_pos[c[index-1]] = index
            index += 1
        query_result[query[2]] = bit.bit_sum_range(query[0], query[1])

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

if __name__ == '__main__':
    main()