b411: 【記憶中】之記憶中的序列2
標籤 : 可持久化 塊狀鏈錶 平衡樹
通過比率 : 6人/7人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-07-09 23:44

內容

liouzhou_101是一名資料結構(数据结构,data structure)愛好者,他與序列有著不解之緣。

第0天morris1028送了他一個序列。他非常喜歡這個序列,他從第一天開始,每天都會對他的序列進行且僅進行一次操作。假設當前的操作是第d(d>=1)天的操作。令L[d]表示第d天序列在被操作之前的長度(L[d]>=1)。

操作有以下5種:  

0 k 将整个序列变回第k天的序列 0<=k<d

1 x v 在序列第x个位置后面插入一个权值为v的数 0<=x<=L[d] 1<=v<=100000

2 x 删除序列第x个位置的数 1<=x<=L[d]

3 x v 将序列第x个位置的数改为v 1<=x<=L[d] 1<=v<=100000

4 x y k 询问第x个位置和第y个位置之间所有数中第k小的数 1<=x<=y<=L[d] 1<=k<=y-x+1 

然而,他太喜歡這個序列了,以至於他做完操作之後只顧著欣賞整個序列,忘了去計算一些操作的答案。可是這些答案對他而言非常重要,現在他想請你幫他算一算。 

輸入說明

第一行是一個正整數n,表示第0天序列的長度,即L[0]。

第二行是n個以空格隔開的正整數,a[1],a[2],...,a[n],表示第0天的這個序列每個位置上的數字,每個數字都在1到100000之間。

第三行是一個正整數q,表示接下來有q天。

接下來q行,第d行表示第d天的操作信息,第一個數字t表示操作類型(0~5),然後對不同的操作,格式參見題目內容。為了模擬實際情況,在第d天,你並不可能知道第d+1天的操作,所以輸入數據中對操作信息進行了加密,就是輸入中的所有數,並不是真正的信息,如果你輸入了一個數字K,事實上你要把K理解成K xor ans,其中xor是異或操作,ans是最近一次詢問的答案,如果到現在為止沒有被詢問過,則我們不把信息加密,即ans=0。

輸入保證合法。

輸出說明
對於每個第4種詢問操作,對應地輸出一個數字,表示答案。
範例輸入
5
1 2 3 4 5
5
4 1 5 2
3 0 3
6 3 7 0
1 0
5 0 4 3
範例輸出
2
1
2
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 10.0s , <1M
公開 測資點#1 (20%): 10.0s , <10M
公開 測資點#2 (20%): 10.0s , <1M
公開 測資點#3 (20%): 10.0s , <10M
公開 測資點#4 (20%): 10.0s , <10M
提示 :

輸入範例解密后應該是:

5
1 2 3 4 5
5
4 1 5 2
1 2 1
4 1 5 2
0 1
4 1 5 2

 
測資1:n<=30000 q<=30000 t≠0
測資2:n<=20000 q<=50000 t≠0
測資3:n<=30000 q<=30000
測資4:n<=20000 q<=50000
測資5:n<=8000 q<=80000
 
這是【記憶中】系列的第二題,上一題是【記憶中】之記憶中的序列,下一題是【記憶中】之記憶中的并查集 
標籤:
可持久化 塊狀鏈錶 平衡樹
出處:
[管理者:
liouzhou_101 (王启圣)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」