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: Wrong Answer

Solution code:
class segtree:
 
    def __init__(self, n, identity):
        # identityは初期値
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2 ** (len(nb) - 1)
        else:
            self.num_end_leaves = 2 ** (len(nb))
 
        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity
 
    def update(self, x, val):
        actual_x = x + self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0:
            actual_x = actual_x // 2
            self.array[actual_x] = self.array[actual_x * 2] + self.array[actual_x * 2 + 1]
 
    def get(self, q_left, q_right, arr_ind=1, leaf_left=0, depth=0):
        width_of_floor = self.num_end_leaves // (2 ** depth)
        leaf_right = leaf_left + width_of_floor - 1
 
        if leaf_left > q_right or leaf_right < q_left:
            return self.identity
 
        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]
 
        else:
            val_l = self.get(q_left, q_right, 2 * arr_ind, leaf_left, depth + 1)
            val_r = self.get(q_left, q_right, 2 * arr_ind + 1, leaf_left + width_of_floor // 2, depth + 1)
            return val_l + val_r
 
N, Q = map(int, input().split())
A = list(map(int, input().split()))
T = {}
s_tree = segtree(N + 1, 0)
for i in range(N):
    if A[i] not in T:
        s_tree.update(i+1, 1)
        T[A[i]] = [i+1]
    else:
        T[A[i]].append(i+1)
Next = [i for i in range(N+1)]
 
for k, v in T.items():
    for j in range(len(v)-1):
        Next[v[j]] = v[j+1]
 
Ans = [0]*Q
K = []
for i in range(Q):
    l, r = map(int, input().split())
    K.append([l, r, i])
 
K = sorted(K, key=lambda x: x[0])

Submission status: Wrong Answer

Solution code:
class segtree:

    def __init__(self, n, identity):
        # identityは初期値
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2 ** (len(nb) - 1)
        else:
            self.num_end_leaves = 2 ** (len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity

    def update(self, x, val):
        actual_x = x + self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0:
            actual_x = actual_x // 2
            self.array[actual_x] = self.array[actual_x * 2] + self.array[actual_x * 2 + 1]

    def get(self, q_left, q_right, arr_ind=1, leaf_left=0, depth=0):
        width_of_floor = self.num_end_leaves // (2 ** depth)
        leaf_right = leaf_left + width_of_floor - 1

        if leaf_left > q_right or leaf_right < q_left:
            return self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left, q_right, 2 * arr_ind, leaf_left, depth + 1)
            val_r = self.get(q_left, q_right, 2 * arr_ind + 1, leaf_left + width_of_floor // 2, depth + 1)
            return val_l + val_r

N, Q = map(int, input().split())
A = list(map(int, input().split()))
T = {}
s_tree = segtree(N + 1, 0)
for i in range(N):
    if A[i] not in T:
        s_tree.update(i+1, 1)
        T[A[i]] = [i+1]
    else:
        T[A[i]].append(i+1)
Next = [i for i in range(N+1)]

for k, v in T.items():
    for j in range(len(v)-1):
        Next[v[j]] = v[j+1]

Ans = [0]*Q
K = {}
for i in range(Q):
    l, r = map(int, input().split())
    if l not in K:
        K[l] = [[r, i]]
    else:
        K[l].append([r, i])

print(1)

Submission status: Wrong Answer

Solution code:
class segtree:

    def __init__(self, n, identity):
        # identityは初期値
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2 ** (len(nb) - 1)
        else:
            self.num_end_leaves = 2 ** (len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity

    def update(self, x, val):
        actual_x = x + self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0:
            actual_x = actual_x // 2
            self.array[actual_x] = self.array[actual_x * 2] + self.array[actual_x * 2 + 1]

    def get(self, q_left, q_right, arr_ind=1, leaf_left=0, depth=0):
        width_of_floor = self.num_end_leaves // (2 ** depth)
        leaf_right = leaf_left + width_of_floor - 1

        if leaf_left > q_right or leaf_right < q_left:
            return self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left, q_right, 2 * arr_ind, leaf_left, depth + 1)
            val_r = self.get(q_left, q_right, 2 * arr_ind + 1, leaf_left + width_of_floor // 2, depth + 1)
            return val_l + val_r

N, Q = map(int, input().split())
A = list(map(int, input().split()))
T = {}
s_tree = segtree(N + 1, 0)
for i in range(N):
    if A[i] not in T:
        s_tree.update(i+1, 1)
        T[A[i]] = [i+1]
    else:
        T[A[i]].append(i+1)
Next = [i for i in range(N+1)]

for k, v in T.items():
    print(k, v)
    for j in range(len(v)-1):
        Next[v[j]] = v[j+1]

Ans = [0]*Q
K = []
for i in range(Q):
    l, r = map(int, input().split())
    K.append([l, r, i])
K.sort()
t = 0

Submission status: Wrong Answer

Solution code:
class segtree:
 
    def __init__(self, n, identity):
        # identityは初期値
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2 ** (len(nb) - 1)
        else:
            self.num_end_leaves = 2 ** (len(nb))
 
        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity
 
    def update(self, x, val):
        actual_x = x + self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0:
            actual_x = actual_x // 2
            self.array[actual_x] = self.array[actual_x * 2] + self.array[actual_x * 2 + 1]
 
    def get(self, q_left, q_right, arr_ind=1, leaf_left=0, depth=0):
        width_of_floor = self.num_end_leaves // (2 ** depth)
        leaf_right = leaf_left + width_of_floor - 1
 
        if leaf_left > q_right or leaf_right < q_left:
            return self.identity
 
        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]
 
        else:
            val_l = self.get(q_left, q_right, 2 * arr_ind, leaf_left, depth + 1)
            val_r = self.get(q_left, q_right, 2 * arr_ind + 1, leaf_left + width_of_floor // 2, depth + 1)
            return val_l + val_r
 
N, Q = map(int, input().split())
A = list(map(int, input().split()))
T = {}
s_tree = segtree(N + 1, 0)
for i in range(N):
    if A[i] not in T:
        s_tree.update(i+1, 1)
        T[A[i]] = [i+1]
    else:
        T[A[i]].append(i+1)
Next = [i for i in range(N+1)]
for k, v in T.items():
    for j in range(len(v)-1):
        Next[v[j]] = v[j+1]

Submission status: Wrong Answer

Solution code:
class segtree:

    def __init__(self, n, identity):
        # identityは初期値
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2 ** (len(nb) - 1)
        else:
            self.num_end_leaves = 2 ** (len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity

    def update(self, x, val):
        actual_x = x + self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0:
            actual_x = actual_x // 2
            self.array[actual_x] = self.array[actual_x * 2] + self.array[actual_x * 2 + 1]

    def get(self, q_left, q_right, arr_ind=1, leaf_left=0, depth=0):
        width_of_floor = self.num_end_leaves // (2 ** depth)
        leaf_right = leaf_left + width_of_floor - 1

        if leaf_left > q_right or leaf_right < q_left:
            return self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left, q_right, 2 * arr_ind, leaf_left, depth + 1)
            val_r = self.get(q_left, q_right, 2 * arr_ind + 1, leaf_left + width_of_floor // 2, depth + 1)
            return val_l + val_r

N, Q = map(int, input().split())
A = list(map(int, input().split()))
T = {}
s_tree = segtree(N + 1, 0)
for i in range(N):
    if A[i] not in T:
        s_tree.update(i+1, 1)
        T[A[i]] = [i+1]
    else:
        T[A[i]].append(i+1)
print(1)

Submission status: Wrong Answer

Solution code:
class segtree:

    def __init__(self, n, identity):
        # identityは初期値
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2 ** (len(nb) - 1)
        else:
            self.num_end_leaves = 2 ** (len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity

    def update(self, x, val):
        actual_x = x + self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0:
            actual_x = actual_x // 2
            self.array[actual_x] = self.array[actual_x * 2] + self.array[actual_x * 2 + 1]

    def get(self, q_left, q_right, arr_ind=1, leaf_left=0, depth=0):
        width_of_floor = self.num_end_leaves // (2 ** depth)
        leaf_right = leaf_left + width_of_floor - 1

        if leaf_left > q_right or leaf_right < q_left:
            return self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left, q_right, 2 * arr_ind, leaf_left, depth + 1)
            val_r = self.get(q_left, q_right, 2 * arr_ind + 1, leaf_left + width_of_floor // 2, depth + 1)
            return val_l + val_r

N, Q = map(int, input().split())
A = list(map(int, input().split()))
T = {}
s_tree = segtree(N + 1, 0)
for i in range(N):
    if A[i] not in T:
        s_tree.update(i+1, 1)
        T[A[i]] = [i+1]
    else:
        T[A[i]].append(i+1)
Next = [i for i in range(N+1)]
for k, v in T.items():
    for j in range(len(v)-1):
        Next[v[j]] = v[j+1]

Ans = [0]*Q
K = []
for i in range(Q):
    l, r = map(int, input().split())
    K.append([l, r, i])
K.sort()
t = 0
print(1)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from math import ceil ,log2
class SegT:
    def __init__(self,num_factor:int,ini:int):
        self.num_factor = num_factor
        self.length = 2*2**ceil(log2(num_factor)) - 1
        self.INT_MAX = ini
        self.tree = [self.INT_MAX]*self.length
        return

    def update(self,index,value):#0-indexed
        index += self.length // 2
        self.tree[index] = value
        while index > 0:
            index = (index - 1) // 2
            self.tree[index] = self.tree[index*2 + 1] +  self.tree[index*2 + 2]
        return

    def queryA(self,left: int, right: int , node : int, node_left :int, node_right :int)->int:#[left, right]
        if node_right < left or right < node_left:
            return self.INT_MAX
        elif left <= node_left and node_right <= right:
            return self.tree[node]
        tmp1 = self.queryA(left , right , node*2 + 1, node_left, (node_right + node_left) // 2)
        tmp2 = self.queryA(left , right , node*2 + 2, (node_right + node_left) // 2 + 1, node_right )
        return tmp1  + tmp2

    def query(self,left: int, right: int):
        return self.queryA(left,right,0,0,self.length // 2)


def main():
    n,q = map(int,input().split())
    C = list(map(int,input().split()))
    LR = [list(map(int,input().split())) + [i] for i in range(q)]

    LR.sort(key = itemgetter(0))
    LR.sort(key = itemgetter(1))
    dic = {0:1}
    index = 0
    Ans = [0]*q
    tree  = SegT(n,0)
    for l,r,j in LR:
        while index < r-1:
            index += 1
            if C[index] in dic:
                tree.update(dic[C[index]],0)
            dic[C[index]] = index
            tree.update(index,1)
        Ans[j] = tree.query(l-1,r-1)
    print(*Ans,sep="\n")
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from math import ceil ,log2
class SegT:
    def __init__(self,num_factor:int,ini:int):
        self.num_factor = num_factor
        self.length = 2*2**ceil(log2(num_factor)) - 1
        self.INT_MAX = ini
        self.tree = [self.INT_MAX]*self.length
        return

    def update(self,index,value):#0-indexed
        index += self.length // 2
        self.tree[index] = value
        while index > 0:
            index = (index - 1) // 2
            self.tree[index] = self.tree[index*2 + 1] +  self.tree[index*2 + 2]
        return

    def queryA(self,left: int, right: int , node : int, node_left :int, node_right :int)->int:#[left, right]
        if node_right < left or right < node_left:
            return self.INT_MAX
        elif left <= node_left and node_right <= right:
            return self.tree[node]
        tmp1 = self.queryA(left , right , node*2 + 1, node_left, (node_right + node_left) // 2)
        tmp2 = self.queryA(left , right , node*2 + 2, (node_right + node_left) // 2 + 1, node_right )
        return tmp1  + tmp2

    def query(self,left: int, right: int):
        return self.queryA(left,right,0,0,self.length // 2)


def main():
    n,q = map(int,input().split())
    C = list(map(int,input().split()))
    LR = [list(map(int,input().split())) + [i] for i in range(q)]

    LR.sort(key = itemgetter(0))
    LR.sort(key = itemgetter(1))
    dic = {}
    index = 0
    Ans = [0]*q
    tree  = SegT(n,0)
    for l,r,j in LR:
        while index < r-1:
            index += 1
            if C[index] in dic:
                tree.update(dic[C[index]],0)
            dic[C[index]] = index
            tree.update(index,1)
        Ans[j] = tree.query(l-1,r-1)
    print(*Ans,sep="\n")
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

if __name__ == '__main__':
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    LR = []
    for i in range(Q):
        LR.append(tuple(map(int, input().split())))
    ACC = []
    ACC.append({})
    hash = {} 
    for c in C:
        if c in hash:
            hash[c] += 1
        else:
            hash[c] = 1 
        ACC.append(deepcopy(hash))
    for l, r in LR:
        head = ACC[l-1]
        tail = ACC[r]
        delta = r - (l - 1)  
        kind_cnt = len(tail)
        for t_key, t_value in tail.items():
            if t_key in head:
                if head[t_key] == t_value:
                    kind_cnt -= 1
                    delta -= 1
            if delta == 0:
                break
        print(kind_cnt)

Submission status: Wrong Answer

Solution code:
from sys import stdin


def bit_add(bit, i, x):
    i += 1
    n = len(bit)
    while i <= n:
        bit[i - 1] += x
        i += i & -i


def bit_sum(bit, i):
    result = 0
    i += 1
    while i > 0:
        result += bit[i - 1]
        i -= i & -i
    return result


def bit_query(bit, start, stop):
    return bit_sum(bit, stop - 1) - bit_sum(bit, start - 1)


def main():
    readline = stdin.readline

    N, Q = map(int, readline().split())
    c = list(map(int, readline().split()))

    lr = [None] * Q
    for i in range(Q):
        l, r = map(int, readline().split())
        lr[i] = (r - 1, l - 1, i)
    lr.sort()

    result = [None] * Q

    bit = [0] * N
    mr = {}
    k = 0
    for i in range(N):
        if c[i] in mr:
            bit_add(bit, mr[c[i]], -1)
        bit_add(bit, i, 1)
        mr[c[i]] = i
        while k < Q and lr[k][0] == i:
            result[lr[k][2]] = bit_query(bit, lr[k][1], lr[k][0] + 1)
            k += 1

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

Submission status: Wrong Answer

Solution code:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

from sys import stdin
input = lambda: stdin.readline().strip()

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

    lis = [[] for _ in range(n + 1)]
    for i, ci in enumerate(c):
        lis[ci].append(i)

    st = SegmentTree(n, f=lambda x, y: x + y, default=0)
    for i in range(n+1):
        if len(lis[i]) > 0:
            st.update(lis[i].pop(-1), 1)

    query = [0] * q
    ans = [-1] * q
    for lap in range(q):
        l, r = map(int, input().split())
        query[lap] = (r, l-1, lap)
    
    query.sort(reverse=True)
    '''
    now_r = n
    for ind, (r, l, lap) in enumerate(query):
        while now_r > r:
            now_r -= 1
            st.update(now_r, 0) # delete
            if len(lis[c[now_r]]) > 0:
                st.update(lis[c[now_r]].pop(-1), 1) # add
        ans[lap] = st.query(l, r)
    
    for i in ans:
        print(i)
    '''
main()

Submission status: Wrong Answer

Solution code:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

from sys import stdin
input = lambda: stdin.readline().strip()

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

    lis = [[] for _ in range(n + 1)]
    for i, ci in enumerate(c):
        lis[ci].append(i)

    st = SegmentTree(n, f=lambda x, y: x + y, default=0)
    for i in range(n+1):
        if len(lis[i]) > 0:
            st.update(lis[i].pop(-1), 1)

    query = [0] * q
    ans = [-1] * q
    for lap in range(q):
        l, r = map(int, input().split())
        query[lap] = (l-1, r, lap)
    
    query.sort(reverse=True, key=lambda x: x[1])
    '''
    now_r = n
    for ind, (l, r, lap) in enumerate(query):
        while now_r > r:
            now_r -= 1
            st.update(now_r, 0) # delete
            if len(lis[c[now_r]]) > 0:
                st.update(lis[c[now_r]].pop(-1), 1) # add
        ans[lap] = st.query(l, r)
    
    for i in ans:
        print(i)
    '''
main()

Submission status: Wrong Answer

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


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


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

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

# lr.sort(key=lambda x: x[1])
# print("lr", lr)
rightest = [-1] * (N + 1)
current_q = 0
bit = Bit(N)
ans = [0] * Q

for i in range(N):
    if rightest[c[i]] != -1:
        bit.add(rightest[c[i]] + 1, -1)
    rightest[c[i]] = i
    bit.add(i + 1, 1)
    # print(bit.tree)

for i in range(Q):
    ans[i] = bit.sum(lr[i][1]) - bit.sum(lr[i][0] - 1)

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

Submission status: Wrong Answer

Solution code:
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)

N, Q = map(int, input().split())
Cs = [0] + list(map(int, input().split()))

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

ans = [-1]*Q
dic = {}
b = 1
bt = BIT(N)

for i,l,r in Qs:
  st = set()
  for j in range(b,r+1):
    if Cs[j] in dic:
      bt.add(dic[Cs[j]],-1)
    st.add(Cs[j])
    dic[Cs[j]] = j
  for s in st:
    bt.add(dic[Cs[j]], 1)
  ans[i] = bt.get(l-1,r)
  b = r + 1
  
for i in range(Q):
  print(ans[i])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
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
 
n,q = list(map(int,input().split()))
ball = list(map(int,input().split()))
 
h = Bit(n+1)

L_most = {}
#J = [[] for _ in range(max(ball)+2)]
L = {}
jump = {}
on = set()

for i,b in enumerate(ball):
  if b not in L_most:
    L_most[b]=i
    h.add(i+1,1)
    on.add(i+1)
  #J[b].append(i)
  if b in L:
    jump[L[b]]=i+1
  L[b] = i+1
  
print(jump)
  
#for i in range(max(ball)+2):
#  for j in range(len(J[i])):
#    if j+1<len(J[i]):
#      jump[J[i][j]+1] = J[i][j+1]+1

Q = []
 
for _ in range(q):
  l,r = list(map(int,input().split()))
  Q.append((l,r))
  
LOO = list(Q)
Q.sort(key=lambda x:x[0])

c = 1
ans = {}
#print(on)

for l,r in Q:
  for i in range(c,l):
    if i in on:
      on.remove(i)
      h.add(i,-1)
      if i in jump:
        dest = jump[i]
        h.add(dest,1)
        on.add(dest)

  tmp = h.sum(r)- h.sum(l-1)
  ans[(l,r)] = tmp
  c = l

for q in LOO:
  print(ans[q])

Submission status: Wrong Answer

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

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

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

h = Bit(500000+1)
L_most = {}

Q = []

for _ in range(q):
  l,r = list(map(int,input().split()))
  l-=1
  r-=1
  Q.append((l,r))
  
Q.sort(key=lambda x:x[1])
print(Q)

Submission status: Wrong Answer

Solution code:
class BIT():
    def __init__(self, N):
        self.data0 = [0]*(N+1)
        self.data1 = [0]*(N+1)
    
    # 区間[l, r)に x を加算
    def _add(self, data, k, x):
        while k <= N:
            data[k] += x
            k += k & -k
    
    def add(self, l, r, x):
        l += 1
        r += 1
        self._add(self.data0, l, -x*(l-1))
        self._add(self.data0, r, x*(r-1))
        self._add(self.data1, l, x)
        self._add(self.data1, r, -x)

    # 区間[l, r)の和を求める
    def _get(self, data, k):
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s
    
    def query(self, l, r):
        l += 1
        r += 1
        return self._get(self.data1, r-1) * (r-1) + self._get(self.data0, r-1) - self._get(self.data1, l-1) * (l-1) - self._get(self.data0, l-1)


N, Q = map(int, input().split())
*c, = map(int, input().split())
tree2 = BIT(N+1)
m = [tuple(map(int, input().split()))+(i,) for i in range(Q)]
m.sort(key=lambda x:x[1])

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

for l, r, k in m:
    if right!=r:
        for i in range(right, r):
            if pos[c[i]] != -1:
                tree2.add(pos[c[i]], pos[c[i]]+1, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, i+2, 1)
    ans[k] = tree2.query(l, r+1)
    right = r

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

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)

n,q = inpl()
c = inpl()
de = {}
queries = []
for i in range(q):
    a,b = inpl()
    de[(a,b)] = i
    queries.append((a,b))
res = [-1] * q
d = [-1] * n
sec = []
for i,x in enumerate(c):
    if d[x-1] != -1:
        sec.append([d[x-1], i+1])
    d[x-1] = i+1
sec_ln = len(sec)
sec.sort(reverse = True)
queries.sort(reverse = True)
# print(queries)
bit = BIT(n)
sec_ind = que_ind = 0
for i in range(n+1)[::-1]:
    while sec_ind < sec_ln and sec[sec_ind][0] >= i:
        x = sec[sec_ind][1]
        bit.add(x,1)
        sec_ind += 1
    
    while que_ind < q and queries[que_ind][0] >= i:
        _,x = queries[que_ind]
        ind = de[(_,x)]
        res[ind] = x-_+1 - bit.get(1,x)
        que_ind += 1
print(*res)

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit
from collections import Counter
from collections import defaultdict
from collections import deque
from pprint import pprint
from heapq import heapify
from heapq import heappop
from heapq import heappush
from time import time
setrecursionlimit(10**9)
mod=10**9+7
inf=10**18

class Bit:
    def __init__(self,size):
        self.size=size+1
        self.seg=[0]*self.size
    def add(self,idx,val):
        idx+=1
        while idx<self.size:
            self.seg[idx]+=val
            idx+=idx&(-idx)
    def sum(self,idx):
        idx+=1
        res=0
        while idx>0:
            res+=self.seg[idx]
            idx-=idx&(-idx)
        return res

n,q=[int(x) for x in input().split()]
c=[int(x)-1 for x in input().split()]
lri=[]
# O(n)
for i in range(q):
    l,r=[int(x)-1 for x in input().split()]
    lri.append((l,r,i))

rr=defaultdict()
bfr=[-1]*n
# O(n)
for i in range(n):
    if bfr[c[i]]!=-1:
        rr[bfr[c[i]]]=i
    bfr[c[i]]=i

bit=Bit(n)

ans=[-1]*q
# O(logn)
lri.sort(reverse=True)
lri=deque(lri)
lft,rgt,idx=lri.popleft()
# O(n)
for lt in range(n-1,-1,-1):
    # O(logn)
    if rr.get(lt) is not None:
        bit.add(rr.get(lt),1)
    # O(>n)
    while lft==lt:
        # O(logn)
        ans[idx]=rgt-lft+1-(bit.sum(rgt))
        if len(lri)==0:
            break
        lft,rgt,idx=lri.popleft()
    if len(lri)==0:
        break
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from collections import defaultdict
from collections import deque
from heapq import heapify
from heapq import heappop
from heapq import heappush
from pprint import pprint
from sys import setrecursionlimit
from sys import stdin
from time import time

def main():
    input=stdin.readline
    class Bit:
        def __init__(self,size):
            self.size=size+1
            self.seg=[0]*self.size
            self.cache=defaultdict()
        def add(self,idx,val):
            idx+=1
            while idx<self.size:
                self.seg[idx]+=val
                idx+=idx&(-idx)
        def sum(self,idx):
            cidx=idx
            cval=self.cache.get(cidx)
            if cval is not None:
                return cval
            idx+=1
            res=0
            while idx>0:
                res+=self.seg[idx]
                idx-=idx&(-idx)
            self.cache[cidx]=res
            return res

    n,q=[int(x) for x in input().split()]
    c=[int(x)-1 for x in input().split()]
    lri=[]
    # O(n)
    for i in range(q):
        l,r=[int(x)-1 for x in input().split()]
        lri.append((l,r,i))
    
    rr=defaultdict()
    bfr=[-1]*n
    # O(n)
    for i in range(n):
        if bfr[c[i]]!=-1:
            rr[bfr[c[i]]]=i
        bfr[c[i]]=i
    
    bit=Bit(n)
    
    ans=[-1]*q
    # O(logn)
    lri.sort(reverse=True)
    lri=deque(lri)
    lft,rgt,idx=lri.popleft()
    # O(n)
    for lt in range(n-1,-1,-1):
        # O(logn)
        if rr.get(lt) is not None:
            bit.add(rr.get(lt),1)
        # O(>n)
        while lft==lt:
            # O(logn)
            ans[idx]=rgt-lft+1-(bit.sum(rgt))
            if len(lri)==0:
                break
            lft,rgt,idx=lri.popleft()
    for i in ans:
        print(i)
main()