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:
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 + 1)
    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))

    E.sort(key=lambda tup: tup[0], 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: Time Limit Exceeded

Solution code:
import numpy as np

N, Q = input().split()
cn = np.array(input().split(), np.int64)

for _ in range(int(Q)):
  i, j = input().split()
  if i == j:
    print(1)
  else:
  	print(np.unique(cn[int(i)-1: int(j)]).size)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, Q = input().split()
cn = np.array(input().split(), np.int64)

for _ in range(int(Q)):
  i, j = input().split()
  print(np.unique(cn[int(i)-1: int(j)]).size)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np

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

for _ in range(int(Q)):
  i, j = input().split()
  print(len(set(cn[int(i)-1: int(j)])))

Submission status: Time Limit Exceeded

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 + 1)
    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: Time Limit Exceeded

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 = {C[i]: -1 for i in range(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: Time Limit Exceeded

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

    D = {C[i]: -1 for i in range(N)}
    for i in range(N):
        if D[C[i]] != -1:
            E.append((D[C[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: Time Limit Exceeded

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,r)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, Q = mapint()
Cs = list(mapint())
LR = []
for i in range(Q):
    l, r = mapint()
    LR.append((l, r, i))
LR.sort(key=lambda x:x[1])
A = [0]*N

def add(A,a,w):#リストに値を追加する関数
    x = a
    while x <= N:
        A[x-1] += w
        x += x&(-x)

def sums(A,a):#k番目までの和
    x = a
    S = 0
    while x != 0:
        S += A[x-1]
        x -= x&(-x)
    return S

ans = [0]*Q
idx = 0
last_appeared = [-1]*(N+1)
for i in range(N):
    c = Cs[i]
    if last_appeared[c]==-1:
        last_appeared[c] = i+1
        add(A, i+1, 1)
    else:
        past = last_appeared[c]
        last_appeared[c] = i+1
        add(A, past, -1)
        add(A, i+1, 1)
    while idx<Q and LR[idx][1]<=i+1:
        l, r, ans_idx = LR[idx]
        ans[ans_idx] = sums(A, r)-sums(A, l-1)
        idx += 1
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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

    D = {C[i]: -1 for i in range(N)}
    for i in range(N):
        if D[C[i]] == -1:
            D[C[i]] = i
        else:
            E.append((D[C[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: Time Limit Exceeded

Solution code:
def add(idx):
    global s
    if cnt[cs[idx]]==0:
        s += 1
    cnt[cs[idx]] += 1

def delete(idx):
    global s
    cnt[cs[idx]] -= 1
    if cnt[cs[idx]]==0:
        s -= 1

def distribute(idx):
    v[idx]^=True
    if v[idx]:
        add(idx)
    else:
        delete(idx)

N,Q=map(int,input().split())
cs=list(map(lambda x:int(x)-1,input().split()))

v=[False]*N
cnt=[0]*N

querys = []
for i in range(Q):
    l,r=map(int,input().split())
    querys.append((l-1,r))
order=[i for i in range(Q)]
order.sort(key=lambda x:querys[x])

###
#for i in order:
#    print(i, querys[i])

###
nl=0
nr=0
s=0
ans=[0]*Q
for i in order:
    #while nl > querys[i][0]: # いらない？nlはふえるだけ？
    #    nl -=1
    #    distribute(nl)
    while nr < querys[i][1]:
        distribute(nr)
        nr +=1
    while nl < querys[i][0]:
        distribute(nl)
        nl +=1
    while nr > querys[i][1]:
        nr -=1
        distribute(nr)
    ans[i] = s
for i in range(Q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = [([int(i) for i in input().split()], j) for j in range(Q)]
    Query.sort(key=lambda p: p[0][1])
    lastappend = [0]*(N+1)

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

    def add(tree, i, x):
        while i <= N:
            tree[i] += x
            i += i & -i
    bit = [0]*(N+1)

    for i, a in enumerate(C, start=1):
        if i <= Query[0][0][1]:
            lastappend[a] = i
    for la in lastappend[1:]:
        if la != 0:
            add(bit, la, 1)
    pre = Query[0][0][1]
    ans = []
    for (le, ri), j in Query:
        if pre <= N and pre < ri:
            for i in range(pre+1, ri+1):
                pre_i = lastappend[C[i-1]]
                if pre_i != 0:
                    add(bit, pre_i, -1)
                lastappend[C[i-1]] = i
                add(bit, i, 1)
            pre = ri
        ans.append((j, sum(bit, ri) - sum(bit, le-1)))
    ans.sort()
    for _, a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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


def main():
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = [([int(i) for i in input().split()], j) for j in range(Q)]
    Query.sort(key=lambda p: p[0][1])
    lastappend = [0]*(N+1)
    bit = Bit(N)

    for i, a in enumerate(C, start=1):
        if i <= Query[0][0][1]:
            lastappend[a] = i
    for la in lastappend[1:]:
        if la != 0:
            bit.add(la, 1)
    pre = Query[0][0][1]
    ans = []
    for (le, ri), j in Query:
        if pre <= N and pre < ri:
            for i in range(pre+1, ri+1):
                pre_i = lastappend[C[i-1]]
                if pre_i != 0:
                    bit.add(pre_i, -1)
                lastappend[C[i-1]] = i
                bit.add(i, 1)
            pre = ri
        ans.append((j, bit.sum(ri) - bit.sum(le-1)))
    ans.sort()
    for _, a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class RangeUpdate:
    def __init__(self, n):
        self.p = Bit(n + 1)
        self.q = Bit(n + 1)

    def add(self, s, t, x):
        t += 1
        self.p.add(s, -x * s)
        self.p.add(t, x * t)
        self.q.add(s, x)
        self.q.add(t, -x)

    def sum(self, s, t):
        t += 1
        return self.p.sum(t) + self.q.sum(t) * t - \
            self.p.sum(s) - self.q.sum(s) * s


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

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

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


def main():
    import sys
    input = sys.stdin.buffer.readline
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = [([int(i) for i in input().split()], j) for j in range(Q)]
    Query.sort(key=lambda p: p[0][1])
    lastappend = [0]*(N+1)
    bit = RangeUpdate(N)

    for i, a in enumerate(C, start=1):
        if i <= Query[0][0][1]:
            lastappend[a] = i
    for la in lastappend[1:]:
        if la != 0:
            bit.add(la, la, 1)
    pre = Query[0][0][1]
    ans = []
    for (le, ri), j in Query:
        if pre <= N and pre < ri:
            for i in range(pre+1, ri+1):
                pre_i = lastappend[C[i-1]]
                if pre_i != 0:
                    bit.add(pre_i, pre_i, -1)
                lastappend[C[i-1]] = i
                bit.add(i, i, 1)
            pre = ri
        ans.append((j, bit.sum(le, ri)))
    ans.sort()
    for _, a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    D = {C[i]: -1 for i in range(N)}
    for i in range(N):
        if D[C[i]] == -1:
            D[C[i]] = i
        else:
            E.append((D[C[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)

    ANS = [0] * Q
    y_list = [0] * (N + 1)
    for e in E:
        if e[2] == -1:
            y_list[e[1]] = 1
        else:
            ans = y_list[0:e[1] + 1].count(1)
            ANS[e[2]] = e[1] - e[0] + 1 - ans

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    E = []

    D = {i: -1 for i in range(1, N + 1)}
    for i in range(N):
        if D[C[i]] == -1:
            D[C[i]] = i
        else:
            E.append((D[C[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)

    ANS = [0] * Q
    y_list = []
    for e in E:
        if e[2] == -1:
            y_list.append(e[1])
            y_list.sort()
        else:
            ans = bisect.bisect_right(y_list, e[1])
            ANS[e[2]] = e[1] - e[0] + 1 - ans

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    E = []

    D = {C[i]: -1 for i in range(N)}
    for i in range(N):
        if D[C[i]] == -1:
            D[C[i]] = i
        else:
            E.append((D[C[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)

    ANS = [0] * Q
    y_list = []
    for e in E:
        if e[2] == -1:
            y_list.append(e[1])
            y_list.sort()
        else:
            ans = bisect.bisect_right(y_list, e[1])
            ANS[e[2]] = e[1] - e[0] + 1 - ans

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    E = []

    D = {C[i]: -1 for i in range(N)}
    for i in range(N):
        if D[C[i]] == -1:
            D[C[i]] = i
        else:
            E.append((D[C[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)

    ANS = [0] * Q
    y_list = []
    for e in E:
        if e[2] == -1:
            y_list.append(e[1])
            y_list.sort()
        else:
            ans = bisect.bisect_right(y_list, e[1])
            ANS[e[2]] = e[1] - e[0] + 1 - ans

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    E = []

    D = {C[i]: -1 for i in range(N)}
    for i in range(N):
        if D[C[i]] == -1:
            D[C[i]] = i
        else:
            E.append((D[C[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)

    ANS = [0] * Q
    y_list = []
    for e in E:
        if e[2] == -1:
            y_list.append(e[1])
        else:
            y_list.sort()
            ans = bisect.bisect_right(y_list, e[1])
            ANS[e[2]] = e[1] - e[0] + 1 - ans

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    L = [0] * Q
    R = [0] * Q
    E = []

    D = {C[i]: -1 for i in range(N)}
    for i in range(N):
        if D[C[i]] == -1:
            D[C[i]] = i
        else:
            E.append((D[C[i]], i, -1))
            D[C[i]] = i

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

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

    ANS = [0] * Q
    y_list = []
    for e in E:
        if e[2] == -1:
            y_list.append(e[1])
            y_list.sort()
        else:
            ans = bisect.bisect_right(y_list, e[1])
            ANS[e[2]] = e[1] - e[0] + 1 - ans

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

data = [0]*(N+1)
def add(k, x):
    while k <= N:
        data[k] += x
        k += k & -k

def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s

# 二分探索
N0 = 2**(N-1).bit_length()
def lower_bound(x):
    w = i = 0
    k = N0
    while k:
        if i+k <= N and w + data[i+k] <= x:
            w += data[i+k]
            i += k
        k >>= 1
    return i+1

c=[int(i) for i in input().split()]
Q=[]
for i in range(q):
    l,r=map(int,input().split())
    Q.append((l,r,i))
Ans=[0 for i in range(q)]
F=[-1 for i in range(5*10**5+1)]
Q.sort(key=lambda x:x[1])
Q.append((10**6,10**6,10**6))

for i in range(n):
    add(i+1,1)

quen=0
for i in range(n):
    if F[c[i]]>=0:
        add(F[c[i]]+1,-1)
    F[c[i]]=i
    while Q[quen][1]==i+1:
        Ans[Q[quen][2]]=-get(Q[quen][0]-1)+get(Q[quen][1])
        #print(Tre.query(Q[quen][0]-1,Q[quen][1]))
        quen+=1

for ele in Ans:
    print(ele)

Submission status: Time Limit Exceeded

Solution code:

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

#####ide_ele　単位元#####
ide_ele = 0
#################



class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

#appapp[i]=SegTree(app[i], segfunc, ide_ele) #こんなかんじ

n,q=map(int,input().split())
c=[int(i) for i in input().split()]
Q=[]
for i in range(q):
    l,r=map(int,input().split())
    Q.append((l,r,i))
Ans=[0 for i in range(q)]
Tre=SegTree([1 for i in range(n+1)],segfunc,ide_ele)
F=[-1 for i in range(5*10**5+1)]
Q.sort(key=lambda x:x[1])
Q.append((10**6,10**6,10**6))

quen=0
for i in range(n):
    if F[c[i]]>=0:
        Tre.update(F[c[i]],0)
    F[c[i]]=i
    while Q[quen][1]==i+1:
        Ans[Q[quen][2]]=Tre.query(Q[quen][0]-1,Q[quen][1])
        #print(Tre.query(Q[quen][0]-1,Q[quen][1]))
        quen+=1

for ele in Ans:
    print(ele)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import sys


def add(arr, i, size):
    while i < size:
        arr[i] += 1
        i += i & -i


def sub(arr, i, size):
    while i < size:
        arr[i] -= 1
        i += i & -i


def bit_sum(arr, a, b):
    s = 0
    i = b
    while i > 0:
        s += arr[i]
        i -= i & -i
    i = a - 1
    while i > 0:
        s -= arr[i]
        i -= i & -i
    return s


def read():
    return sys.stdin.readline().rstrip()


def main():
    n, q = map(int, read().split())
    c = [int(i) - 1 for i in read().split()]
    queries = [(0, 0, 0) for _ in range(q)]
    for i in range(q):
        l, r = map(int, read().split())
        queries[i] = (i, l, r)
    queries = iter(sorted(queries, key=itemgetter(2)))
    last = [0] * n
    bit = [0] * (n + 1)
    ans = [-1] * q
    k, l, r = next(queries)
    for i in range(n):
        ci = c[i]
        li = last[ci]
        if li > 0:
            sub(bit, li, n + 1)
        last[ci] = i + 1
        add(bit, i + 1, n + 1)
        while i + 1 == r:
            ans[k] = bit_sum(bit, l, r)
            try:
                k, l, r = next(queries)
            except StopIteration:
                print(*ans, sep="\n")
                return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
N, Q = map(int, input().split())
C = list(map(int, input().split()))
L = [0] * Q
R = [0] * Q
E = []

D = {C[i]: -1 for i in range(N)}
for i in range(N):
    if D[C[i]] == -1:
        D[C[i]] = i
    else:
        E.append((D[C[i]], i, -1))
        D[C[i]] = i

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

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

ANS = [0] * Q
y_list = []
for e in E:
    if e[2] == -1:
        y_list.append(e[1])
        y_list.sort()
    else:
        ans = bisect.bisect_right(y_list, e[1])
        ANS[e[2]] = e[1] - e[0] + 1 - ans

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

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import sys


class BIT:
    def __init__(self, size: int):
        self.size = size + 1
        self.array = [0] * self.size

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

    def sub(self, i):
        while i < self.size:
            self.array[i] -= 1
            i += i & -i

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


def read():
    return sys.stdin.readline().rstrip()


def main():
    n, q = map(int, read().split())
    c = [int(i) - 1 for i in read().split()]
    queries = [(0, 0, 0) for _ in range(q)]
    for i in range(q):
        l, r = map(int, read().split())
        queries[i] = (i, l, r)
    queries = iter(sorted(queries, key=itemgetter(2)))
    last = [0] * n
    bit = BIT(n)
    ans = [-1] * q
    k, l, r = next(queries)
    for i in range(n):
        ci = c[i]
        li = last[ci]
        if li > 0:
            bit.sub(li)
        last[ci] = i + 1
        bit.add(i + 1)
        while i + 1 == r:
            ans[k] = bit.sum(l, r)
            try:
                k, l, r = next(queries)
            except StopIteration:
                print(*ans, sep="\n")
                return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import sys


class BIT:
    def __init__(self, size: int):
        self.size = size + 1
        self.array = [0] * self.size

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

    def sub(self, i):
        while i < self.size:
            self.array[i] -= 1
            i += i & -i

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


def read():
    return sys.stdin.readline().rstrip()


def main():
    n, q = map(int, read().split())
    c = [int(i) - 1 for i in read().split()]
    queries = [(0, 0, 0) for _ in range(q)]
    for i in range(q):
        l, r = map(int, read().split())
        queries[i] = (i, l, r)
    queries = iter(sorted(queries, key=itemgetter(2)))
    last = [0] * n
    bit = BIT(n)
    ans = [-1] * q
    k, l, r = next(queries)
    for i in range(n):
        ci = c[i]
        li = last[ci]
        if li > 0:
            bit.sub(li)
        last[ci] = i + 1
        bit.add(i + 1)
        while i + 1 == r:
            ans[k] = bit.sum(l, r)
            try:
                k, l, r = next(queries)
            except StopIteration:
                break
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()