結果

問題 No.2935 Division Into 3 (Mex Edition)
ユーザー nouka28
提出日時 2024-10-04 00:05:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,707 ms / 5,000 ms
コード長 1,670 bytes
コンパイル時間 123 ms
コンパイル使用メモリ 82,196 KB
実行使用メモリ 296,796 KB
最終ジャッジ日時 2024-10-04 00:07:10
合計ジャッジ時間 62,407 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

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

P=[i for i in range(n)]

T=400000
dp=[[]for i in range(3*T)]
dp2=[[]for i in range(3*T)]

def build(l:int,r:int,k:int,idx:list)->None:
    global dp,dp2
    for C in range(1,4):
        R=0
        now=0

        cnt=[0]*(r-l)

        for i in range(len(idx)):
            assert i<=R

            while R<len(idx) and now<r-l:
                cnt[a[idx[R]]-l]+=1
                if cnt[a[idx[R]]-l]==C:
                    now+=1
                R+=1
            
            if now==r-l:
                dp[(C-1)*T+k].append(idx[i])
                dp2[(C-1)*T+k].append(idx[R-1])
            
            if cnt[a[idx[i]]-l]==C:
                now-=1
            
            cnt[a[idx[i]]-l]-=1
        dp[(C-1)*T+k].append(10**9)
        dp2[(C-1)*T+k].append(10**9)

    if r-l==1:return

    idxL=[]
    idxR=[]
    mid=(l+r)//2

    for e in idx:
        if a[e]<mid:idxL.append(e)
        else:idxR.append(e)
    
    build(l,mid,2*k+1,idxL)
    build(mid,r,2*k+2,idxR)

def search(l:int,r:int,k:int,C:int,L:int,R:int)->int:
    p=bisect.bisect_left(dp[(C-1)*T+k],L)
    p=dp2[(C-1)*T+k][p]

    if p<R:return r
    if r-l==1:return l

    mid=(l+r)//2
    res=search(l,mid,2*k+1,C,L,R)
    if res<mid:return res
    else:return search(mid,r,2*k+2,C,L,R)

build(0,100001,0,P)

q=int(input())

res_prev=0

while q:
    q-=1

    x,y=map(int,input().split())

    L=(x^res_prev)-1
    R=y^res_prev

    # print("L R : ",L,R)

    assert 0<=L and R-L>=2 and R<=n

    v=[search(0,100001,0,C,L,R)for C in range(1,4)]

    res=min(sum(v),R-L-sum([not i for i in v]))

    print(res)

    res_prev=res
0