Problem Description
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
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
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
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<bitset>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int maxn = 2e4 + 10;
int T, x, y, a[maxn], ans, n, m;
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
ans = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
for (int j = i - 1; j; j--) ans ^= a[i] + a[j];
}
while (m--)
{
scanf("%d%d", &x, &y);
(ans ^= a[x] + a[x]) ^= a[x] + y;
for (int i = 1; i <= n; i++) (ans ^= a[i] + a[x]) ^= a[i] + y;
a[x] = y;
printf("%d\n", ans);
}
}
return 0;
}