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: Accepted

Solution code:
from sys import stdin

input = stdin.readline
from collections import defaultdict


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

    def add(self, ind, x=1):
        ind += 1
        while ind <= self.N:
            self.arr[ind] += x
            ind += (ind & -ind)

    def get_sum(self, ind):
        ind += 1
        res = 0
        while ind > 0:
            res += self.arr[ind]
            ind -= (ind & -ind)
        return res


def solve():
    N, Q = map(int, input().split())
    c = list(map(int, input().split()))
    query = [tuple(map(int, inp.split())) for inp in stdin.read().splitlines()]
    prev = [-1] * (N+1)
    nxt = [-1] * (N+1)
    for i, v in enumerate(c):
        if prev[v] != -1:
            nxt[prev[v]] = i
        prev[v] = i
    q = defaultdict(list)
    for i, (l, r) in enumerate(query):
        q[l - 1].append((r - 1, i))
    bit = BIT(N)
    ans = [0] * Q
    for l in range(N - 1, -1, -1):
        if nxt[l] != -1:
            bit.add(nxt[l], 1)
        for r, i in q[l]:
            ans[i] = r - l + 1 - bit.get_sum(r)
    for a in ans:
        print(a)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


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

    def add(self, i, x):
        i += 1
        while i <= self.N:
            self.T[i] += x
            i += i & -i

    def _sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.T[i]
            i -= i & -i
        return s

    def sum(self, i, j):
        si = self._sum(i - 1)
        sj = self._sum(j)
        return sj - si
    

def main():
    N, M = read_values()
    C = read_list()
    Q = []
    for i in range(M):
        l, r = read_index()
        Q.append((l, r, i))
    Q.sort(key=lambda a: a[1])

    ans = [0] * M
    T = [-1] * M
    bit = BIT(N)
    q = 0
    # print(Q)
    for i in range(N):
        c = C[i] - 1
        t = T[c]
        if t != -1:
            bit.add(t, -1)
        T[c] = i
        bit.add(i, 1)

        # print(i, T, bit.T)
        while q < len(Q) and i == Q[q][1]:
            l, r, k = Q[q]
            ans[k] = bit.sum(l, r)
            q += 1

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

  
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
"""
    Satwik_Tiwari ;) .
    12th Sept , 2020  - Saturday
"""

#===============================================================================================
#importing some useful libraries.
from __future__ import division, print_function

# from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# from itertools import *
# import bisect
# from heapq import *
# from math import *
# from copy import *
# from collections import deque
# from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
# from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
# from itertools import permutations as permutate
# from bisect import bisect_left as bl

#If the element is already present in the list,
# the left most position where element has to be inserted is returned.

# from bisect import bisect_right as br
# from bisect import bisect

#If the element is already present in the list,
# the right most position where element has to be inserted is returned

#==============================================================================================
#fast I/O region
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

#===============================================================================================
### START ITERATE RECURSION ###
# from types import GeneratorType
# def iterative(f, stack=[]):
#   def wrapped_func(*args, **kwargs):
#     if stack: return f(*args, **kwargs)
#     to = f(*args, **kwargs)
#     while True:
#       if type(to) is GeneratorType:
#         stack.append(to)
#         to = next(to)
#         continue
#       stack.pop()
#       if not stack: break
#       to = stack[-1].send(to)
#     return to
#   return wrapped_func
#### END ITERATE RECURSION ####

#===============================================================================================
#some shortcuts

mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") #for fast input
def out(var): sys.stdout.write(str(var))  #for fast output, always take string
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())
# def graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  #as stdout.write always print sring.
def testcase(t):
    for pp in range(t):
        solve(pp)
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def google(p):
    print('Case #'+str(p)+': ',end='')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(x, y, p) :
    res = 1     # Initialize result
    x = x % p  # Update x if it is more , than or equal to p
    if (x == 0) :
        return 0
    while (y > 0) :
        if ((y & 1) == 1) : # If y is odd, multiply, x with result
            res = (res * x) % p

        y = y >> 1      # y = y/2
        x = (x * x) % p
    return res
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True

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

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

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

    def build(self,a):
        for i in range(len(a)):
            k = a[i]
            x = i+1
            while(x<=self.n):
                self.tree[x]+=k
                x+=x&(-x)

def solve(case):
    n,q = sep()
    c = lis()
    query = []
    for i in range(q):
        l,r = sep()
        query.append((r,l,i))

    query = sorted(query,key=lambda x:x[0])
    bit = BIT(n)
    lastvis = [-1]*(n+1)
    ind = 0
    ans = [0]*q
    for i in range(n):
        if(lastvis[c[i]] != -1):
            bit.update(lastvis[c[i]]+1,-1)

        lastvis[c[i]] = i
        bit.update(i+1,1)
        while(ind<q and query[ind][0] == i+1):
            ans[query[ind][2]] = (bit.sum(i+1) - bit.sum(query[ind][1]-1))
            ind+=1

    print('\n'.join(str(ans[i]) for i in range(len(ans))))

testcase(1)
# testcase(int(inp()))

Submission status: Accepted

Solution code:
"""
    Satwik_Tiwari ;) .
    12th Sept , 2020  - Saturday
"""

#===============================================================================================
#importing some useful libraries.
from __future__ import division, print_function

# from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# from itertools import *
# import bisect
# from heapq import *
# from math import *
# from copy import *
# from collections import deque
# from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
# from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
# from itertools import permutations as permutate
# from bisect import bisect_left as bl

#If the element is already present in the list,
# the left most position where element has to be inserted is returned.

# from bisect import bisect_right as br
# from bisect import bisect

#If the element is already present in the list,
# the right most position where element has to be inserted is returned

#==============================================================================================
#fast I/O region
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

#===============================================================================================
### START ITERATE RECURSION ###
# from types import GeneratorType
# def iterative(f, stack=[]):
#   def wrapped_func(*args, **kwargs):
#     if stack: return f(*args, **kwargs)
#     to = f(*args, **kwargs)
#     while True:
#       if type(to) is GeneratorType:
#         stack.append(to)
#         to = next(to)
#         continue
#       stack.pop()
#       if not stack: break
#       to = stack[-1].send(to)
#     return to
#   return wrapped_func
#### END ITERATE RECURSION ####

#===============================================================================================
#some shortcuts

mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") #for fast input
def out(var): sys.stdout.write(str(var))  #for fast output, always take string
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())
# def graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  #as stdout.write always print sring.
def testcase(t):
    for pp in range(t):
        solve(pp)
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def google(p):
    print('Case #'+str(p)+': ',end='')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(x, y, p) :
    res = 1     # Initialize result
    x = x % p  # Update x if it is more , than or equal to p
    if (x == 0) :
        return 0
    while (y > 0) :
        if ((y & 1) == 1) : # If y is odd, multiply, x with result
            res = (res * x) % p

        y = y >> 1      # y = y/2
        x = (x * x) % p
    return res
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True

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

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

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

    def build(self,a):
        for i in range(len(a)):
            k = a[i]
            x = i+1
            while(x<=self.n):
                self.tree[x]+=k
                x+=x&(-x)
class Query:
    def __init__(self, r,l, idx):
        self.l = l
        self.r = r
        self.idx = idx

def solve(case):
    n,q = sep()
    c = lis()
    query = []
    for i in range(q):
        l,r = sep()
        query.append(Query(r,l,i))

    query = sorted(query,key=lambda x:x.r)
    bit = BIT(n)
    lastvis = [-1]*(n+1)
    ind = 0
    ans = [0]*q
    for i in range(n):
        if(lastvis[c[i]] != -1):
            bit.update(lastvis[c[i]]+1,-1)

        lastvis[c[i]] = i
        bit.update(i+1,1)
        while(ind<q and query[ind].r == i+1):
            ans[query[ind].idx] = (bit.sum(i+1) - bit.sum(query[ind].l-1))
            ind+=1

    print('\n'.join(str(ans[i]) for i in range(len(ans))))

testcase(1)
# testcase(int(inp()))

Submission status: Accepted

Solution code:
"""
    Satwik_Tiwari ;) .
    12th Sept , 2020  - Saturday
"""

#===============================================================================================
#importing some useful libraries.
from __future__ import division, print_function

# from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# from itertools import *
# import bisect
# from heapq import *
# from math import *
# from copy import *
# from collections import deque
# from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
# from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
# from itertools import permutations as permutate
# from bisect import bisect_left as bl

#If the element is already present in the list,
# the left most position where element has to be inserted is returned.

# from bisect import bisect_right as br
# from bisect import bisect

#If the element is already present in the list,
# the right most position where element has to be inserted is returned

#==============================================================================================
#fast I/O region
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

#===============================================================================================
### START ITERATE RECURSION ###
# from types import GeneratorType
# def iterative(f, stack=[]):
#   def wrapped_func(*args, **kwargs):
#     if stack: return f(*args, **kwargs)
#     to = f(*args, **kwargs)
#     while True:
#       if type(to) is GeneratorType:
#         stack.append(to)
#         to = next(to)
#         continue
#       stack.pop()
#       if not stack: break
#       to = stack[-1].send(to)
#     return to
#   return wrapped_func
#### END ITERATE RECURSION ####

#===============================================================================================
#some shortcuts

mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") #for fast input
def out(var): sys.stdout.write(str(var))  #for fast output, always take string
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())
# def graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  #as stdout.write always print sring.
def testcase(t):
    for pp in range(t):
        solve(pp)
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def google(p):
    print('Case #'+str(p)+': ',end='')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(x, y, p) :
    res = 1     # Initialize result
    x = x % p  # Update x if it is more , than or equal to p
    if (x == 0) :
        return 0
    while (y > 0) :
        if ((y & 1) == 1) : # If y is odd, multiply, x with result
            res = (res * x) % p

        y = y >> 1      # y = y/2
        x = (x * x) % p
    return res
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True

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

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

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

    def build(self,a):
        for i in range(len(a)):
            k = a[i]
            x = i+1
            while(x<=self.n):
                self.tree[x]+=k
                x+=x&(-x)
class Query:
    def __init__(self, r,l, idx):
        self.l = l
        self.r = r
        self.idx = idx

def solve(case):
    n,q = sep()
    c = lis()
    query = []
    for i in range(q):
        l,r = sep()
        query.append(Query(r,l,i))

    query.sort(key=lambda x:x.r)
    bit = BIT(n)
    lastvis = [-1]*(n+1)
    ind = 0
    ans = [0]*q
    for i in range(n):
        if(lastvis[c[i]] != -1):
            bit.update(lastvis[c[i]]+1,-1)

        lastvis[c[i]] = i
        bit.update(i+1,1)
        while(ind<q and query[ind].r == i+1):
            ans[query[ind].idx] = (bit.sum(i+1) - bit.sum(query[ind].l-1))
            ind+=1

    print('\n'.join(str(ans[i]) for i in range(len(ans))))

testcase(1)
# testcase(int(inp()))

Submission status: Accepted

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

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

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

    def build(self,a):
        for i in range(len(a)):
            k = a[i]
            x = i+1
            while(x<=self.n):
                self.tree[x]+=k
                x+=x&(-x)
class Query:
    def __init__(self, r,l, idx):
        self.l = l
        self.r = r
        self.idx = idx

def solve(case):
    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(Query(r,l,i))

    query.sort(key = lambda x:x.r)
    bit = BIT(n)
    lastvis = [-1]*(n+1)
    ind = 0
    ans = [0]*q
    for i in range(n):
        if(lastvis[c[i]] != -1):
            bit.update(lastvis[c[i]]+1,-1)

        lastvis[c[i]] = i
        bit.update(i+1,1)
        while(ind<q and query[ind].r == i+1):
            ans[query[ind].idx] = (bit.sum(i+1) - bit.sum(query[ind].l-1))
            ind+=1

    print('\n'.join(str(ans[i]) for i in range(len(ans))))
    # for i in range(q):
    #     print(ans[i])
solve(1)

Submission status: Accepted

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

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

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

    def build(self,a):
        for i in range(len(a)):
            k = a[i]
            x = i+1
            while(x<=self.n):
                self.tree[x]+=k
                x+=x&(-x)
class Query:
    def __init__(self, r,l, idx):
        self.l = l
        self.r = r
        self.idx = idx

def solve(case):
    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(Query(r,l,i))

    query.sort(key = lambda x:x.r)
    bit = BIT(n)
    lastvis = [-1]*(n+1)
    ind = 0
    ans = [0]*q
    for i in range(n):
        if(lastvis[c[i]] != -1):
            bit.update(lastvis[c[i]]+1,-1)

        lastvis[c[i]] = i
        bit.update(i+1,1)
        while(ind<q and query[ind].r == i+1):
            ans[query[ind].idx] = (bit.sum(i+1) - bit.sum(query[ind].l-1))
            ind+=1

    # print('\n'.join(str(ans[i]) for i in range(len(ans))))
    for i in range(q):
        print(ans[i])
solve(1)

Submission status: Accepted

Solution code:
MAX = 1000001

class Query:
    def __init__(self, l, r, idx): 
        self.l = l 
        self.r = r 
        self.idx = idx 
  
class BIT:
    def __init__(self,n):
        self.n = n
        self.tree = [0]*(n+1)

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

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

    def build(self,a):
        for i in range(len(a)):
            k = a[i]
            x = i+1
            while(x<=self.n):
                self.tree[x]+=k
                x+=x&(-x)
  
def answeringQueries(arr, n, queries, q): 
  
    # initialising bit array 
    bit = BIT(n)
  
    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX
  
    # answer for each query 
    ans = [0] * q 
  
    query_counter = 0
    for i in range(n): 
  
        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1: 
            bit.update(last_visit[arr[i]] + 1, -1)
  
        # Setting last_visit[arr[i]] as i and  
        # updating the bit array accordingly 
        last_visit[arr[i]] = i 
        bit.update(i + 1, 1)
  
        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i: 
            ans[queries[query_counter].idx] = bit.sum(queries[query_counter].r + 1) -bit.sum(queries[query_counter].l)
            query_counter += 1
  
    # print answer for each query 
    for i in range(q): 
        print(ans[i]) 
  
# Driver Code 
if __name__ == "__main__": 
    n,q = map(int,input().split())
    a = list(map(int,input().split()))
    # n = len(a)
    queries = []
    for i in range(q):
        l,r = map(int,input().split())
        queries.append(Query(l-1,r-1,i))
    # queries = [Query(0, 4, 0),
    #            Query(1, 3, 1),
    #            Query(2, 4, 2)]
    # q = len(queries)
  
    queries.sort(key = lambda x: x.r) 
    answeringQueries(a, n, queries, q)

Submission status: Accepted

Solution code:
MAX = 1000001

class Query:
    def __init__(self, l, r, idx): 
        self.l = l 
        self.r = r 
        self.idx = idx 
  
# updating the bit array 
def update(idx, val, bit, n): 
    while idx <= n: 
        bit[idx] += val 
        idx += idx & -idx 
  
# querying the bit array 
def query(idx, bit, n): 
    summ = 0
    while idx: 
        summ += bit[idx] 
        idx -= idx & -idx 
    return summ 
  
def answeringQueries(arr, n, queries, q): 
  
    # initialising bit array 
    bit = [0] * (n + 1) 
  
    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX
  
    # answer for each query 
    ans = [0] * q 
  
    query_counter = 0
    for i in range(n): 
  
        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1: 
            update(last_visit[arr[i]] + 1, -1, bit, n) 
  
        # Setting last_visit[arr[i]] as i and  
        # updating the bit array accordingly 
        last_visit[arr[i]] = i 
        update(i + 1, 1, bit, n) 
  
        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        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
  
    # print answer for each query 
    for i in range(q): 
        print(ans[i]) 
  
# Driver Code 
if __name__ == "__main__": 
    n,q = map(int,input().split())
    a = list(map(int,input().split()))
    # n = len(a)
    queries = []
    for i in range(q):
        l,r = map(int,input().split())
        queries.append(Query(l-1,r-1,i))
    # queries = [Query(0, 4, 0),
    #            Query(1, 3, 1),
    #            Query(2, 4, 2)]
    # q = len(queries)
  
    queries.sort(key = lambda x: x.r) 
    answeringQueries(a, n, queries, q)