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
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r):
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)

from operator import add
def resolve():
    n, q = map(int, input().split())
    C = list(map(lambda x : int(x) - 1, input().split()))

    # build segment tree
    A = [0] * n
    used = set()
    for i, c in enumerate(C):
        if c in used:
            continue
        A[i] += 1
        used.add(c)
    tree = SegmentTree(A, add, 0)

    # caluculate next
    next = [-1] * n
    col_to_idx = {}
    for i in range(n - 1, -1, -1):
        c = C[i]
        if c in col_to_idx:
            next[i] = col_to_idx[c]
        col_to_idx[c] = i

    # process queries
    queries = [None] * q
    for i in range(q):
        l, r = map(int, input().split())
        l -= 1
        queries[i] = (l, r, i)
    queries.sort(reverse = 1)

    ans = [0] * q
    for l, c in enumerate(C):
        while queries and queries[-1][0] == l:
            l, r, i = queries.pop()
            ans[i] = tree.sum(l, r)
        if next[l] != -1:
            tree.add(next[l], 1)
        tree.add(l, -1)
    print(*ans, sep = '\n')
resolve()

Submission status: Time Limit Exceeded

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


def read():
    N, Q = map(int, input().strip().split())
    C = list(map(int, input().strip().split()))
    LR = []
    for i in range(Q):
        l, r = map(int, input().strip().split())
        LR.append((l-1, r))
    return N, Q, C, LR


def solve(N, Q, C, LR, D=300):
    Z = [Counter() for i in range(N//D+2)]
    for i in range(0, N//D):
        Z[i] = Counter(C[i*D:(i+1)*D])
    for l, r in LR:
        chunk_l = l // D
        chunk_r = r // D
        if chunk_r - chunk_l <= 1:
            print(len(Counter(C[l:r])))
        else:
            p1 = len(Counter(C[l:(chunk_l+1)*D]))
            p3 = len(Counter(C[chunk_r*D:r]))
            z = Counter()
            for i in range(chunk_l+1, chunk_r):
                z += Z[i]
            p2 = len(z)
            print(p1+p2+p3)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

Solution code:
import collections as col
import numpy as np

N,Q=map(int, input().split())
c=np.array(list(map(int, input().split())))

for i in range(Q):
    A,B=map(int, input().split())
    print(len(col.Counter(c[A-1:B])))

Submission status: Time Limit Exceeded

Solution code:
import io
import os


# From https://www.geeksforgeeks.org/mos-algorithm-query-square-root-decomposition-set-1-introduction/
def solve(N, Q, C, LR):
    BLOCK = int(Q ** 0.5)
    order = range(len(LR))
    order = sorted(order, key=lambda i: LR[i][1])
    order = sorted(order, key=lambda i: LR[i][0] // BLOCK)

    currL, currR = 0, 0
    countUniq = [0 for i in range(N + 1)]
    numUniq = 0

    ans = [0] * len(LR)
    for i in order:
        L, R = LR[i]

        while currL < L:
            x = C[currL]
            countUniq[x] -= 1
            if countUniq[x] == 0:
                numUniq -= 1
            currL += 1

        while currL > L:
            x = C[currL - 1]
            if countUniq[x] == 0:
                numUniq += 1
            countUniq[x] += 1
            currL -= 1
        while currR <= R:
            x = C[currR]
            if countUniq[x] == 0:
                numUniq += 1
            countUniq[x] += 1
            currR += 1

        while currR > R + 1:
            x = C[currR - 1]
            countUniq[x] -= 1
            if countUniq[x] == 0:
                numUniq -= 1
            currR -= 1

        # print(C[L : R + 1], "is", [i for i, x in enumerate(countUniq) if x > 0], numUniq)
        ans[i] = numUniq
    return "\n".join(map(str, ans))


if False:
    import random

    random.seed(0)
    N = 5 * 10 ** 5
    Q = 5 * 10 ** 5
    C = [random.randint(1, N) for i in range(N)]
    LR = []
    for i in range(Q):
        l = random.randint(1, N)
        r = random.randint(1, N)
        if l > r:
            l, r = r, l
        LR.append((l, r))
    solve(N, Q, C, LR)
    exit()


if __name__ == "__main__":
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    N, Q = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]
    LR = [[int(x) - 1 for x in input().split()] for i in range(Q)]  # 0-indexed
    print(solve(N, Q, C, LR))

Submission status: Time Limit Exceeded

Solution code:
f=len
s=set
n,q=map(int,input().split())
col=list(map(int,input().split()))
le=f(s(col))
bo=False
if le==n:
	bo=True

for _ in range(q):
	l,r=map(int,input().split())
	if bo:
		print(r-l+1)
		continue
	if l==r:
		print(1)
	else:
		print(f(s(col[l-1:r])))

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()
    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:
import sys
input = sys.stdin.readline
from collections import defaultdict
class BIT:
    """
    Binary Index Tree
    ###1-origin####

    add :L[i]+=x
    sum: sum(L[:l])
    range_sum : sum(L[l:r])

    #material http://hos.ac/slides/20140319_bit.pdf
    """

    def __init__(self, N, init_val=0):
        self.init_val = init_val
        self.size = N
        self.L = [init_val]*(N+1)

    def sum(self, r):
        """
        sum[,r)
        calc sum from L[0] to L[r-1]
        """
        ret = self.init_val
        while r > 0:
            ret += self.L[r]
            r -= r & (-r)

        return ret

    def range_sum(self, l, r):
        
        """
        idx周りが怪しい?
        sum[l,r)
        calc sum from L[l] to L[r-1]
        """
        return self.sum(r-1)-self.sum(l-1)

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

    def bisect(self,k:float)->int:
        """ binary search on BIT
        get index x s.t self.sum(,)>=k

        RETURN:
            res:index of x
        """
        k+=1 #convert k into 1-index

        res=0
        N=1
        while N<self.size:
            N*=2

        i=N//2
        while i>0:
            if(res+i<self.size and self.L[res+i]<k): #move to rignt on tree
                k-=self.L[res+i]
                res+=i
            #else move to left
            i//=2
        return res+1



N,Q = map(int,input().split())
C=list(map(int,input().split()))
pos=[]
for i in range(Q):
    l,r = map(int,input().split())
    pos.append((l,r,i))


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

last_appeared=defaultdict(int)

B = BIT(N,0)

ans=[-1]*Q

cur_r=1
for l,r,i in pos:
    while cur_r<=r:
        last = last_appeared[C[cur_r-1]]
        if last==0:#first add
            B.add(cur_r,1)
        else:
            B.add(last,-1)
            B.add(cur_r,1)

        last_appeared[C[cur_r-1]]=cur_r #lastの更新
        cur_r+=1

    assert l>=1
    ans[i]=B.sum(r)-B.sum(l-1)


print("\n".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
col=list(map(int,input().split()))
le=len(set(col))
bo=False
if le==n:
	bo=True

for _ in range(q):
	l,r=map(int,input().split())
	if bo:
		print(r-l+1)
		continue
	if l==r:
		print(1)
	else:
		print(len(set(col[l-1:r])))

Submission status: Time Limit Exceeded

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

#A1 ~ Aiまでの和 O(logN)
#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()
    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

#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()
    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)))
    
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split(' '))
cs = list(map(int, input().split(' ')))
 
 
for _ in range(q):
  l,r = map(int, input().split(' '))
  print(len(set(cs[l-1:r])))

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
c=list(map(int,input().split()))
lr=[list(map(int,input().split())) for _ in range(q)]
lri=[[lr[i][0],lr[i][1],i] for i in range(q)]
lri.sort(key=lambda x:x[1])
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=segfunc, ide_ele=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
st=SegTree([0]*(n+1))
dc={}
ans=[0]*q
j=0
for i in range(n):
  x=c[i]
  if x in dc:
    st.update(dc[x],0)
    st.update(i+1,1)
    dc[x]=i+1
  else:
    st.update(i+1,1)
    dc[x]=i+1
  while j<q and i+1==lri[j][1]:
    l,r,k=lri[j]
    ans[k]=st.query(l,r+1)
    j+=1
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import io
import os


# From https://www.geeksforgeeks.org/mos-algorithm-query-square-root-decomposition-set-1-introduction/
def solve(N, Q, C, LR):
    order = sorted(range(len(LR)), key=lambda i: LR[i][1])

    currL, currR = 0, 0
    countUniq = [0 for i in range(N + 1)]
    numUniq = 0

    ans = [0] * len(LR)
    for i in order:
        L, R = LR[i]

        while currL < L:
            x = C[currL]
            countUniq[x] -= 1
            if countUniq[x] == 0:
                numUniq -= 1
            currL += 1

        while currL > L:
            x = C[currL - 1]
            if countUniq[x] == 0:
                numUniq += 1
            countUniq[x] += 1
            currL -= 1
        while currR <= R:
            x = C[currR]
            if countUniq[x] == 0:
                numUniq += 1
            countUniq[x] += 1
            currR += 1

        while currR > R + 1:
            x = C[currR - 1]
            countUniq[x] -= 1
            if countUniq[x] == 0:
                numUniq -= 1
            currR -= 1

        # print(C[L : R + 1], "is", [i for i, x in enumerate(countUniq) if x > 0], numUniq)
        ans[i] = numUniq
    print("\n".join(map(str, ans)))


if False:
    import random

    random.seed(0)
    N = 5 * 10 ** 5
    Q = 5 * 10 ** 5
    C = [random.randint(1, N) for i in range(N)]
    LR = []
    for i in range(Q):
        l = random.randint(1, N)
        r = random.randint(1, N)
        if l > r:
            l, r = r, l
        LR.append((l, r))
    solve(N, Q, C, LR)
    exit()


if __name__ == "__main__":
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    N, Q = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]
    LR = [[int(x) - 1 for x in input().split()] for i in range(Q)]  # 0-indexed
    solve(N, Q, C, LR)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,Q=map(int, input().split())
c=np.array(list(map(int, input().split())))

for i in range(Q):
    A,B=map(int, input().split())
    print(np.unique(c[A-1:B]).size)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
    res = [None] * n
    for i in range(n):
        res[i] = II()
    return res
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI_() + [i]
    return res
def FR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
mod = 1000000007
inf = float('INF')
#solve
def solve():
    n, q = LI()
    c = LI()
    lr = LIR(q)
    ans = [None] * q
    lr.sort(key=lambda x: x[1])
    dp = [-1] * (max(c) + 1)
    bit = [0] * (n + 1)
    def add(i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= n:
            bit[x - 1] += w
            x += x & -x
        return
    def sum(i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += bit[x - 1]
            x -= x & -x
        return res
    t = 0
    def f(t):
        l, r, j = lr[t]
        xr = sum(r)
        xl = sum(l-1)
        tmp = xr - xl
        ans[j] = tmp
    for i in range(n):
        ci = c[i]
        l = dp[ci]
        add(i, 1)
        dp[ci] = i
        if l != -1:
            add(l, -1)
        while t < q and lr[t][1] <= i:
            f(t)
            t += 1
        if t == q:
            break
    for ai in ans:
        print(ai) 
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,Q=map(int, input().split())
c=np.array(list(map(int, input().split())))
l=np.array([list(map(int, input().split()))  for _ in range(Q)])

for i in range(Q):
    print(np.unique(c[l[i][0]-1:l[i][1]]).size)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, a):
        self.padding = 0
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)//2] = self.seg_data[i] + self.seg_data[i-1]
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.seg_data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.seg_data[idx] = self.seg_data[2*idx+1] + self.seg_data[2*idx+2]
    
    def query(self, i, j):
        # [i, j)
        if i == j:
            return self.seg_data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = self.padding
            while idx1 < idx2 + 1:
                if idx1&1 == 0: # idx1が偶数
                    result = result + self.seg_data[idx1]
                if idx2&1 == 1: # idx2が奇数
                    result = result + self.seg_data[idx2]
                    idx2 -= 1
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            return result
    
    @property
    def data(self):
        return self.seg_data[self.N-1:self.N-1+self.n]


N, Q = map(int, input().split())
C = list(map(int, input().split()))
ans = [0] * Q
last_appeared = [-1] * (N + 1)
st = SegmentTree([0]*N)
li = [[] for i in range(N+1)]
for i in range(Q):
    l, r = map(int, input().split())
    li[r].append((i, l-1))

now = 0
for r in range(1, N+1):
    for i, l in li[r]:
        while now < r:
            c = C[now]
            pre_idx, last_appeared[c] = last_appeared[c], now
            if pre_idx >= 0:
                st.update(pre_idx, 0)
            st.update(now, 1)
            now += 1
        ans[i] = st.query(l, r)


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

Submission status: Time Limit Exceeded

Solution code:
import math
N,Q=[int(r) for r in input().split()]
C=input().split()

for i in range(Q):
  a,b=[int(r) for r in input().split()]
  print(len(set(C[a-1:b])))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,Q=map(int, input().split())
c=np.array(list(map(int, input().split())))
l=[list(map(int, input().split()))  for _ in range(Q)]

for i in range(Q):
    print(np.unique(c[l[i][0]-1:l[i][1]]).size)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
C = list(map(int, input().split()))
ans = []
for i in range(q):
    l, r = map(int, input().split())
    ans.append(len(set(C[l - 1:r])))
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
c = list(map(int, input().split()))
lr = [list(map(int, input().split())) for _ in range(Q)]

keys = set([])
cnts = [{}]
cnt = {}
for i, ci in enumerate(c):
    key = str(ci)
    keys.add(key)
    cnt.setdefault(key, 0)
    cnt[key] += 1
    cnts.append(dict(cnt))

# print("#", cnts)
for i, (li, ri) in enumerate(lr):
    ans = 0
    for key in keys:
        cnts[ri].setdefault(key, 0)
        cnts[li - 1].setdefault(key, 0)
        if cnts[ri][key] > cnts[li - 1][key]:
            ans += 1
    #
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import io
import os
from collections import Counter

from bisect import bisect_left, bisect_right


# From https://www.geeksforgeeks.org/mos-algorithm-query-square-root-decomposition-set-1-introduction/
def solve(C, LR):
    order = sorted(range(len(LR)), key=lambda i: LR[i][1])

    currL, currR = 0, 0
    currUniq = Counter()

    ans = [0] * len(LR)
    for i in order:
        L, R = LR[i]

        while currL < L:
            x = C[currL]
            currUniq[x] -= 1
            if currUniq[x] == 0:
                del currUniq[x]
            currL += 1

        while currL > L:
            x = C[currL - 1]
            currUniq[x] += 1
            if currUniq[x] == 0:
                del currUniq[x]
            currL -= 1
        while currR <= R:
            x = C[currR]
            currUniq[x] += 1
            if currUniq[x] == 0:
                del currUniq[x]
            currR += 1

        while currR > R + 1:
            x = C[currR - 1]
            currUniq[x] -= 1
            if currUniq[x] == 0:
                del currUniq[x]
            currR -= 1

        # print(C[L : R + 1], "is", currUniq)
        ans[i] = len(currUniq)
    print("\n".join(map(str, ans)))


if False:
    import random

    random.seed(0)
    N = 5 * 10 ** 5
    Q = 5 * 10 ** 5
    C = [random.randint(1, N) for i in range(N)]
    LR = []
    for i in range(Q):
        l = random.randint(1, N)
        r = random.randint(1, N)
        if l > r:
            l, r = r, l
        LR.append((l, r))
    solve(C, LR)
    exit()


if __name__ == "__main__":
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    N, Q = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]
    LR = [[int(x) - 1 for x in input().split()] for i in range(Q)]  # 0-indexed
    solve(C, LR)

Submission status: Time Limit Exceeded

Solution code:
MAX = 1000001
class Query: 
    def __init__(self, l, r, idx): 
        self.l = l 
        self.r = r 
        self.idx = idx 

def query(idx, bit, n): 
    summ = 0
    while idx: 
        summ += bit[idx] 
        idx -= idx & -idx 
    return summ 

def update(idx, val, bit, n): 
    while idx <= n: 
        bit[idx] += val 
        idx += idx & -idx 
  
def answeringQueries(arr, n, queries, q): 
  
    bit = [0] * (n + 1) 
    last_visit = [-1] * MAX
    ans = [0] * q 
  
    query_counter = 0
    for i in range(n):  
        if last_visit[arr[i]] != -1: 
            update(last_visit[arr[i]] + 1, -1, bit, n)  
        last_visit[arr[i]] = i 
        update(i + 1, 1, bit, n) 
        while query_counter < q and queries[query_counter].r == i: 
            ans[queries[query_counter].idx] = query(queries[query_counter].r + 1, bit, n) - query(queries[query_counter].l, bit, n) 
            query_counter += 1
    for i in range(q): 
        print(ans[i]) 

if __name__ == "__main__":
    n,q = map(int,input().split())
    arr = list(map(int,input().split()))
    queries = []
    for i in range(q):
        a,b = map(int,input().split())
        queries.append(Query(a-1,b-1,i))
    queries.sort(key = lambda x: x.r) 
    answeringQueries(arr, n, queries, q)

Submission status: Time Limit Exceeded

Solution code:
import math
N,Q=[int(r) for r in input().split()]
C=input().split()

for i in range(Q):
  a,b=[int(r) for r in input().split()]
  ans=C[a-1:b]
  
  
  print(len(set(ans)))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
Qs = list(map(int, input().split()))
Qs = [set([Qs[i]]) for i in range(n)]

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

def init(init_val):
  #set_val
  for i in range(n):
    seg[i+num-1]=init_val[i]  
  #built
  for i in range(num-2,-1,-1) :
    seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
  
def update(k,x):
  k += num-1
  seg[k] = x
  while k:
    k = (k-1)//2
    seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
  
def query(p,q):
  if q<=p:
    return ide_ele
  p += num-1
  q += num-2
  res=ide_ele
  while q-p>1:
    if p&1 == 0:
      res = segfunc(res,seg[p])
    if q&1 == 1:
      res = segfunc(res,seg[q])
      q -= 1
    p = p//2
    q = (q-1)//2
  if p == q:
    res = segfunc(res,seg[p])
  else:
    res = segfunc(segfunc(res,seg[p]),seg[q])
  return res

#####単位元######
ide_ele = set([])

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
init(Qs)

for _ in range(q):
  l, r = map(int, input().split())
  print(len(query(l-1,r)))

Submission status: Time Limit Exceeded

Solution code:
# [temp1.py] => [29-07-2020 @ 10:25:10] 
# Author & Template by : Udit "luctivud" Gupta
# https://www.linkedin.com/in/udit-gupta-1b7863135/


import math;   from collections import *
import sys;    from functools import reduce
import time;   from itertools import groupby

# sys.setrecursionlimit(10**6)

def input()         : return sys.stdin.readline()
def get_ints()      : return map(int, input().strip().split())
def get_list()      : return list(get_ints())
def get_string()    : return list(input().strip().split())
def printxsp(*args) : return print(*args, end="")
def printsp(*args)  : return print(*args, end=" ")


DIRECTIONS = [(+0, +1), (+0, -1), (+1, +0), (+1, -1)] 
NEIGHBOURS = [(-1, -1), (-1, +0), (-1, +1), (+0, -1),\
              (+1, +1), (+1, +0), (+1, -1), (+0, +1)]


CAPS_ALPHABETS = {chr(i+ord('A')) : i for i in range(26)}
SMOL_ALPHABETS = {chr(i+ord('a')) : i for i in range(26)}
INF = float('inf')


# Custom input output is now piped through terminal commands.
# for _test_ in range(int(input())): 

maxn = int(5e5) + 2
  
def update(idx, val, bit, n): 
    while idx <= n: 
        bit[idx] += val 
        idx += idx & -idx 
  
def query(idx, bit, n): 
    summ = 0
    while idx: 
        summ += bit[idx] 
        idx -= idx & -idx 
    return summ 
  
def solve(arr, n, queries, q): 
    bit = [0] * (n + 1) 
    prev = [-1] * maxn  
    ans = [0] * q 
    count = 0
    for i in range(n): 
        if prev[arr[i]] != -1: 
            update(prev[arr[i]] + 1, -1, bit, n) 
        prev[arr[i]] = i 
        update(i + 1, 1, bit, n) 
        while count < q and queries[count][2] == i: 
            ans[queries[count][0]] = query(queries[count][2] + 1, bit, n) - query(queries[count][1], bit, n) 
            count += 1
    for i in range(q): 
        print(ans[i]) 

# main
n, q = get_ints()
a = get_list()
queries = []
for i in range(q):
	l, r = get_ints()
	queries.append((i, l-1, r-1))
queries = sorted(queries, key = lambda x: x[2]) 
solve(a, n, queries, q) 

# print("Time Elapsed: {}".format(float(S34p-S34t)))

# Binary Indexed Tree code taken from https://www.geeksforgeeks.org/queries-number-distinct-elements-subarray/

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    n, q = map(int, input().split())
    c = list(map(int,input().split()))
    for _ in range(q):
        l, r = map(int, input().split())
        print(len(set(c[l-1:r])))
main()

Submission status: Time Limit Exceeded

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


def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    Qu = []

    for i in range(Q):
        l, r = map(int, input().split())
        Qu.append((r, l, i))
    Qu.sort()
    ans = [0] * Q
    rp = 0
    la = [-1] * (N + 1)
    B = BIT(N)
    for r, l, i in Qu:
        for j in range(rp, r):
            k = C[j]
            if la[k] >= 0:
                B.add(la[k], -1)
            la[k] = j + 1
            B.add(la[k], 1)
        ans[i] = B.get(l - 1, r)
        rp = r
    print('\n'.join(str(i) for i in ans))

main()