b405: 【記憶中】之記憶中的序列
Tags : 可持久化 平衡樹
Accepted rate : 5人/7人 ( 71% ) [非即時]
評分方式:
Tolerant

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

Content

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

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

操作有以下8種: 

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

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

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

3 x y 翻转序列第x个位置和第y个位置之间的所有数 1<=x<=y<=L[d]

4 x y v 序列第x个位置和第y个位置之间的所有数都加上v 1<=x<=y<=L[d],0<=v<100000

5 x y 求序列第x个位置和第y个位置之间的最大值 1<=x<=y<=L[d]

6 x y 求序列第x个位置和第y个位置之间的最小值 1<=x<=y<=L[d]

7 x y 求序列第x个位置和第y个位置之间的所有数之和 1<=x<=y<=L[d]

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

Input

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

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

第三行是一個正整數q(1<=q<=60000),表示接下來有q天。

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

輸入保證合法。

Output
對於每個第5,6,7種詢問操作,對應地輸出一個數字,表示答案。
Sample Input
10
9 81 28 6 40 68 74 50 82 62 
15
1 1 83
2 11
3 7 8
4 4 10 28
5 2 6
85 82 89
14 13 13
56 61
57 57 40
58 61
59 61 63
60 57 59 4
61 58 49
137 139 136
37 38 42
Sample Output
83
9
56
143
34
381
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (50%): 2.0s , <10M
公開 測資點#1 (50%): 2.0s , <10M
Hint :

輸入範例解密后應該是:

10
9 81 28 6 40 68 74 50 82 62
15
1 1 83
2 11
3 7 8
4 4 10 28
5 2 6
6 1 10
7 4 4
0 5
1 1 16
2 5
3 5 7
4 1 3 60
5 2 9
6 4 7
7 4 8

對50%的測資,沒有第0種操作。

注意使用long long。

這是【記憶中】系列的第一題,下一題是【記憶中】之記憶中的序列2

Tags:
可持久化 平衡樹
出處:
[管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」