ETH官方钱包

切換
舊版
前往
大廳
主題

ZeroJudge - c651: 三、區(qū)間xor(RXQ) 解題心得

Not In My Back Yard | 2019-09-01 23:05:56 | 巴幣 0 | 人氣 256

題目連結(jié):


題目大意:
第一列給定兩正整數(shù) N 、 Q (N 、 Q ≦ 10 ^ 6),代表有 N 個整數(shù) ai (1 ≦ i ≦ N)以及 Q 筆詢問。

第二列有 N 個非負(fù)整數(shù)(不超過 10 ^ 9),代表 ai 們的值。

從第三列開始的 Q 列輸入,每列的輸入只可能是:
0 l r (1 ≦ l ≦ r ≦ N),代表詢問 al XOR al + 1 XOR …… ar 的結(jié)果為何?
1 x v (1 ≦ x ≦ N , 0 ≦ v ≦ 10 ^ 9),代表將 ax 的值變更為 v 。

對於每筆詢問請輸出對應(yīng)的結(jié)果。



範(fàn)例輸入:
5 3
16 9 1 5 3
0 1 5
1 1 5
0 1 5


範(fàn)例輸出:
30
11


解題思維:
首先,輸出輸入量非常大,再加上評判系統(tǒng)之速度相對於題目出的時間時較為緩慢。因此需要最佳化輸出入的速度(要快過 scanf 、 printf),參見這篇

接著,因?yàn)檫@題是求區(qū)間 XOR 的結(jié)果,所以可以套用這題的資料結(jié)構(gòu)(將其中的取最大值之操作替換成 XOR 運(yùn)算即可)。BIT(Binary Indexed Tree)這個資料結(jié)構(gòu)也可以完成本題。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
追蹤 創(chuàng)作集

作者相關(guān)創(chuàng)作

更多創(chuàng)作