題干：

前綴異或?

?

基準(zhǔn)時(shí)間限制：2?秒 空間限制：131072?KB 分值:?5

輸入一個(gè)長(zhǎng)度為n(1 <= n <= 100000)數(shù)組a[1], a[2], ..., a[n]。

輸入一個(gè)詢問(wèn)數(shù)m(1 <= m <= 100000)和m組詢問(wèn)，每組詢問(wèn)形如(l, r)

對(duì)于每組詢問(wèn)(l, r)，你需要輸出a[l] xor a[l + 1] xor ... xor a[r - 1] xor a[r]，即第l個(gè)數(shù)字到第r個(gè)數(shù)字的異或。

如果你的算法需要約n*m的時(shí)間，你將只能通過(guò)第一個(gè)測(cè)試點(diǎn)。

如果你的算法需要約n+m的時(shí)間，你將可以通過(guò)本題。

Input

第一行一個(gè)整數(shù)n 第二行為n個(gè)整數(shù)a[1],?a[2],?...?a[n] 第三行一個(gè)整數(shù)m 接下來(lái)m行，每行兩個(gè)整數(shù)l,?r表示詢問(wèn)。

Output

輸出一共m行，對(duì)于每一個(gè)詢問(wèn)輸出一個(gè)整數(shù)表示結(jié)果。

Input示例

3 1?2?3 6 1?1 2?2 3?3 1?2 2?3 1?3

Output示例

1 2 3 3 1 0

解題報(bào)告：

? ? 題目倒是不難，，，主要是更好的理解一下前綴和，最后查詢的時(shí)候不是“-”！！！而是異或的逆運(yùn)算 其實(shí)依舊是異或。。

AC代碼：

#include<bits/stdc++.h> #define ll long long using namespace std; ll a[100000 + 5],ans[100000 + 5]; int n,m; int main() { // printf("%d\n",2^3);cin>>n;for(int i = 1; i<=n; i++) {scanf("%lld",&a[i]);ans[i] = ans[i-1] ^ a[i];} // for(int i = 1; i<=n; i++) { // printf("%d ",ans[i]); // } // printf("\n");cin>>m;int l,r;while(m--) {scanf("%d%d",&l,&r);printf("%lld\n",ans[r] ^ ans[l - 1]);}return 0;}

?

總結(jié)

以上是生活随笔為你收集整理的【51nod - 前缀异或】 对前缀和的理解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。