zxa and xor

Time Limit: 16000/8000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Problem 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

After the first called function, this sequence is $\{4,2,3\}$, and $(4+2)\otimes(4+3)\otimes(2+3)=4$.

After the second called function, this sequence is $\{4,5,3\}$ and $(4+5)\otimes(4+3)\otimes(5+3)=6$.

After the third called function, this sequence is $\{4,5,6\}$ and $(4+5)\otimes(4+6)\otimes(5+6)=8$.

思路：通过位运算一些简单性质，暴力；（居然不会超时。。。）

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define mod 1000000009

#define inf 999999999

#define esp 0.00000000001

//#pragma comment(linker, "/STACK:102400000,102400000")

int scan()

{

    int res =  , ch ;

    while( !( ( ch = getchar() ) >= '' && ch <= '' ) )

    {

        if( ch == EOF ) return  <<  ;

    }

    res = ch - '' ;

    while( ( ch = getchar() ) >= '' && ch <= '' )

        res = res *  + ( ch - '' ) ;

    return res ;

}

int a[];

int main()

{

    int x,y,z,i,t;

    scanf("%d",&x);

    while(x--)

    {

        scanf("%d%d",&y,&z);

        for(i=;i<=y;i++)

        scanf("%d",&a[i]);

        int sum=;

        for(i=;i<=y;i++)

        for(t=i+;t<=y;t++)

        sum^=(a[i]+a[t]);

        while(z--)

        {

            int pos,change;

            scanf("%d%d",&pos,&change);

            for(i=;i<=y;i++)

            {

                if(i!=pos)

                sum^=(a[i]+change)^(a[i]+a[pos]);

            }

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

            a[pos]=change;

        }

    }

    return ;

}

a2

hdu 5683 zxa and xor 暴力

zxa and xor