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: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


class SegmentTree:
    def segfunc(self,x,y):
        #ここに評価
        return x + y

    #nは総数、initがlist,ide_eleが元
    def __init__(self,n,init,ide_ele):
        self.n = n
        self.ide_ele = ide_ele
        self.num = 2**(n-1).bit_length()
        self.seg = [ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1] = init[i]
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2])
    
    
    def update(self,k,x):
        k += self.num-1
        self.seg[k] += x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1],self.seg[2*k+2])
    
    def query(self,p,q):
        if q <= p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p > 1:
            if p & 1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q & 1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p //= 2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res


n,k = m()

Seg = SegmentTree(n,[0 for i in range(n)],0)
a = l()

data = []
for i in range(k):
    po = l()
    po.append(i)
    data.append(po)

data.sort(key = lambda x:x[1])

where = [-1 for i in range(n)]
ans = [0 for i in range(n)]
left = -1
for i in range(k):
    aaa = data[i]
    aaa[0] -= 1
    aaa[1] -= 1
    if aaa[1] > left:
        for j in range(left+1,aaa[1]+1):
            popopo = a[j]-1
            if where[popopo] != -1:
                Seg.update(where[popopo],-1)
            Seg.update(j,1)
            where[popopo] = j
        left = aaa[1]
    ans[aaa[2]] = Seg.query(aaa[0],aaa[1]+1)



ans.sort(key = lambda x:x[0])

for i in range(k):
    print(ans[i])

Submission status: Runtime Error

Solution code:
I = [int(_) for _ in open(0).read().split()]
N, Q=I[:2]
C = I[2:2 + N]
LR = I[2 + N:]
2 ** 40
2 ** 20
Query = []
for i, lr in enumerate(zip(LR[::2], LR[1::2])):
    l, r = lr
    Query += [r * 2 ** 40 + l * 2 ** 20 + i]
for i, c in enumerate(C):
    Query += [(i + 1) * 2 ** 40 + c]
Query.sort()
c_i = [-1] * (N + 1)

class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])
 
    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])
 
    def operate_right(self, p, v):  # apply operator from the right side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])
 
    def operate_left(self, p, v):  # apply operator from the left side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])
 
    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)
 

ans = [0] * N
st = SegmentTree([0] * (N + 5), lambda x,y:x+y, 0)
for q in Query:
    x, yz = divmod(q, 2 ** 40)
    y, z = divmod(yz, 2 ** 20)
    if y==0:
        if c_i[z] != -1:
            st.operate_right(c_i[z], -1)
        c_i[z] = x
        st.operate_right(x, 1)
    else:
        ans[z] = st.query(y, x + 1)
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
n,q = map(int, input().split())
cs = list(map(int, input().split()))

prevs = [-1] * n
# 左端
sts = [-1] * n
for i,c in enumerate(cs):
    if prevs[c] != -1:
        sts[prevs[c]] = i
    prevs[c] = i

qs = [[] for i in range(n)] 
for i in range(q):
    l,r = map(int, input().split())
    l -= 1
    r -= 1
    qs[l].append((r,i))

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

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

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

bit = BIT(n)
ans = [0] * q
for l in range(n-1,-1,-1):
    # 矢印を追加
    if sts[l] != -1:
        bit.add(sts[l], 1)
    for r,i in qs[l]:
        cnt = bit.sum(r)
        ans[i] = r - l + 1 - cnt

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

Submission status: Runtime Error

Solution code:
from collections import Counter
N, Q = map(int, input().split())
lis = input().split()
for i in range(0, Q):
    s, e = map(int, input().split())
    temp = lis[s-1:e-1]
    print(len(Counter(temp).keys))

Submission status: Runtime Error

Solution code:
from collections import Counter
N, Q = map(int, input().split())
lis = input().split()
for i in range(0, Q):
    s, e = map(int, input().split())
    temp = lis[s-1, e-1]
    print(len(Counter(temp).keys))

Submission status: Runtime Error

Solution code:
import sys
import math
import time
sys.setrecursionlimit(int(1e6))
if False:
    dprint = print
else:
    def dprint(*args):
        pass

n, q = list(map(int, input().split()))
c = list(map(int, input().split()))

c_d = [0] * n
col_i = [-1] * n
for i in range(q):
    col = c[i] - 1
    c_d[i] = col_i[col]
    col_i[col] = i

for i in range(q):
    l, r = list(map(int, input().split()))
    l -= 1
    r -= 1
    dup = 0
    for j in range(l, r+1):
        if (l <= c_d[j]) and (c_d[j] <= r):
            dup += 1
    ans = r - l + 1 - dup
    print(ans)

Submission status: Runtime Error

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

n, q = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1]*(n+1)
A = [0]*q
U = 10**6
RLI = []
for i in range(n):
  l, r = map(int, input().split())
  RLI.append(r*U*U + l*U + i)
RLI.sort()
B = [0]*(n+1)
def add(i, a):
  while i <= n:
    B[i] += a
    i += i & -i
def acc(i):
  res = 0
  while i:
    res += B[i]
    i -= i & -i
  return res
temp = 1
for rli in RLI:
  rl, i = divmod(rli, U)
  r, l = divmod(rl, U)
  while temp <= r:
    c = C[temp]
    add(temp, 1)
    if D[c] != -1:
      add(D[c], -1)
    D[c] = temp
    temp += 1
  A[i] = acc(r) - acc(l-1)
print(*A, sep="\n")

Submission status: Runtime Error

Solution code:
n, q = [ int(x) for x in input().split() ]
xs = input().split()
buf, idx = [{}], {}
for x in xs:
  idx[x] = idx.get(x, 0) + 1
  buf.append(idx.copy())
for _ in range(q)
  i, j = [ int(x) for x in input().split() ]
  idx = buf[j].copy()
  for k,v in buf[i-1].items(): idx[k] -= v
  print(len([ 1 for v in idx.values() if v ]))

Submission status: Runtime Error

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import Decimal #floatの高精度ver, 渡すのはstr型で
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

n,q=map(int,input().split())
A=list(map(int,input().split()))
Q=[]
for i in range(q):
    a,b=map(int,input().split())
    a-=1 ; b-=1
    Q.append([i,a,b])
Q=sorted(Q, key=lambda x: x[2])
ANS=[-1]*q

A=[i-1 for i in A]

C=[-1]*n #その色の一番右の球はどこ
# G=[0]*n #右球があるところに1

mae=[2**i for i in range(21)]  #10**6 = 2**19.93
import bisect as bi
ookisa= mae[ bi.bisect_left(mae,n) ]
BIT=[0]*(ookisa+1)
#BIT[0]は使用しない(1-indexedにしたいので)
# print(BIT)

def bsum(i):
    ans=0
    while i>0:
        ans+=BIT[i]
        i -= i & (-i)
    return ans

def badd(i,x):
    while i<=len(BIT):
        BIT[i]+=x
        i += i & (-i)
def bmenos(i):
    while i<=len(BIT):
        BIT[i]-=1
        i += i&(-i)

# for i in range(1,len(A)+1): #配列をぶち込む
#     badd(i,A[i-1])

# print(BIT)

left=Q[0][1] ; right=Q[0][2]
for i in range(right,-1,-1):
    if C[A[i]]==-1:
        C[A[i]]=i
for i in C:
    if i==-1 : continue
    badd(i+1, 1) #1-indexed


# print("A",A)
# print("C",C)
# print("G",G)
# print("ruiG",ruiG)
# print("ANS",ANS)
#print(BIT)
ANS[Q[0][0]]=bsum(right+1)-bsum(left)  #0問目

for l in Q[1:]:
    newleft=l[1] ; newright=l[2]
    for i in range(newright, right,-1):
        if C[A[i]] ==-1: #まだ発見してない色
            C[A[i]] = i
            badd(i+1,1)
        else:
            bmenos(C[A[i]]+1)
            C[A[i]] =i
            badd(i+1,1)
    ANS[l[0]]= bsum(newright+1)-bsum(newleft)
    left=newleft ; right=newright
    #print(BIT, bsum(newright+1)-bsum(newleft))


for i in ANS:
    print(i)

Submission status: Runtime Error

Solution code:
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
 
# sys.stdin = open('input')
 
def inp(force_list=False):
    re = map(int, raw_input().split())
    if len(re) == 1 and not force_list:
        return re[0]
    return re
 
def inst():
    return raw_input().strip()
 
def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
 
mod = 1000000007
def idx(c):
    return ord(c) - ord('a')

class Fenwick(object):
    def __init__(self, n):
        self.n = n
        self.da = [0] * n
    
    def add(self, pos, x):
        while pos < self.n:
            self.da[pos] += x
            pos |= pos + 1

    def ps(self, pos):
        re = 0
        while pos >= 0:
            re += self.da[pos]
            pos &= pos + 1
            pos -= 1
        return re

    def sum(self, x, y):
        return self.ps(y) - self.ps(x-1)

def my_main():
    n, nq = inp()
    da = inp()
    q = []
    for i in range(nq):
        l, r = inp()
        q.append((l, r, i))
    q.sort(key=lambda e:e[-2])
    mp = [-1] * (510000)
    now = -1
    fw = Fenwick(n)
    ans = [0] * nq
    for l, r, idx in q:
        l -= 1
        r -= 1
        while now < r:
            now += 1
            if mp[da[now]]!=-1:
                fw.add(mp[da[now]], -1)
            mp[da[now]] = now
            fw.add(now, 1)
        ans[idx] = fw.sum(l, r)

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



my_main()

Submission status: Runtime Error

Solution code:
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
 
# sys.stdin = open('input')
 
def inp(force_list=False):
    re = map(int, raw_input().split())
    if len(re) == 1 and not force_list:
        return re[0]
    return re
 
def inst():
    return raw_input().strip()
 
def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
 
mod = 1000000007
def idx(c):
    return ord(c) - ord('a')

class Fenwick(object):
    def __init__(self, n):
        self.n = n
        self.da = [0] * n
    
    def add(self, pos, x):
        while pos < self.n:
            self.da[pos] += x
            pos |= pos + 1

    def ps(self, pos):
        re = 0
        while pos >= 0:
            re += self.da[pos]
            pos &= pos + 1
            pos -= 1
        return re

    def sum(self, x, y):
        return self.ps(y) - self.ps(x-1)

def my_main():
    n, nq = inp()
    da = inp()
    q = []
    for i in range(nq):
        l, r = inp()
        q.append((l, r, i))
    q.sort(key=lambda e:e[-2])
    mp = [-1] * (n+5)
    now = -1
    fw = Fenwick(n)
    ans = [0] * nq
    for l, r, idx in q:
        l -= 1
        r -= 1
        while now < r:
            now += 1
 
            if mp[da[now]]!=-1:
                fw.add(mp[da[now]], -1)
            try:
                mp[da[now]] = now
            except:
                pass
            fw.add(now, 1)
        ans[idx] = fw.sum(l, r)

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


            

 
 
 
 
my_main()

Submission status: Runtime Error

Solution code:
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
 
# sys.stdin = open('input')
 
def inp(force_list=False):
    re = map(int, raw_input().split())
    if len(re) == 1 and not force_list:
        return re[0]
    return re
 
def inst():
    return raw_input().strip()
 
def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
 
mod = 1000000007
def idx(c):
    return ord(c) - ord('a')

class Fenwick(object):
    def __init__(self, n):
        self.n = n
        self.da = [0] * n
    
    def add(self, pos, x):
        while pos < self.n:
            self.da[pos] += x
            pos |= pos + 1

    def ps(self, pos):
        re = 0
        while pos >= 0:
            re += self.da[pos]
            pos &= pos + 1
            pos -= 1
        return re

    def sum(self, x, y):
        return self.ps(y) - self.ps(x-1)

def my_main():
    n, nq = inp()
    da = inp()
    q = []
    for i in range(nq):
        l, r = inp()
        q.append((l, r, i))
    q.sort(key=lambda e:e[-2])
    mp = [-1] * (n+5)
    now = -1
    fw = Fenwick(n)
    ans = [0] * nq
    for l, r, idx in q:
        l -= 1
        r -= 1
        while now < r:
            now += 1
            try:
                if mp[da[now]]!=-1:
                    fw.add(mp[da[now]], -1)
            except:pass
            mp[da[now]] = now
            fw.add(now, 1)
        ans[idx] = fw.sum(l, r)

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


            

 
 
 
 
my_main()

Submission status: Runtime Error

Solution code:
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
 
# sys.stdin = open('input')
 
def inp(force_list=False):
    re = map(int, raw_input().split())
    if len(re) == 1 and not force_list:
        return re[0]
    return re
 
def inst():
    return raw_input().strip()
 
def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
 
mod = 1000000007
def idx(c):
    return ord(c) - ord('a')

class Fenwick(object):
    def __init__(self, n):
        self.n = n
        self.da = [0] * n
    
    def add(self, pos, x):
        while pos < self.n:
            self.da[pos] += x
            pos |= pos + 1

    def ps(self, pos):
        re = 0
        while pos >= 0:
            re += self.da[pos]
            pos &= pos + 1
            pos -= 1
        return re

    def sum(self, x, y):
        return self.ps(y) - self.ps(x-1)

def my_main():
    n, nq = inp()
    da = inp()
    q = []
    try:
        for i in range(nq):
            l, r = inp()
            q.append((l, r, i))
        q.sort(key=lambda e:e[-2])
        mp = [-1] * (n+5)
        now = -1
        fw = Fenwick(n)
        ans = [0] * nq
    except:
        pass
    for l, r, idx in q:
        l -= 1
        r -= 1
        while now < r:
            now += 1
            if mp[da[now]]!=-1:
                fw.add(mp[da[now]], -1)
            mp[da[now]] = now
            fw.add(now, 1)
        ans[idx] = fw.sum(l, r)

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


            

 
 
 
 
my_main()

Submission status: Runtime Error

Solution code:
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
 
# sys.stdin = open('input')
 
def inp(force_list=False):
    re = map(int, raw_input().split())
    if len(re) == 1 and not force_list:
        return re[0]
    return re
 
def inst():
    return raw_input().strip()
 
def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
 
mod = 1000000007
def idx(c):
    return ord(c) - ord('a')

class Fenwick(object):
    def __init__(self, n):
        self.n = n
        self.da = [0] * n
    
    def add(self, pos, x):
        while pos < self.n:
            self.da[pos] += x
            pos |= pos + 1

    def ps(self, pos):
        re = 0
        while pos >= 0:
            re += self.da[pos]
            pos &= pos + 1
            pos -= 1
        return re

    def sum(self, x, y):
        return self.ps(y) - self.ps(x-1)

def my_main():
    n, nq = inp()
    da = inp()
    q = []
    for i in range(nq):
        l, r = inp()
        q.append((l, r, i))
    q.sort(key=lambda e:e[-2])
    mp = [-1] * (n+5)
    now = -1
    fw = Fenwick(n)
    ans = [0] * nq
    for l, r, idx in q:
        l -= 1
        r -= 1
        while now < r:
            now += 1
            if mp[da[now]]!=-1:
                fw.add(mp[da[now]], -1)
            mp[da[now]] = now
            fw.add(now, 1)
        try:
            ans[idx] = fw.sum(l, r)
        except:
            pass
    print '\n'.join(map(str, ans))


            

 
 
 
 
my_main()

Submission status: Runtime Error

Solution code:
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
 
# sys.stdin = open('input')
 
def inp(force_list=False):
    re = map(int, raw_input().split())
    if len(re) == 1 and not force_list:
        return re[0]
    return re
 
def inst():
    return raw_input().strip()
 
def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
 
mod = 1000000007
def idx(c):
    return ord(c) - ord('a')

class Fenwick(object):
    def __init__(self, n):
        self.n = n
        self.da = [0] * n
    
    def add(self, pos, x):
        while pos < self.n:
            self.da[pos] += x
            pos |= pos + 1

    def ps(self, pos):
        re = 0
        while pos >= 0:
            re += self.da[pos]
            pos &= pos + 1
            pos -= 1
        return re

    def sum(self, x, y):
        return self.ps(y) - self.ps(x-1)

def my_main():
    n, nq = inp()
    da = inp()
    q = []
    for i in range(nq):
        l, r = inp()
        q.append((l, r, i))
    q.sort(key=lambda e:e[-2])
    mp = [-1] * (n+5)
    now = -1
    fw = Fenwick(n)
    ans = [0] * nq
    for l, r, idx in q:
        l -= 1
        r -= 1
        while now < r:
            now += 1
            if mp[da[now]]!=-1:
                fw.add(mp[da[now]], -1)
            mp[da[now]] = now
            fw.add(now, 1)
        ans[idx] = fw.sum(l, r)
        # print mp
    print '\n'.join(map(str, ans))


            

 
 
 
 
my_main()

Submission status: Runtime Error

Solution code:
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
 
# sys.stdin = open('input')
 
def inp(force_list=False):
    re = map(int, raw_input().split())
    if len(re) == 1 and not force_list:
        return re[0]
    return re
 
def inst():
    return raw_input().strip()
 
def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
 
mod = 1000000007
def idx(c):
    return ord(c) - ord('a')

class Fenwick(object):
    def __init__(self, n):
        self.n = n
        self.da = [0] * n
    
    def add(self, pos, x):
        while pos < self.n:
            self.da[pos] += x
            pos |= pos + 1

    def ps(self, pos):
        re = 0
        while pos >= 0:
            re += self.da[pos]
            pos &= pos + 1
            pos -= 1
        return re

    def sum(self, x, y):
        return self.ps(y) - self.ps(x-1)

def my_main():
    n, nq = inp()
    da = inp()
    q = []
    for i in range(nq):
        q.append(inp() + [i])
    q.sort(key=lambda e:e[-2])
    mp = {}
    now = -1
    fw = Fenwick(n)
    ans = [0] * nq
    for l, r, idx in q:
        l -= 1
        r -= 1
        while now < r:
            now += 1
            if da[now] in mp:
                fw.add(mp[da[now]], -1)
            mp[da[now]] = now
            fw.add(mp[da[now]], 1)
        ans[idx] = fw.sum(l, r)
    print '\n'.join(map(str, ans))


            

 
 
 
 
my_main()

Submission status: Runtime Error

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    class SegTree:
        def __init__(self,N,ide,segfunc=min):
            self.ide_ele = ide
            """
            ex)
             最小値のセグ木 → +inf
              和のセグ木 → 0
              積のセグ木 → 1
              gcdのセグ木 → 0
            """
            
            self.segfunc=segfunc
            
            #num:N以上の最小の2のべき乗
            self.num =2**(N-1).bit_length()
            self.seg=[self.ide_ele]*2*self.num

        #リストで初期化する
        def setL(self,init_val):
            #init_valは操作する数列
            for i in range(N):
                self.seg[i+self.num-1]=init_val[i]    
            #built
            for i in range(self.num-2,-1,-1) :
                self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 


        #k番目の値をxに更新
        def update(self,k,x):
            k += self.num-1
            self.seg[k] = x
            while k:
                k = (k-1)//2
                self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])


        #[p,q)の区間に対するクエリへの応答
        def query(self,p,q):
            if q<=p:
                return self.ide_ele
            p += self.num-1
            q += self.num-2
            res=self.ide_ele
            while q-p>1:
                if p&1 == 0:
                    res = self.segfunc(res,self.seg[p])
                if q&1 == 1:
                    res = self.segfunc(res,self.seg[q])
                    q -= 1
                p = p//2
                q = (q-1)//2
            if p == q:
                res = self.segfunc(res,self.seg[p])
            else:
                res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
            return res

    mod=10**9+7
    N,Q=MI()
    C=LI()
    for i in range(N):
        C[i]-=1
    
    R=[0]*N
    L=[0]*N
    I=[0]*N
    for i in range(Q):
        l,r,=MI()
        l-=1
        r-=1
        R[i]=r
        L[i]=l
        I[i]=i
        
    R,L,I = zip(*sorted(zip(R,L,I)))
    seg=SegTree(N,0,lambda a,b: a+b)
    Rn=[-1]*N#各色ごとに最右がどこか保持する
    
    """
    事前処理 + クエリの高速処理
    or 
    クエリ先読み
    
    とりあえずrの昇順にクエリをソートしておく．
    結局，各色ごとに1つ前のやつがどこにあるかが問題=>各色ごとに最新の物だけを保持すれば良い．
    最終的にクエリに答えたいので，i番目が使えるかどうかseg木で管理
    """
    
    ans=[0]*Q
    now=-1
    for ii in range(N):
        r=R[ii]
        l=L[ii]
        i=I[ii]
        while now<r:
            now+=1
            c=C[now]
            old=Rn[c]#その色の古いやつ
            if old!=-1:#あれば削除
                seg.update(old,0)
            #最新を追加
            Rn[c]=now
            seg.update(now,1)
        ans[i]=seg.query(l,r+1)
        
    for i in range(Q):
        print(ans[i])
                
                
            
    
    

main()

Submission status: Runtime Error

Solution code:
from operator import itemgetter
import sys
def read():
    return sys.stdin.readline().rstrip()
def main():
    N, Q = map(int, read().split())
    C = list(map(int, read().split()))
    E = []

    D = [-1] * N
    for i in range(N):
        D_i = D[C[i]]
        if D_i != -1:
            E.append((D_i, i, -1))
        D[C[i]] = i

    for i in range(Q):
        l, r = map(int, input().split())
        E.append((l - 1, r - 1, i))

    def f(tup):
        return tup[0]
    E.sort(key=f, reverse=True)

    # Binary Indexed Tree (Fenwick Tree)
    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)

    ANS = [0] * Q
    d = BIT(N)
    for e in E:
        if e[2] == -1:
            d.add(e[1], 1)
        else:
            ANS[e[2]] = e[1] - e[0] + 1 - d.sum(e[1])

    for i in range(Q):
        print(ANS[i])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class SegTreeLayer:
    def __init__(self, ndata, fill, function, segsize=1,
                 upper_layer=None, lower_layer=None):
        self.data = [fill]*ndata
        self.function = function
        self.segsize = segsize
        self.upper_layer = upper_layer
        self.lower_layer = lower_layer
        
        
        ndata_upper = (ndata+1)//2 if ndata>1 else 0
        if not self.upper_layer and ndata_upper>0:
            self.upper_layer = SegTreeLayer(
                ndata_upper, fill, self.function, self.segsize*2, lower_layer=self)

    def update(self, i, value):
        self.data[i] = value

        if not self.upper_layer: return
        v_upper = vi = self.data[i]
        
        j = i-1 if i&1 else i+1
        if j<len(self.data):
            vj = self.data[j]
            v_upper = self.function(vi, vj)
            
        self.upper_layer.update(i//2, v_upper)

    def query(self, ibgn, iend):
        if ibgn%self.segsize==0 and iend-ibgn==self.segsize:
            return self.data[ibgn//self.segsize]

        imid = (ibgn//self.segsize)*self.segsize + self.segsize//2
        if iend<=imid or imid<=ibgn: return self.lower_layer.query(ibgn, iend)
        return self.function(
            self.lower_layer.query(ibgn, imid),
            self.lower_layer.query(imid, iend)
        )

    def extend(self, add, fill):
        self.data.extend([fill]*add)
        ndata = len(self.data)
        ndata_upper_new = (ndata+1)//2 if ndata>1 else 0
        
        if not self.upper_layer and ndata_upper_new>0:
            self.upper_layer = SegTreeLayer(
                self.segsize*2, self.function, lower_layer=self)

        if self.upper_layer:
            ndata_upper_now = len(self.upper_layer.data)
            return self.upper_layer.extend(ndata_upper_new - ndata_upper_now, fill)

        return self

N, Q = map(int, input().split())
C = list(map(int, input().split()))
LR = sorted([[q]+list(map(int, input().split())) for q in range(Q)], key=lambda x:x[2])

bottom = SegTreeLayer(N, 0, lambda x,y: x+y)
top = bottom
while top.upper_layer: top = top.upper_layer

I = [None]*(N+1)
i = 0
ans = [None]*Q
for q, l, r in LR:
    while i<r:
        bottom.update(i, 1)
        
        c = C[i]
        i_old = I[c]
        if i_old is not None: bottom.update(i_old, 0)
        
        I[c] = i
        i+=1
    ans[q] = top.query(l-1,top.segsize)

for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
class SegTreeLayer:
    def __init__(self, segsize, function, upper_layer=None, lower_layer=None):
        self.data = []
        self.segsize = segsize
        self.function = function
        self.upper_layer = upper_layer
        self.lower_layer = lower_layer

    def update(self, i, value):
        self.data[i] = value

        if not self.upper_layer: return
        v_upper = vi = self.data[i]
        
        j = i-1 if i&1 else i+1
        if j<len(self.data):
            vj = self.data[j]
            v_upper = self.function(vi, vj)
            
        self.upper_layer.update(i//2, v_upper)

    def query(self, ibgn, iend):
        if ibgn%self.segsize==0 and iend-ibgn==self.segsize:
            return self.data[ibgn//self.segsize]

        imid = (ibgn//self.segsize)*self.segsize + self.segsize//2
        if iend<=imid or imid<=ibgn: return self.lower_layer.query(ibgn, iend)
        return self.function(
            self.lower_layer.query(ibgn, imid),
            self.lower_layer.query(imid, iend)
        )

    def extend(self, add, fill):
        self.data.extend([fill]*add)
        ndata = len(self.data)
        ndata_upper_new = (ndata+1)//2 if ndata>1 else 0
        
        if not self.upper_layer and ndata_upper_new>0:
            self.upper_layer = SegTreeLayer(
                self.segsize*2, self.function, lower_layer=self)

        if self.upper_layer:
            ndata_upper_now = len(self.upper_layer.data)
            return self.upper_layer.extend(ndata_upper_new - ndata_upper_now, fill)

        return self

N, Q = map(int, input().split())
C = list(map(int, input().split()))
LR = sorted([[q]+list(map(int, input().split())) for q in range(Q)], key=lambda x:x[2])

bottom = SegTreeLayer(1, lambda x,y: x+y)
top = bottom.extend(N, 0)


I = [None]*(N+1)
i = 0
ans = [None]*Q
for q, l, r in LR:
    while i<r:
        bottom.update(i, 1)
        
        c = C[i]
        i_old = I[c]
        if i_old is not None: bottom.update(i_old, 0)
        
        I[c] = i
        i+=1
    ans[q] = top.query(l-1,top.segsize)

for a in ans:
    print(a)