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:
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
        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)
    lridx=len(lri)-1
    lft,rgt,idx=lri[lridx]
    lridx-=1
    # 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 lridx<0:
                break
            lft,rgt,idx=lri[lridx]
            lridx-=1
    for i in ans:
        print(i)
main()

Submission status: Wrong Answer

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

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

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

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))
bit = BIT(N)
#color[i] => 色iが最後に登場したインデックス(1-indexed)
color = [0]*(N+1)

ANS = [0]*Q
LR.sort(key=lambda x: x[1])
cur = 1
for l,r,j in LR:
    for i in range(cur,r+1):
        c = C[i-1]
        if color[c] == 0:
            color[c] = cur
            bit.add(i,1)
        else:
            bit.add(color[c],-1)
            color[c] = i
            bit.add(i,1)
    cur = r+1
    ANS[j] = bit.sum(r)-bit.sum(l-1)
for a in ANS:
    print(a)

Submission status: Wrong Answer

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

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

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

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))
bit = BIT(N)
#color[i] => 色iが最後に登場したインデックス(1-indexed)
color = [0]*(N+1)

ANS = [0]*Q
LR.sort(key=lambda x: x[1])
cur = 1
for l,r,j in LR:
    for i in range(cur,r+1):
        c = C[i-1]
        if color[c] == 0:
            color[c] = cur
            bit.add(i,1)
        else:
            bit.add(color[c],-1)
            color[c] = i
            bit.add(i,1)
    ANS[j] = bit.sum(r)-bit.sum(l-1)
for a in ANS:
    print(a)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
class BIT():
    def __init__(self, N):
        self._N = N
        self._bit = [0 for _ in range(N+1)]

    @property
    def bit(self):
        return self._bit

    def add(self, a, w):
        """v[a]に値wを加算する"""
        x = a
        while x <= self._N:
            self._bit[x] += w
            x += x&-x

    def sum(self, a):
        """区間和v[1]+...+v[a]を返す"""
        ret = 0
        x = a
        while x > 0:
            ret += self._bit[x]
            x -= x&-x
        return ret


def solve():
    """ 解説実装 """
    import sys
    N, Q = list(map(int, sys.stdin.readline().split()))
    Cs = list(map(int, sys.stdin.readline().split()))

    # (s,t)の位置を保持するst_listを作っていく
    s_set = set()  # sの座標をとにかく保持する
    st_list = []
    dic = {}  # (s,t)を保持する辞書
    for i, c in enumerate(Cs):
        if not c in dic:
            dic[c] = (i+1, None)  # tは決まっていないのでNoneとする
            continue
        if dic[c][1] is None:
            # はじめて(s,t)が作成された
            dic[c] = (dic[c][0], i+1)
        else:
            # 既に(s,t)が作成されている場合
            dic[c] = (dic[c][1], i+1)
        st_list.append(dic[c])
        s_set.add(dic[c][0])

    # (l,r)の位置を保持するlr_listを作っていく
    lr_list = []
    for q in range(Q):
        l, r = list(map(int, sys.stdin.readline().split()))
        lr_list.append(((l, r), q))
        s_set.add(l)

    s_list = list(s_set)
    st_list.sort()
    lr_list.sort()
    anss = [-1 for _ in range(Q)]

    # 右から左へ平面走査するとき、座標sの時点で座標t以下の(s,t)が何個あるかを、
    # t_ruiskei[座標t] := 座標t以下の(s,t)の個数
    # で表す
    st_i = len(st_list)-1
    lr_i = len(lr_list)-1
    t_ruiseki = BIT(5*10**5)

    for s in s_list[::-1]:  # 右から左へ走査する
        while st_i >= 0 and st_list[st_i][0] == s:  # ダセェな！
            t_ruiseki.add(st_list[st_i][1], 1)
            st_i -= 1

        # クエリを実行する
        while lr_i >= 0 and lr_list[lr_i][0][0] == s:
            lr, query = lr_list[lr_i]
            l, r = lr
            anss[query] = (r-l+1) - t_ruiseki.sum(r)
            lr_i -= 1

    for q in range(Q):
        print(anss[q])


if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n, q = nm()
    c = nl()
    g = [tuple(nm()) for _ in range(q)]
    g.sort(key=lambda x: x[0]//600 * 10**7 + x[1] * (-1) ** ((x[0] // 600) & 1))
    l, r = 0, -1
    d = [0]*(n+1)
    ans = 0
    for nc, nr in g:
        while r < nr:
            r += 1

    return

solve()

Submission status: Wrong Answer

Solution code:
from itertools import *

class BIT:
    def __init__(self, size):
        self.size = size
        self.A = [0] * (size+1)
    def read(self, i):
        s = 0
        while i > 0: s += self.A[i]; i -= i&-i;
        return s
    def add(self, i, k):
        while i <= self.size: self.A[i] += k; i += (i&-i);

n, q = map(int, input().split())
cs = list(map(int, input().split()))
last_seen = [n+1]*(n+2)
queries = [list(map(int, input().split())) + [0] for i in range(q)]
queriesAt = {k: list(v) for k,v in groupby(queries, lambda q: q[0])}
# print(queriesAt)

answers = {}
bit = BIT(n+3)
for l in range(n, 0, -1):
    bit.add(last_seen[cs[l-1]], -1)
    bit.add(l, 1)
    last_seen[cs[l-1]]=l
    for q in queriesAt.get(l, []):
        if q[0]==l:
            q[2] = bit.read(q[1])
for q in queries: print(q[2])

Submission status: Wrong Answer

Solution code:
from itertools import *

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

L = [0]*n
R = [0]*n
a = 0
for i in range(0, len(cs)):
    a |= 1 << cs[i]
    L[i] = a
a = 0
for i in range(len(cs)-1, -1, -1):
    a |= 1 << cs[i]
    R[i] = a

for i in range(q):
    l, r = map(int, input().split())
    print(bin(L[r-1] & R[l-1]).count('1'))

Submission status: Wrong Answer

Solution code:

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

class BIT:
    def __init__(self, n=0):
        self.n = n
        self.d = [0] * (n+1)
    
    def add(self, i, x=1):
        i = int(i+1) # index begin 1
        while i <= self.n:
            self.d[i] += x
            i += i&-i # add LSB
    
    def sum(self, i=None):
        x = 0
        i = int( i+1 if not (i is None) else self.n )
        while i > 0:
            x += self.d[i]
            i -= i&-i # sub LSB
        return x

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

# check colors pair index (s,t)
st = [0] * (n+1)
col_last = [0] * (n+1)
for i in range(n):
    t = i + 1
    col = c[i]
    s = col_last[col]
    if s > 0:
        st[s] = t
    col_last[col] = t
dprint("st =", st)

# input querys (l,r)
lr = [None] * n
qs = list()
sorted_qs = list()
for i in range(q):
    l, r = list(map(int, input().split()))
    qs.append((i,l,r)) 
sorted_qs = sorted(qs, key=lambda q: q[1], reverse=True)
dprint("qs =", qs)
dprint("sorted_qs =", sorted_qs)

i_qs = 0
x = n
d = BIT(n+1)
qs_ans = [0] * len(qs)
for i_qs in range(len(sorted_qs)):
    i, l, r = sorted_qs[i_qs]
    dprint("i, l, r", i, l, r)
    while (x >= l):
        if st[x] > 0:
            d.add(st[x])
            dprint("add x(s), t =", x, st[x])
        x -= 1
    qs_ans[i] = (r-l+1)-d.sum(r)

for ans in qs_ans:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.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))

# 1-indexed
left_index_dict = {}
d = defaultdict(int)

for i, ci in enumerate(c):
    index = d[ci]
    if index in left_index_dict:
        left_index_dict[index].append(i+1)
    else:
        left_index_dict[index] = [i+1]
    d[ci] = i + 1

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

# index = list(left_index_dict.keys())
# index.sort()
# i = 0

# N = n
# bit = [0] * (N+1)

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

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

# ans = [0] * q

# for l, r, _i in lr:
#     while i < len(index) and index[i] < l:
#         for j in left_index_dict[index[i]]:
#             add(j, 1)
#         i += 1
#     ans[_i] = sum(r) - sum(l-1)

# for ansi in ans:
#     print(ansi)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.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))

# 1-indexed
left_index_dict = {}
d = defaultdict(int)

for i, ci in enumerate(c):
    index = d[ci]
    if index in left_index_dict:
        left_index_dict[index].append(i+1)
    else:
        left_index_dict[index] = [i+1]
    d[ci] = i + 1

lr.sort()

# index = list(left_index_dict.keys())
# index.sort()
# i = 0

# N = n
# bit = [0] * (N+1)

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

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

# ans = [0] * q

# for l, r, _i in lr:
#     while i < len(index) and index[i] < l:
#         for j in left_index_dict[index[i]]:
#             add(j, 1)
#         i += 1
#     ans[_i] = sum(r) - sum(l-1)

# for ansi in ans:
#     print(ansi)

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1]*(n+1)
A = [0]*q
LR = tuple(tuple(map(int, input().split())) for _ in range(q))
W = sorted((r, i) for i, (l, r) in enumerate(LR))
B = [0]*(1<<n.bit_length())
def add(i, a):
  while i < n:
    B[i] += a
    i += i & -i
def acc(i):
  res = 0
  while i:
    res += B[i]
    i -= i & -i
  return res
temp = 1
for r, i in W:
  while temp <= r:
    c = C[temp]
    add(temp, 1)
    if D[c] != -1:
      add(D[c], -1)
    D[c] = temp
    temp += 1
  l = LR[i][0]
  A[i] = acc(r) - acc(l-1)
print(*A, sep="\n")

Submission status: Wrong Answer

Solution code:
class Binary_Indexed_Tree_Exception(Exception):
    pass

class Binary_Indexed_Tree():
    def __init__(self,N,L=[]):
        """calcを演算とするN項のBinary Indexed Treeを作成

        N:要素数
        """
        self.calc=lambda x,y:x+y
        self.unit=0

        N=max(N,len(L))

        k=1
        d=1

        while k<N:
            k*=2
            d+=1

        X=[None]+[0]*k

        self.num=k
        self.depth=d

        if L:
            for i in range(len(L)):
                p=i+1
                while p<=k:
                    X[p]+=L[i]
                    p+=p&(-p)
        self.data=X

    def index(self,k,index=1):
        """第k要素の値を出力する.

        k:数列の要素
        index:先頭の要素の番号
        """

        p=k+(1-index)
        return self.sub_array(p,p)

    def add(self,k,x,index=1):
        """第k要素にx加え,更新を行う.

        k:数列の要素
        x:更新後の値
        index:先頭の要素の番号
        """
        p=k+(1-index)
        while p<=self.num:
            self.data[p]+=x
            p+=p&(-p)

    def update(self,k,x,index=1):
        """第k要素をxに変え,更新を行う.

        k:数列の要素
        x:更新後の値
        """

        a=self.index(k,index)
        y=x-a

        self.add(k,y,index)

    def sub_array(self,From,To,index=1):
        """第From要素から第To要素までの総和を求める.

        From:始まり
        To:終わり
        index:先頭の要素の番号
        """
        alpha=From+(1-index)
        beta=To+(1-index)
        return self.__section(beta)-self.__section(alpha-1)

    def __section(self,To):
        S=0
        x=To
        while x>0:
            S+=self.data[x]
            x-=x&(-x)
        return S
#================================================
N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

G=[0]*Q
X=[0]*Q
U={}
for i in range(Q):
    G[i]=tuple(map(int,input().split()))
    U[G[i]]=i

G.sort(key=lambda x:x[1])
F=[-1]*(N+1)
T=Binary_Indexed_Tree(N)

Y=1
for (L,R) in G:
    while Y<=R:
        c=C[Y]

        if F[c]!=-1:
            T.add(F[c],-1)

        F[c]=Y
        T.add(Y,1)
        Y+=1
        P=T.sub_array(1,R)

    if L!=1:
        X[U[(L,R)]]=P-T.sub_array(1,L-1)
    else:
        X[U[(L,R)]]=P

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

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import Decimal #floatの高精度ver, 渡すのはstr型で
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
class BIT:
    def __init__(self,n):
        self.n=n
        self.data= [0]*(n+1) #これがBIT
        self.el= [0]*(n+1) #これが元データ
    def sum(self,i):  #iまでの和
        s=0
        while i>0:
            s+=self.data[i]
            i-= i&(-i)
        return s
    def add(self,i,x):  #iにxを足す(x<0)
        self.el[i]+=x
        while i<= self.n:
            self.data[i]+= x
            i+= i&-i
    def get(self,i,j=None):  #iからjまでの和、iだけなら普通の要素iを取得(いる？)
        if j is None:
            return self.el[i]
        return self.sum(j)-self.sum(i)
    

n,q=map(int,input().split())
C=list(map(int,input().split()))
C=[i-1 for i in C]  #球の純粋配置
Q=[]
for i in range(q):
    l,r=map(int,input().split())
    l-=1;r-=1
    Q.append([i,l,r])
Q=sorted(Q, key=lambda x:x[2]) 
ANS=[-1]*q

B=BIT(n)
YOI=[-1]*n #色iの良い球の位置
for i in range(Q[0][2],-1,-1):
    if YOI[i]==-1:
        YOI[C[i]]=i
        B.add(i+1,1)


ANS[Q[0][0]]= B.sum(Q[0][2]+1)- B.sum(Q[0][1])
left=Q[0][1]; right=Q[0][2]
#print(B.data)

for l in Q[1:]:
    newleft,newright=l[1],l[2]
    for i in range(newright,right,-1):
        if YOI[C[i]]==-1: #新種の色
            YOI[C[i]]=i
            B.add(i+1, 1)
        elif YOI[C[i]]>i:
            continue
        else:
            B.add(YOI[C[i]]+1, -1)
            YOI[C[i]]=i
            B.add(i+1, 1)
    ANS[l[0]]= B.sum(newright+1)- B.sum(newleft)
    left,right= newleft,newright
    #print(B.data)
for i in ANS:
    print(i)

Submission status: Wrong Answer

Solution code:
class BIT:
    def __init__(self,n):
        self.n=n
        self.data= [0]*(n+1) #これがBIT
        self.el= [0]*(n+1) #これが元データ
    def sum(self,i):  #iまでの和
        s=0
        while i>0:
            s+=self.data[i]
            i-= i&(-i)
        return s
    def add(self,i,x):  #iにxを足す(x<0)
        self.el[i]+=x
        while i<= self.n:
            self.data[i]+= x
            i+= i&-i
    def get(self,i,j=None):  #iからjまでの和、iだけなら普通の要素iを取得(いる？)
        if j is None:
            return self.el[i]
        return self.sum(j)-self.sum(i)
    

n,q=map(int,input().split())
C=list(map(int,input().split()))
C=[i-1 for i in C]  #球の純粋配置
Q=[]
for i in range(q):
    l,r=map(int,input().split())
    l-=1;r-=1
    Q.append([i,l,r])
Q=sorted(Q, key=lambda x:x[2]) 
ANS=[-1]*q

B=BIT(n)
YOI=[-1]*n #色iの良い球の位置
for i in range(Q[0][2],-1,-1):
    if YOI[i]==-1:
        YOI[C[i]]=i
        B.add(i+1,1)


ANS[Q[0][0]]= B.sum(Q[0][2]+1)- B.sum(Q[0][1])
left=Q[0][1]; right=Q[0][2]
#print(B.data)

for l in Q[1:]:
    newleft,newright=l[1],l[2]
    for i in range(newright,right,-1):
        if YOI[C[i]]==-1: #新種の色
            YOI[C[i]]=i
            B.add(i+1, 1)
        elif YOI[C[i]]>i:
            continue
        else:
            B.add(YOI[C[i]]+1, -1)
            YOI[C[i]]=i
            B.add(i+1, 1)
    ANS[l[0]]= B.sum(newright+1)- B.sum(newleft)
    left,right= newleft,newright
    #print(B.data)
for i in ANS:
    print(i)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

A=[i-1 for i in A]

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

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

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

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

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

# print(BIT)

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


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

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


for i in ANS:
    print(i)

Submission status: Wrong Answer

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

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

A=[i-1 for i in A]

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

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

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

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

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

# print(BIT)

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


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

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


for i in ANS:
    print(i)

Submission status: Wrong Answer

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

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

A=[i-1 for i in A]

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

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

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

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

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

# print(BIT)

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


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

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


for i in ANS:
    print(i)

Submission status: Wrong Answer

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

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

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

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

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

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


            

 
 
 
 
my_main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

def solve(h, w, a):
    c = Counter(list("".join(a)))
    d = Counter(list(map(lambda num: num % 4, c.values())))
    if (h % 2 == 0) and (w % 2 == 0):
        return "Yes" if list(d.keys()) == [4] else "No"
    if (h % 2 == 1) and (w % 2 == 1):
        for k in [1, 3]:
            if k in d:
                if d[k] != 1:
                    return "No"
        if 1 in d and 3 in d:
            return "No"
        if (2 in d) and d[2] > sum(x // 2 for x in [h,w]):
            return "No"
    else:
        for k in [1, 3]:
            if k in d:
                return "No"
        if (2 in d) and d[2] > sum((x % 2 == 0) * (x // 2) for x in [h,w]):
            return "No"
    return "Yes"

h, w = map(int, input().split())
a = [input() for r in range(h)]
print(solve(h, w, a))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    def I(): return int(input())
    
    readline = sys.stdin.readline
    readall = sys.stdin.read
    MI = lambda: map(int, readline().split())
    LI = lambda: list(map(int, readline().split()))
    
    class BIT:
        '''
        0-indexed
        '''
        def __init__(self, N):
            self.size = N
            self.tree = [0] * (N + 1)
            self.depth = N.bit_length()

        def _bitsum(self, i):
            ret = 0
            while i:
                ret += self.tree[i]
                i ^= i & -i
            return ret

        # [l,r)の和
        def bitsum(self, l, r=None):
            if r is None:
                return self._bitsum(l)
            else:
                return self._bitsum(r) - self._bitsum(l)

        # i番目にxを追加
        def add(self, i, x):
            i += 1
            while i <= self.size:
                self.tree[i] += x
                i += i & -i
            return

        def lower_bound(self, x):
            sum_ = 0
            pos = 0
            v = 1 << self.depth
            for i in range(self.depth, -1, -1):
                k = pos + v
                if k <= self.size and sum_ + self.tree[k] < x:
                    sum_ += self.tree[k]
                    pos += v
                v >>= 1
            return pos + 1, sum_

    
    N,Q=MI()
    C=LI()
    
    R=[0]*Q
    L=[0]*Q
    I=[0]*Q
    for i in range(Q):
        l,r=MI()
        R[i]=r-1
        L[i]=l-1
        I[i]=i
        
    R,L,I = zip(*sorted(zip(R,L,I)))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline

    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    
    class BIT:
        '''
        0-indexed
        '''
        def __init__(self, N):
            self.size = N
            self.tree = [0] * (N + 1)
            self.depth = N.bit_length()

        def _bitsum(self, i):
            ret = 0
            while i:
                ret += self.tree[i]
                i ^= i & -i
            return ret

        # [l,r)の和
        def bitsum(self, l, r=None):
            if r is None:
                return self._bitsum(l)
            else:
                return self._bitsum(r) - self._bitsum(l)

        # i番目にxを追加
        def add(self, i, x):
            i += 1
            while i <= self.size:
                self.tree[i] += x
                i += i & -i
            return

        def lower_bound(self, x):
            sum_ = 0
            pos = 0
            v = 1 << self.depth
            for i in range(self.depth, -1, -1):
                k = pos + v
                if k <= self.size and sum_ + self.tree[k] < x:
                    sum_ += self.tree[k]
                    pos += v
                v >>= 1
            return pos + 1, sum_

    
    N,Q=MI()
    C=LI()
    
    R=[0]*Q
    L=[0]*Q
    I=[0]*Q
    for i in range(Q):
        l,r=MI()
        R[i]=r-1
        L[i]=l-1
        I[i]=i
        
    R,L,I = zip(*sorted(zip(R,L,I)))
    
main()