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:


# point update
# range query
class SegmentTreeNode:
	def __init__(self, start, end, initial, merge):
#		print("s", start, end)
		self.start = start
		self.end = end
		self.width = end - start
		self.merge = merge
		self.initial = initial
		if self.width > 1:
			w2 = self.width // 2
			self.left = SegmentTreeNode(start, start + w2, initial, merge)
			self.right = SegmentTreeNode(start + w2, end, initial, merge)
			self.value = self.merge(self.left.value, self.right.value)
		else:
			self.value = self.initial

	def update(self, index, value):
		if self.start <= index and index < self.end:
			if self.width == 1:
				self.value = value
			else:
				self.left.update(index, value)
				self.right.update(index, value)
				self.value = self.merge(self.left.value, self.right.value)
	
	def pick(self, start, end):
		if start <= self.start and self.end <= end:
			return self.value
		elif self.start < end and self.end > start:
#			m = self.merge(self.left.pick(start, end), self.right.pick(start, end))
#			print(start, end, m)
			return self.merge(self.left.pick(start, end), self.right.pick(start, end))
		else:
			return self.initial
	
	def to_list(self, items):
		if self.width == 1:
			items.append(self.value)
		else:
			self.left.to_list(items)
			self.right.to_list(items)
	
class SegmentTree:
	def __init__(self, n, *, merge, initial = None):
		width = 1
		while width < n:
			width *= 2
		self.root = SegmentTreeNode(0, width, initial, merge)
		self.root.value = 0
	
	def update(self, index, value):
		self.root.update(index, value)
	
	def pick(self, start, end):
		return self.root.pick(start, end)
	
	def to_list(self):
		items = []
		self.root.to_list(items)
		return items

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

def merge(a, b):
	if a == None:
		return b
	elif b == None:
		return a
	else:
		return a | b

st = SegmentTree(N, merge = merge)

for i, c in enumerate(map(int, input().split())):
	st.update(i, {c, })

for _ in range(Q):
	l, r = map(int, input().split())
	l -= 1
	r -= 1
	print(len(st.pick(l, r + 1)))

Submission status: Time Limit Exceeded

Solution code:
N, Q = input().split()
N = int(N)
Q = int(Q)
c = list(map(int, input().split()))
l = list()
r = list()
u = list()
U = list()
for i in range (Q):
    L, R = input().split()
    L = int(L) - 1
    R = int(R) - 1
    l.append(L)
    r.append(R)    
for i in range (Q):
    a = 0
    o = 0
    d = l[0]
    for i in range (r[0] - l[0] + 1):
        u.append (c[d])
        d = d + 1
    d = 0
    for i in range(len(u)):
        if not u[d] in U:
            U.append(u[d])
        d = d + 1
    print(len(U))
    u.clear()
    U.clear()
    del r[0]
    del l[0]

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    """
    1-indexed
    """
    def __init__(self, size):
        self.size = size
        self.data = [0] * (size + 1)

    def add(self, index, value=1):
        while index <= self.size:
            self.data[index] += value
            index += index & (-index)

    def sum(self, index):
        """
        右端含める
        """
        ret = 0
        while index:
            ret += self.data[index]
            index -= index & (-index)
        return ret

    def search(self, val):
        """
        x_1 + ... x_i >= val を満たす最小のi
        """
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)  # 一番上の長さ

        while step:
            if i + step <= self.size and s + self.data[i + step] < val:
                i += step
                s += self.data[i]
            step //= 2
        return i + 1

N, Q = map(int, input().split())
C = [-1] + list(map(int, input().split()))
tree = BIT(N)

query = [[] for _ in range(N + 1)]
for q in range(Q):
    l, r = map(int, input().split())
    query[r].append((q, l))

index = [-1] * (N + 1)
ans = [0] * Q

for r in range(1, N + 1):
    if index[C[r]] > 0:
        tree.add(index[C[r]], -1)
    tree.add(r, 1)
    index[C[r]] = r

    for q, l in query[r]:
        ans[q] = tree.sum(r) - tree.sum(l - 1)

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

Submission status: Time Limit Exceeded

Solution code:
N, Q = input().split()
N = int(N)
Q = int(Q)
c = list(map(int, input().split()))
l = list()
r = list()
u = list()
U = list()
for i in range (Q):
    L, R = input().split()
    L = int(L) - 1
    R = int(R) - 1
    l.append(L)
    r.append(R)    
for i in range (Q):
    a = 0
    o = 0
    d = l[0]
    for i in range (r[0] - l[0] + 1):
        u.append (c[d])
        d = d + 1
    d = 0
    for i in range(len(u)):
        if not u[d] in U:
            U.append(u[d])
        d = d + 1
    print(len(U))
    for i in range (len(U)):
        del U[0]
    for i in range (len(u)):
        del u[0]
    del r[0]
    del l[0]

Submission status: Time Limit Exceeded

Solution code:
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")

Submission status: Time Limit Exceeded

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

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[]
for i in range(q):
  l,r=map(int,input().split())
  query.append((l,r,i))
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_all=[[] for _ in range(n+1)]
for i in range(n):
  val=arr[i]
  if pos_now[val]==-1:
    bit.add(i+1,1)
    pos_now[val]=0
  pos_all[val].append(i+1)
for i in range(n+1):
  pos_all[i].append(-1)
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if pos_all[val][pos_now[val]+1]!=-1:
      pos_now[val]+=1
      bit.add(pos_all[val][pos_now[val]],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)

Submission status: Time Limit Exceeded

Solution code:
#参考https://qiita.com/takayg1/items/c811bd07c21923d7ec69

#####segfunc#####
def segfunc(x, y):
    return x+y
#################

#####ide_ele初期値#####
ide_ele = 0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    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])

    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

    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 function():
    N, Q = map(int, input().split())
    c = list(map(int, input().split()))
    lrs = [list(map(lambda x:int(x)-1, input().split())) for i in range(Q)]
    
    for i in range(len(lrs)):
        lrs[i] = [lrs[i][0], lrs[i][1], i]
    
    right_edge = [-1]*(N+1)
    seg = SegTree([0]*(N+1), segfunc, ide_ele)

    lrs = sorted(lrs, key = lambda x:x[1])
    order_num = 0
    answer = [0]*(Q)
    for i, c_o in enumerate(c):
        if right_edge[c_o] >= 0:
            seg.update(right_edge[c_o], 0)
        right_edge[c_o] = i
        seg.update(i, 1)
        
        for j in range(N):
            if order_num >= Q:
                break
            if lrs[order_num][1] == i:
                answer[lrs[order_num][2]] = [order_num,seg.query(lrs[order_num][0],lrs[order_num][1]+1)]
                order_num += 1
            else:
                break
    
    for i in range(len(answer)):
        print(answer[i][1])
        
if __name__ == '__main__':
    function()

Submission status: Time Limit Exceeded

Solution code:
#参考https://qiita.com/takayg1/items/c811bd07c21923d7ec69

#####segfunc#####
def segfunc(x, y):
    return x+y
#################

#####ide_ele初期値#####
ide_ele = 0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    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])

    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

    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 function():
    N, Q = map(int, input().split())
    c = list(map(int, input().split()))
    lrs = [list(map(lambda x:int(x)-1, input().split())) for i in range(Q)]
    
    for i in range(len(lrs)):
        lrs[i].append(i)
    
    right_edge = [-1]*(N+1)
    seg = SegTree([0]*(N+1), segfunc, ide_ele)
    # =============================================================================
    # print(seg.tree[1])
    # print(seg.query(0,7))
    # seg.update(0,100)
    # print(seg.tree)
    # =============================================================================
    
    lrs = sorted(lrs, key = lambda x:x[1])
    order_num = 0
    answer = [0]*(Q)
    for i, c_o in enumerate(c):
        if right_edge[c_o] >= 0:
            seg.update(right_edge[c_o], 0)
        right_edge[c_o] = i
        seg.update(i, 1)
        
        for j in range(N):
            if order_num >= Q:
                break
            if lrs[order_num][1] == i:
                answer[lrs[order_num][2]] = [order_num,seg.query(lrs[order_num][0],lrs[order_num][1]+1)]
                order_num += 1
            else:
                break
    
    for i in range(len(answer)):
        print(answer[i][1])
        
if __name__ == '__main__':
    function()

Submission status: Time Limit Exceeded

Solution code:
import bisect

def answer(kintama, lri0):
    tama = kintama[:]
    tama.sort()
    num = bisect.bisect_left(tama, lri0)
    return 5*10**5 - num

n, q = [int(i) for i in input().split()]
c = [int(i)-1 for i in input().split()]
lr = []
for i in range(q):
    lr_ = [int(_)-1 for _ in input().split()] + [i]
    lr.append(lr_)
lr.sort(key=lambda x: x[1])

k = 0
ans = []
kintama = [-10 for i in range(5*10**5)]

for i in range(q):
    while lr[i][1] > k:
        kintama[c[k]] = k
        k += 1
    kintama[c[k]] = k
    ans.append([answer(kintama, lr[i][0]), lr[i][2]])

ans.sort(key=lambda x: x[1])
[print(ans[i][0]) for i in range(q)]

Submission status: Time Limit Exceeded

Solution code:
#参考https://qiita.com/takayg1/items/c811bd07c21923d7ec69

#####segfunc#####
def segfunc(x, y):
    return x+y
#################

#####ide_ele初期値#####
ide_ele = 0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    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])

    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

    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 function():
    N, Q = map(int, input().split())
    c = list(map(int, input().split()))
    lrs = [list(map(lambda x:int(x)-1, input().split())) for i in range(Q)]
    
    for i in range(len(lrs)):
        lrs[i].append(i)
    
    right_edge = [-1]*(N+1)
    seg = SegTree([0]*(N+1), segfunc, ide_ele)
    # =============================================================================
    # print(seg.tree[1])
    # print(seg.query(0,7))
    # seg.update(0,100)
    # print(seg.tree)
    # =============================================================================
    
    lrs = sorted(lrs, key = lambda x:x[1])
    order_num = 0
    answer = [0]*(Q)
    for i, c_o in enumerate(c):
        if right_edge[c_o] >= 0:
            seg.update(right_edge[c_o], 0)
        right_edge[c_o] = i
        seg.update(i, 1)
        
        while order_num < Q:
            if lrs[order_num][1] == i:
                answer[lrs[order_num][2]] = [order_num,seg.query(lrs[order_num][0],lrs[order_num][1]+1)]
                order_num += 1
            else:
                break
    
    for i in range(len(answer)):
        print(answer[i][1])
        
if __name__ == '__main__':
    function()

Submission status: Time Limit Exceeded

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

cl = list(map(int,input().split()))

k = 1
e = 0
while(N>k):
    k*=2
    e+=1

d = (1<<e)-N

st = []
for _ in range(1<<(e+1)):
    st.append(set())

for i in range(N):
    st[i+(1<<e)].add(cl[i])

for f in range(e-1,-1,-1):
    for i in range(1<<f,(1<<(f+1))):
        st[i]=st[2*i].union(st[2*i+1])

for _ in range(Q):
    l,r = map(int,input().split())
    a = l-1 + (1<<e)
    b = r-1 + (1<<e)
    s = set()
    while(a<=b):
        if(a%2==1):
            s = s.union(st[a])
            a+=1
        if(b%2==0):
            s = s.union(st[b])
            b-=1
        a = a//2
        b = b//2
    print(len(s))

Submission status: Time Limit Exceeded

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

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[]
for i in range(q):
  l,r=map(int,input().split())
  query.append((l,r,i))
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_all=[[] for _ in range(n+1)]
for i in range(n):
  val=arr[i]
  if pos_now[val]==-1:
    bit.add(i+1,1)
    pos_now[val]=0
  pos_all[val].append(i+1)
for i in range(n+1):
  pos_all[i].append(-1)
cnt=collections.Counter(arr)
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if pos_all[val][pos_now[val]+1]!=-1:
      pos_now[val]+=1
      bit.add(pos_all[val][pos_now[val]],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)

Submission status: Time Limit Exceeded

Solution code:
#参考https://qiita.com/takayg1/items/c811bd07c21923d7ec69

#####segfunc#####
def segfunc(x, y):
    return x+y
#################

#####ide_ele初期値#####
ide_ele = 0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    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])

    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

    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 function():
    N, Q = map(int, input().split())
    c = list(map(int, input().split()))
    lrs = [list(map(lambda x:int(x)-1, input().split())) for i in range(Q)]
    
    for i in range(len(lrs)):
        lrs[i].append(i)
    
    right_edge = [-1]*(N+1)
    seg = SegTree([0]*(N+1), segfunc, ide_ele)
    # =============================================================================
    # print(seg.tree[1])
    # print(seg.query(0,7))
    # seg.update(0,100)
    # print(seg.tree)
    # =============================================================================
    
    lrs = sorted(lrs, key = lambda x:x[1])
    order_num = 0
    answer = [[] for _ in range(Q)]
    for i, c_o in enumerate(c):
        if right_edge[c_o] >= 0:
            seg.update(right_edge[c_o], 0)
        right_edge[c_o] = i
        seg.update(i, 1)
        
        while order_num < Q:
            if lrs[order_num][1] == i:
                answer[order_num] = [order_num,seg.query(lrs[order_num][0],lrs[order_num][1]+1)]
                order_num += 1
            else:
                break
    
    answer = sorted(answer,key=lambda x: lrs[x[0]][2])
    
    for i in range(len(answer)):
        print(answer[i][1])
        
if __name__ == '__main__':
    function()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LRI = []
    for i in range(Q):
        l, r = map( int, input().split())
        LRI.append((r,l,i))
    LRI.sort(key=lambda x:x[0])
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        if idx == 0:
            return 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

    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(now, 1)
            else:
                BIT_update( now, 1)
                BIT_update(lastAppend[c],-1)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(r) - BIT_query(l-1)
    print( "\n".join( map( str, ANS)))
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def BIT_query(BIT,idx):
  res_sum=0
  if idx==0:
    return 0
  while idx>0:
    res_sum+=BIT[idx]
    idx-=idx&(-idx)
  return res_sum

def BIT_update(BIT,idx,x,n):
  while idx<=n:
    BIT[idx]+=x
    idx+=idx&(-idx)
  return

def main():
  N,Q=map( int, input().split())
  C=list( map( int, input().split()))
  LRI=[]
  for i in range(Q):
    l,r=map( int, input().split())
    LRI.append((r,l,i))
  LRI=sorted(LRI)
  lastAppend=[-1]*(N+1)
  BIT=[0]*(N+1)
  ANS=[0]*Q
  now=1
  for r,l,i in LRI:
    while now <= r:
      c=C[now-1]
      if lastAppend[c]== -1:
        BIT_update(BIT,now,1,N)
      else:
        BIT_update(BIT,now,1,N)
        BIT_update(BIT,lastAppend[c],-1,N)
      lastAppend[c]=now                
      now+=1
    ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
  for ans in ANS:
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def BIT_query(BIT,idx):
    res_sum = 0
    if idx == 0:
        return 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum
def BIT_update(BIT,idx,x,n):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return
def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LRI = []
    for i in range(Q):
        l, r = map( int, input().split())
        LRI.append((r,l, i))
    LRI.sort(key=lambda x:x[0])
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(BIT, now, 1,N)
            else:
                BIT_update(BIT, now, 1,N)
                BIT_update(BIT, lastAppend[c],-1,N)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
    for ans in ANS:
        print(ans)    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#A1 ~ Aiまでの和 O(logN)
def BIT_query(BIT,idx):
    res_sum = 0
    if idx == 0:
        return 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(BIT,idx,x,n):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LRI = []
    for i in range(Q):
        l, r = map( int, input().split())
        LRI.append((r,l, i))
    LRI.sort(key=lambda x:x[0])
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(BIT, now, 1,N)
            else:
                BIT_update(BIT, now, 1,N)
                BIT_update(BIT, lastAppend[c],-1,N)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
    # print( "\n".join( map( str, ANS)))
    for ans in ANS:
        print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def BIT_query(BIT,idx):
  res_sum=0
  if idx==0:
    return 0
  while idx>0:
    res_sum+=BIT[idx]
    idx-=idx&(-idx)
  return res_sum

def BIT_update(BIT,idx,x,n):
  while idx<=n:
    BIT[idx]+=x
    idx+=idx&(-idx)
  return

def main():
  N,Q=map( int, input().split())
  C=list( map( int, input().split()))
  LRI=[]
  for i in range(Q):
    l,r=map( int, input().split())
    LRI.append((r,l,i))
  LRI.sort(key=lambda x:x[0])
  lastAppend=[-1]*(N+1)
  BIT=[0]*(N+1)
  ANS=[0]*Q
  now=1
  for r,l,i in LRI:
    while now <= r:
      c=C[now-1]
      if lastAppend[c]== -1:
        BIT_update(BIT,now,1,N)
      else:
        BIT_update(BIT,now,1,N)
        BIT_update(BIT,lastAppend[c],-1,N)
      lastAppend[c]=now                
      now+=1
    ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
  for ans in ANS:
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#A1~Aiまでの和 O(logN)　iが与えられたとき a1~aiまでの和を計算する(O(log n))
def BIT_query(BIT,idx):
  res_sum=0
  if idx==0:
    return 0
  while idx>0:
    res_sum+=BIT[idx]
    idx-=idx&(-idx)
  return res_sum

#Ai+=x O(logN)　iとxが与えられたとき ai+=x とする (O(log n))
def BIT_update(BIT,idx,x,n):
  while idx<=n:
    BIT[idx]+=x
    idx+=idx&(-idx)
  return

def main():
  N,Q=map( int, input().split())
  C=list( map( int, input().split()))
  LRI=[]
  for i in range(Q):
    l,r=map( int, input().split())
    LRI.append((r,l,i))
  LRI.sort(key=lambda x:x[0])
  lastAppend=[-1]*(N+1)
  BIT=[0]*(N+1)
  ANS=[0]*Q
  now=1
  for r,l,i in LRI:
    while now <= r:
      c=C[now-1]
      if lastAppend[c]== -1:
        BIT_update(BIT,now,1,N)
      else:
        BIT_update(BIT,now,1,N)
        BIT_update(BIT,lastAppend[c],-1,N)
      lastAppend[c]=now                
      now+=1
    ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
  for ans in ANS:
    print(ans)
    
if __name__ == '__main__':
    main()