建设网站应达到的目的和作用,平面设计培训大概费用,网站开发的母的目的和意义.,建设银行报网站题干#xff1a;
前缀异或 基准时间限制#xff1a;2 秒 空间限制#xff1a;131072 KB 分值: 5
输入一个长度为n(1 n 100000)数组a[1], a[2], ..., a[n]。
输入一个询问数m(1 m 100000)和m组询问#xff0c;每组询问形如(l, r)
对于每组询问(l, …题干
前缀异或 基准时间限制2 秒 空间限制131072 KB 分值: 5
输入一个长度为n(1 n 100000)数组a[1], a[2], ..., a[n]。
输入一个询问数m(1 m 100000)和m组询问每组询问形如(l, r)
对于每组询问(l, r)你需要输出a[l] xor a[l 1] xor ... xor a[r - 1] xor a[r]即第l个数字到第r个数字的异或。
如果你的算法需要约n*m的时间你将只能通过第一个测试点。
如果你的算法需要约nm的时间你将可以通过本题。
Input
第一行一个整数n
第二行为n个整数a[1], a[2], ... a[n]
第三行一个整数m
接下来m行每行两个整数l, r表示询问。
Output
输出一共m行对于每一个询问输出一个整数表示结果。
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
解题报告 题目倒是不难主要是更好的理解一下前缀和最后查询的时候不是“-”而是异或的逆运算 其实依旧是异或。。
AC代码
#includebits/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);cinn;for(int i 1; in; i) {scanf(%lld,a[i]);ans[i] ans[i-1] ^ a[i];}
// for(int i 1; in; i) {
// printf(%d ,ans[i]);
// }
// printf(\n);cinm;int l,r;while(m--) {scanf(%d%d,l,r);printf(%lld\n,ans[r] ^ ans[l - 1]);}return 0;}
