zxa and xor

题目连接：

http://acm.hdu.edu.cn/showproblem.php?pid=5683

Description

zxa had a great interest in exclusive disjunction(i.e. XOR) recently, therefore he took out a non-negative integer sequence a1,a2,⋯,an of length n.

zxa thought only doing this was too boring, hence a function funct(x,y) defined by him, in which ax would be changed into y irrevocably and then compute ⊗1≤i<j≤n(ai+aj) as return value.

zxa is interested to know, assuming that he called such function m times for this sequence, then what is the return value for each calling, can you help him?

tips:⊗1≤i<j≤n(ai+aj) means that (a1+a2)⊗(a1+a3)⊗⋯⊗(a1+an)⊗(a2+a3)⊗(a2+a4)⊗⋯⊗(a2+an)⊗⋯⊗(an−1+an).

Input

The first line contains an positive integer T, represents there are T test cases.

For each test case:

The first line contains two positive integers n and m.

The second line contains n non-negative integers, represent a1,a2,⋯,an.

The next m lines, the i-th line contains two non-negative integers x and y, represent the i-th called function is funct(x,y).

There is a blank between each integer with no other extra space in one line.

1≤T≤1000,2≤n≤2⋅104,1≤m≤2⋅104,0≤ai,y≤109,1≤x≤n,1≤∑n,∑m≤105

Output

For each test case, output in m lines, the i-th line a positive integer, repersents the return value for the i-th called function.

Sample Input

1

3 3

1 2 3

1 4

2 5

3 6

Sample Output

4

6

8

Hint

题意

zxa最近对按位异或(exclusive disjunction)产生了极大的兴趣，为此他拿出了一个长度为\(n\)的非负整数序列\(a_1,a_2,\cdots,a_n\)。

zxa觉得这样太单调了，于是他定义了一种方法\(funct(x,y)\)，表示将\(a_x\)不可逆转地修改为\(y\)后计算\(\otimes_{1\leq i < j\leq n}{(a_i+a_j)}\)作为该方法的返回值。

zxa很好奇，如果他对这个序列调用\(m\)次这样的方法，那么每次得到的返回值分别是多少，你能帮助他吗？

题解：

模拟就好了

题目怎么说的，就怎么做，这样就能AC

吃惊！

总而言之，从出题的意义上来说，这道题太蠢了……

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e4+6;

int a[maxn],ans,n,m;

void solve()

{

    scanf("%d%d",&n,&m);

    ans=0;

    for(int i=1;i<=n;i++)scanf("%d",&a[i]);

    for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)

        ans^=(a[i]+a[j]);

    while(m--)

    {

        int x,y;scanf("%d%d",&x,&y);

        for(int i=1;i<x;i++)ans^=(a[x]+a[i])^(y+a[i]);

        for(int i=x+1;i<=n;i++)ans^=(a[x]+a[i])^(y+a[i]);

        a[x]=y;

        printf("%d\n",ans);

    }

}

int main()

{

    int t;scanf("%d",&t);

    while(t--)solve();

    return 0;

}

zxa

HDU 5683 zxa and xor 暴力模拟