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:
import sys
from operator import itemgetter
 
sys.setrecursionlimit(500005)
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()
 
n, q = na()
a = na()

lasts = [-1] * (n+1)
rs = []
for i in range(n):
  if lasts[a[i]] != -1:
    rs.append((lasts[a[i]], i))
  lasts[a[i]] = i
rs.sort(key=itemgetter(0))

qs = []
for i in range(q):
  u = na()
  qs.append((u[0]-1, u[1]-1, i))
qs.sort(key=itemgetter(0))

def addfenwick(ft, i, v):
  if v==0 or i<0: return
  i+=1
  while i<len(ft):
    ft[i] += v
    i += i&-i

def sumfenwick(ft, i):
  s = 0
  i += 1
  while i>0:
    s += ft[i]
    i -= i&-1
  return s

ft = [0] * (n+10)
ans = [0] * q
p = len(rs)-1
for q in qs[::-1]:
  while p>=0 and rs[p][0] >= q[0]:
    addfenwick(ft, rs[p][1], 1)
    p -= 1
  ans[q[2]] = q[1]-q[0]+1-sumfenwick(ft, q[1])

for v in ans: print(v)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

lasts = [-1] * (n+1)
rs = []
for i in range(n):
  if lasts[a[i]] != -1:
    rs.append((lasts[a[i]], i))
  lasts[a[i]] = i
rs.sort(key=itemgetter(0))

qs = []
for i in range(q):
  u = list(map(int,input().split()))
  qs.append((u[0]-1, u[1]-1, i))
qs.sort(key=itemgetter(0))

def addfenwick(ft, i, v):
  if v==0 or i<0: return
  i+=1
  while i<len(ft):
    ft[i] += v
    i += i&-i

def sumfenwick(ft, i):
  s = 0
  i += 1
  while i>0:
    s += ft[i]
    i -= i&-1
  return s

ft = [0] * (n+10)
ans = [0] * q
p = len(rs)-1
for q in qs[::-1]:
  while p>=0 and rs[p][0] >= q[0]:
    addfenwick(ft, rs[p][1], 1)
    p -= 1
  ans[q[2]] = q[1]-q[0]+1-sumfenwick(ft, q[1])

for v in ans: print(v)

Submission status: Wrong Answer

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

lasts = [-1] * (n+1)
rs = []
for i in range(n):
  if lasts[a[i]] != -1:
    rs.append((lasts[a[i]], i))
  lasts[a[i]] = i
rs.sort(key=lambda x: x[0])

qs = []
for i in range(q):
  u = list(map(int,input().split()))
  qs.append((u[0]-1, u[1]-1, i))
qs.sort(key=lambda x: x[0])

def addfenwick(ft, i, v):
  if v==0 or i<0: return
  i+=1
  while i<len(ft):
    ft[i] += v
    i += i&-i

def sumfenwick(ft, i):
  s = 0
  i += 1
  while i>0:
    s += ft[i]
    i -= i&-1
  return s

ft = [0] * (n+10)
ans = [0] * q
p = len(rs)-1
for q in qs[::-1]:
  while p>=0 and rs[p][0] >= q[0]:
    addfenwick(ft, rs[p][1], 1)
    p -= 1
  ans[q[2]] = q[1]-q[0]+1-sumfenwick(ft, q[1])

for v in ans: print(v)

Submission status: Wrong Answer

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

lasts = [-1] * (n+1)
rs = []
for i in range(n):
  if lasts[a[i]] != -1:
    rs.append((lasts[a[i]], i))
  lasts[a[i]] = i
rs.sort()

qs = []
for i in range(q):
  u = list(map(int,input().split()))
  qs.append((u[0]-1, u[1]-1, i))
qs.sort()

def addfenwick(ft, i, v):
  if v==0 or i<0: return
  i+=1
  while i<len(ft):
    ft[i] += v
    i += i&-i

def sumfenwick(ft, i):
  s = 0
  i += 1
  while i>0:
    s += ft[i]
    i -= i&-1
  return s

ft = [0] * (n+10)
ans = [0] * q
p = len(rs)-1
for q in qs[::-1]:
  while p>=0 and rs[p][0] >= q[0]:
    addfenwick(ft, rs[p][1], 1)
    p -= 1
  ans[q[2]] = q[1]-q[0]+1-sumfenwick(ft, q[1])

for v in ans: print(v)

Submission status: Wrong Answer

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


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def summarize(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.summarize(j) - self.summarize(i)


def main():
    n, q = map(int, input().split())
    c = [int(x) for x in input().split()]
    
    judge = dict()
    key = [-1]*n
    for i in range(n):
        if c[i] in judge:
            key[i] = judge[c[i]]
        judge[c[i]] = i
    
    query = [(r, l, i) for i, (l, r) in enumerate([[int(x) for x in input().split()] for _ in range(q)])]
    #query.sort()
    bit = BIT(n)
    ans = [0]*q
    index = 0
    count = 0
    for i in range(n):
        if key[i] != -1:
            count += 1
            bit.add(key[i]+1, 1)
        while True:
            if index == q:
                break
            r, l, c = query[index]
            if r == i+1:
                ans[c] = r-l+1-count+bit.summarize(l-1)
                index += 1
            else:
                break
        if index == q:
            break

    for v in ans:
        print(v)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
buf = sys.stdin.buffer
input = buf.readline
class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    def add(self, i, x):
        n, tree = self.n, self.tree
        while i <= n:
            tree[i] += x
            i += i & -i
    def sum(self, i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
def main():
    n, q = map(int, input().split())
    res = [0] * q
    *c, = map(int, input().split())
    q = [(i, l, r) for i, (l, r) in enumerate(zip(*[map(int, buf.read().split())] * 2))]
    #q.sort(key=itemgetter(2))
    bit = BIT(n + 2)
    add, sum = bit.add, bit.sum
    b = [1] * (n + 1)
    j = 1
    for i, l, r in q:
        while j <= r:
            d = c[j - 1]
            j += 1
            k = b[d]
            b[d] = j
            add(k + 1, 1)
            add(j + 1, -1)
        res[i] = sum(l + 1)
    print(' '.join(map(str, res)))
main()

Submission status: Wrong Answer

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


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def summarize(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.summarize(j) - self.summarize(i)


def main():
    n, q = map(int, input().split())
    c = [int(x) for x in input().split()]
    
    judge = dict()
    key = [-1]*n
    for i in range(n):
        if c[i] in judge:
            key[i] = judge[c[i]]
        judge[c[i]] = i
    
    query = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        query[i] = (r-1, l-1, i)
    
    query.sort()
    """
    bit = BIT(n)
    ans = [0]*q
    index = 0
    count = 0
    for i in range(n):
        if key[i] != -1:
            count += 1
            bit.add(key[i]+1, 1)
        while True:
            if index == q:
                break
            r, l, c = query[index]
            if r == i:
                ans[c] = r-l+1-count+bit.summarize(l)
                index += 1
            else:
                break
        if index == q:
            break
    
    for v in ans:
        print(v)
    """
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def summarize(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.summarize(j) - self.summarize(i)


def main():
    n, q = map(int, input().split())
    c = [int(x) for x in input().split()]
    
    judge = dict()
    key = [-1]*n
    for i in range(n):
        if c[i] in judge:
            key[i] = judge[c[i]]
        judge[c[i]] = i
    
    query = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        query[i] = (r-1, l-1, i)
    
    #query.sort()
    
    bit = BIT(n)
    ans = [0]*q
    index = 0
    count = 0
    for i in range(n):
        if key[i] != -1:
            count += 1
            bit.add(key[i]+1, 1)
        while True:
            if index == q:
                break
            r, l, c = query[index]
            if r == i:
                ans[c] = r-l+1-count+bit.summarize(l)
                index += 1
            else:
                break
        if index == q:
            break
    
    for v in ans:
        print(v)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)


def main():
    n, q = map(int, input().split())
    c = [int(x) for x in input().split()]
    
    judge = dict()
    key = [-1]*n
    for i in range(n):
        if c[i] in judge:
            key[i] = judge[c[i]]
        judge[c[i]] = i

    query = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        query[i] = (r, l, i)
    
    query.sort()
    
    bit = BIT(n)
    ans = [0]*q
    index = 0
    count = 0
    while True:
        if index == q or count == n:
            break
        r, l, i = query[index]
        while r > count:
            bit.add(count+1, 1)
            if key[count] != -1:
                bit.add(key[count]+1, -1)
            count += 1
        ans[i] = bit.get_sum(l-1, r)
        index += 1

    for v in ans:
        print(v)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def A(i,x):
 while i<q:t[i]+=x;i+=i&-i
(n,q),c,*z=[[*map(int,t.split())]for t in open(0)]
a=[0]*q
j,*b=t=[0]*9**6
for i in sorted(range(q),key=lambda x:z[x][1]):
 l,r=z[i]
 while j<r:d=c[j];j+=1;A(b[d]+1,1);b[d]=j;A(j+1,-1)
 while l:a[i]+=t[l];l-=l&-l
print(*a)

Submission status: Wrong Answer

Solution code:
def A(i,x):
 while i<n:t[i]+=x;i+=i&-i
(n,q),c,*z=[[*map(int,t.split())]for t in open(0)]
a=[0]*q
j,*b=t=[0]*9**6
for i in sorted(range(q),key=lambda x:z[x][1]):
 l,r=z[i]
 while j<r:d=c[j];j+=1;A(b[d]+1,1);b[d]=j;A(j+1,-1)
 while l:a[i]+=t[l];l-=l&-l
print(*a)

Submission status: Wrong Answer

Solution code:
def A(i,x):
 while~i>~n:t[i]+=x;i+=i&-i
(n,q),c,*z=[[*map(int,t.split())]for t in open(0)]
a=[0]*q
j,*b=t=[0]*(n+2)
for i,(l,r)in sorted(zip(range(q),z),key=lambda x:x[1][1]):
 while j<r:d=c[j];j+=1;A(b[d]+1,1);b[d]=j;A(j+1,-1)
 while l:a[i]+=t[l];l-=l&-l
print(*a)

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
clist=list(map(int,input().split()))

lrlist=[]
rllist=[]
for _ in range(Q):
  l,r=map(int,input().split())
  lrlist.append((l,r))
  rllist.append((r,l))
rllist.sort()
#print(rllist)

#A1～Aiまでの和 O(logN)
def BIT_query(idx):
  res_sum = 0
  while idx > 0:
    res_sum += BIT[idx]
    idx -= idx&(-idx)
  return res_sum
#Ai += x O(logN)
def BIT_update(idx,x):
  while idx <= N:
    BIT[idx] += x
    idx += idx&(-idx)
  return

dic_rpos={}
ans_dic={}

BIT=[0]*(N+1)
BIT_update(1,1)
r0=1
for r,l in rllist:
  if r0<r:
    for i in range(r0+1,r+1):
      c=clist[i-1]
      if c in dic_rpos:
        BIT_update(dic_rpos[c],-1)
      BIT_update(i,1)
      dic_rpos[c]=i
      
  ans=BIT_query(r)-BIT_query(l-1)
  ans_dic[(l,r)]=ans
  
for l,r in lrlist:
  print(ans_dic[(l,r)])

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
clist=list(map(int,input().split()))

lrlist=[]
rllist=[]
for _ in range(Q):
  l,r=map(int,input().split())
  lrlist.append((l,r))
  rllist.append((r,l))
rllist.sort()
#print(rllist)

#A1～Aiまでの和 O(logN)
def BIT_query(idx):
  res_sum = 0
  while idx > 0:
    res_sum += BIT[idx]
    idx -= idx&(-idx)
  return res_sum
#Ai += x O(logN)
def BIT_update(idx,x):
  while idx <= N:
    BIT[idx] += x
    idx += idx&(-idx)
  return

dic_rpos={}
ans_dic={}

BIT=[0]*(N+1)
r0=1
for r,l in rllist:
  if r0<r:
    for i in range(r0,r+1):
      c=clist[i-1]
      if c in dic_rpos:
        BIT_update(dic_rpos[c],-1)
      BIT_update(i,1)
      dic_rpos[c]=i
      
  ans=BIT_query(r)-BIT_query(l-1)
  ans_dic[(l,r)]=ans
  
for l,r in lrlist:
  print(ans_dic[(l,r)])

Submission status: Wrong Answer

Solution code:
from collections import deque
N,Q=map(int, input().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

    # I: idx(base: 1), x: value
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            
    # i<x<=j 
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

query=[]

C=list(map(int, input().split()))
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l,r,i))
query=sorted(query, key=lambda x: -x[1])

state=[-1]*N
seg=BIT(N+1)
ans=[0]*Q

for i in range(N):
    while query and query[-1][1]<i+1:
        l,r,j=query.pop()
        ans[j]=r-l+1-(seg.get(l-1,r))

    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i+1
    else:
        idx=state[c-1]
        seg.add(idx,1)
        state[c-1]=i+1
    while query and query[-1][1]==i:
        lq,rq,j=query.pop()
        ans[j]=rq-lq+1-(seg.get(lq-1,rq))
        #print(lq, rq, seg.get(lq-1,rq))





for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,Q=map(int,input().split())
a=tuple(map(int1,input().split()))
lr=[() for i in range(Q)]
for i in range(Q):
    l,r=map(int1,input().split())
    lr[i]=(l,r,i)
class BIT:
    def __init__(self,n):
        self.num=n
        self.dat=[0]*(self.num+1)
        self.depth=n.bit_length()
    
    def add(self,i,x):
        i+=1
        while i<=self.num:
            self.dat[i]+=x
            i+=i&-i
    
    def sum(self,i):
        i+=1
        s=0
        while i>0:
            s+=self.dat[i]
            i-=i&-i
        return s
    
    def lower_bound(self,x):
        sum_=0
        pos=0
        for i in range(self.depth,-1,-1):
            k=pos+(1<<i)
            if k<=self.num and sum_+self.dat[k]<x:
                sum_+=self.dat[k]
                pos+=1<<i
        return pos, sum_

b=BIT(N)
lastap=[-1]*N
ans=[-1]*Q
l,r,j=lr.pop()
for i,x in enumerate(a):
    if lastap[x]!=-1:
        b.add(lastap[x],-1)
    b.add(i,1)
    lastap[x]=i
    while r==i:
        ans[j]=b.sum(r)-b.sum(l-1)
        if lr:
            l,r,j=lr.pop()
        else:
            l,r,j=-1,-1,-1
print(*ans,sep='\n')

Submission status: Wrong Answer

Solution code:
import numpy as np
from numba import njit, prange

N, Q = map(int, input().split())
C = np.asarray(list(map(int, input().split())))
LR = np.asarray([list(map(int, input().split())) for _ in range(Q)])

@njit('(i8, i8, i8[:], i8[:,:])', parallel=True)
def solve(N, Q, C, LR):
    ans = np.zeros(Q, dtype=np.int64)
    for i in prange(Q):
        l, r = LR[i]
        used = np.zeros(N + 1, dtype=np.int32)

        for j in range(l - 1, r):
            if used[C[j]] == 0:
                ans[i] += 1
                used[C[j]] += 1

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

solve(N, Q, C, LR)

Submission status: Wrong Answer

Solution code:
import numpy as np
from numba import njit, prange

N, Q = map(int, input().split())
C = np.asarray(list(map(int, input().split())))
LR = np.asarray([list(map(int, input().split())) for _ in range(Q)])

@njit('(i8, i8, i8[:], i8[:,:])')
def solve(N, Q, C, LR):
    ans = np.zeros(N, dtype=np.int64)
    for i in prange(Q):
        l, r = LR[i]
        used = np.zeros(N, dtype=np.int32)
        for j in prange(l - 1, r):
            if used[C[j]] == 0:
                ans[i] += 1
                used[C[j]] += 1

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

solve(N, Q, C, LR)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    # k: index , x: value
    def update(self, k: int, x):
        k += self.N0 - 1
        ############################
        self.data[k] = x
        ###########################
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    # rightは開区間  l<=x<r
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        ##########################
        a, b = [], []
        while L < R:
            if L & 1:
                a.append(L - 1)
                L += 1
            if R & 1:
                R -= 1
                b.append(R - 1)
            L >>= 1
            R >>= 1
        for i in a + b[::-1]:
            res = self.segfunc(res, self.data[i])
        ##########################
        return res


C=list(map(int, input().split()))
state=[-1]*N
que=[]
for i in range(N):
    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i
    else:
        que.append((state[c-1],i))
        state[c-1]=i

que=sorted(que, key=lambda x: x[1])
        
query=[]
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l-1,r-1,i))
query=deque(sorted(query, key=lambda x: x[1]))

A=[0]*(N+1)
def add(a,b):
    return a+b
seg=SegmentTree(A,add,0)
ans=[0]*Q



for i in range(len(que)):
    while query and query[0][1]<que[i][1]:
        q=query.popleft()
        l,r,j=q
        ans[j]=r-l+1-seg.query(l,r+1)

    now=que[i]
    l, r=now  # index
    A[l]+=1
    seg.update(l, A[l])

    while query and query[0][1]==r:
        q=query.popleft()
        lq,rq,j=q
        
        ans[j]=rq-lq+1-seg.query(lq,rq+1)
        #print(lq, rq, seg.query(lq,rq+1))

while query:
    q=query.popleft()
    lq,rq,j=q     
    ans[j]=rq-lq+1-seg.query(lq,rq+1)
    #print(lq, rq, seg.query(lq,rq+1))

for a in ans:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def RSQ_add(i, x):
    while True:
        if i > n:
            break
        b[i] += x
        i += i & -i

def RSQ_getsum(i):
    s = 0
    while True:
        if i <= 0:
            break
        s += b[i]
        i -= i & -i
    return s

n, q = map(int, input().split())
c = list(map(int, input().split()))
cc = [0] * n
b = [0] * (n + 1)
a = [deque() for _ in range(n)]
addlist = [0] * (n + 1)
for i in range(n):
    if cc[c[i] - 1] == 0:
        RSQ_add(i + 1, 1)
        cc[c[i] - 1] = 1
        addlist[i + 1] = 1
        #print(b)
    else:
        a[c[i] - 1].append(i + 1)
#x = [0] * q
x = [deque() for _ in range(n + 1)]
for i in range(q):
    l, r = map(int, input().split())
    #x[i] = [l, r, i]
    x[l].append([r, i])
#print(x)
#x.sort()
i = 1
xx = [0] * q
endcnt = 0
"""
for i in range(q):
    for j in range(u, x[i][0]):
        if cc[c[j - 1] - 1] == 1:
            if a[c[j - 1] - 1]:
                p = a[c[j - 1] - 1].popleft()
                RSQ_add(p, 1)
                addlist[p] = 1
        if addlist[j + 1]:
            endcnt += 1
            addlist[j + 1] = 0
    u = x[i][0]
    xx[x[i][2]] = RSQ_getsum(x[i][1]) - endcnt
    #print(b)
"""

while i <= n:
    while x[i]:
        r, j = x[i].popleft()
        xx[j] = RSQ_getsum(r) - endcnt
    if cc[c[i - 1] - 1] == 1:
        if a[c[i - 1] - 1]:
            p = a[c[i - 1] - 1].popleft()
            RSQ_add(p, 1)
            addlist[p] = 1
    if addlist[j + 1]:
        endcnt += 1
    i += 1

for i in xx:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, Q = in_nn()
    C = in_nl()
    LR = []

    for q in range(Q):
        l, r = in_nn()
        LR.append((r + 0.1, l, q))

    t = [-1] * (N + 1)
    sect = []
    for i in range(N):
        x = C[i]
        if t[x] != -1:
            sect.append((i + 1, t[x], -1))
        t[x] = i + 1

    sect += LR
    sect.sort()
    exit()

    bit = [0] * (N + 1)

    def add(i, val):
        while i <= N:
            bit[i] += val
            i += i & -i

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i & -i
        return res

    ans = [0] * Q
    for s in sect:
        r, l, n = s
        r = int(r)

        if n == -1:
            add(l, 1)
        else:
            t = sum(r) - sum(l - 1)
            ans[n] = r - l + 1 - t

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, Q = in_nn()
    C = in_nl()
    LR = []

    for q in range(Q):
        l, r = in_nn()
        LR.append((r, l, q))

    t = [-1] * (N + 1)
    sect = []
    for i in range(N):
        x = C[i]
        if t[x] != -1:
            sect.append((i + 1, t[x], -1))
        t[x] = i + 1

    sect += LR
    # sect.sort(key=lambda x: (x[0], x[2]))
    exit()

    bit = [0] * (N + 1)

    def add(i, val):
        while i <= N:
            bit[i] += val
            i += i & -i

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i & -i
        return res

    ans = [0] * Q
    for s in sect:
        r, l, n = s

        if n == -1:
            add(l, 1)
        else:
            t = sum(r) - sum(l - 1)
            ans[n] = r - l + 1 - t

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, Q = in_nn()
    C = in_nl()
    LR = []

    for q in range(Q):
        l, r = in_nn()
        LR.append((r, l, q))

    t = [-1] * (N + 1)
    sect = []
    for i in range(N):
        x = C[i]
        if t[x] != -1:
            sect.append((i + 1, t[x], -1))
        t[x] = i + 1

    sect += LR
    sect.sort(key=lambda x: (x[0], x[2]))
    exit()

    bit = [0] * (N + 1)

    def add(i, val):
        while i <= N:
            bit[i] += val
            i += i & -i

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i & -i
        return res

    ans = [0] * Q
    for s in sect:
        r, l, n = s

        if n == -1:
            add(l, 1)
        else:
            t = sum(r) - sum(l - 1)
            ans[n] = r - l + 1 - t

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
li=list(map(int,input().split()))
r=[0]*(n+1)
l=[0]*(n+1)
rs=set()
ls=set()
for i in range(n):
  if li[i] in rs:
    r[i+1]=r[i]
  else:
    r[i+1]=r[i]+1
    rs.add(li[i])
  if li[-1-i] in ls:
    l[i+1]=l[i]
  else:
    l[i+1]=l[i]+1
    ls.add(li[-1-i])
for i in range(q):
  a,b=map(int,input().split())
  if a==b:
    print(1)
  else:  
    print(max(r[b]-r[a-1],l[-a]-l[-b-1]))

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


class Bit:

    def __init__(self, a):  # 配列か要素数で初期化
        if hasattr(a, "__iter__"):
            le = len(a)
            self.n = 1 << le.bit_length()
            self.values = values = [0] * (self.n + 1)
            values[1:le + 1] = a[:]
            for i in range(1, self.n):
                values[i + (i & -i)] += values[i]
        elif isinstance(a, int):
            self.n = 1 << a.bit_length()
            self.values = [0] * (self.n + 1)
        else:
            raise TypeError

    def add(self, i, val):  # a[i] += val
        n, values = self.n, self.values
        while i <= n:
            values[i] += val
            i += i & -i

    def sum(self, i):  # (0, i] の累積和
        values = self.values
        res = 0
        while i > 0:
            res += values[i]
            i -= i & -i
        return res

    def bisect_left(self, v):  # 累積和 が v 以上になる最小の i
        n, values = self.n, self.values
        if v > values[n]:
            return None
        i, step = 0, n >> 1
        while step:
            if values[i + step] < v:
                i += step
                v -= values[i]
            step >>= 1
        return i + 1


def main():

    N, Q = in_nn()
    C = in_nl()
    LR = []

    for q in range(Q):
        l, r = in_nn()
        LR.append((r, l, q))

    t = [-1] * (N + 1)
    sect = []
    for i in range(N):
        x = C[i]
        if t[x] != -1:
            sect.append((i + 1, t[x], -1))
        t[x] = i + 1

    sect += LR
    sect.sort(key=lambda x: (x[0], x[2]))

    print(sect)

    ans = []
    bit = Bit(N)
    for s in sect:
        r, l, n = s

        if n == -1:
            bit.add(l, 1)
        else:
            t = bit.sum(r) - bit.sum(l - 1)
            ans.append((n, r - l + 1 - t))

    ans.sort()
    for q in range(Q):
        print(ans[q][1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.buffer.readline
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])


BIT = [0] * (n + 1)


def update(idx, val):
    while idx <= n:
        BIT[idx] += val
        idx += idx & (-idx)


def query(idx):
    res = 0
    while idx > 0:
        res += BIT[idx]
        idx -= idx & (-idx)
    return res


pos = [-1] * (n + 1)


def func(idx):
    temp = C[idx]
    if pos[temp] == -1:
        pos[temp] = idx + 1
        update(idx + 1, 1)
    else:
        pre = pos[temp]
        update(pre, -1)
        update(idx + 1, 1)


ans = [0] * (q)
idx = 0
for i in range(q):
    l, r, ans_num = LR[i]
    l -= 1
    r -= 1
    while idx < r + 1:
        if idx < n:
            func(idx)
            idx += 1
        else:
            break
    res = 0
    res += query(r + 1)
    if l > 0:
        res -= query(l)
    ans[ans_num] = res

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