P8891 「UOI-R1」询问
Infinite_Eternity
·
·
题解
Description
「UOI-R1」询问
给定 n 个数的整数序列 a_1, a_2, \cdots, a_n，有 m 次操作，每次操作给定 x, y。对于所有满足 i \oplus x = 0 的 i，使得 a_i \gets a_i - y。
数据范围：1 \leq n, m \leq 10^6，-10^8 \leq y, a_i \leq 10^{8}，0 \leq x \leq n。
Analysis
> 将两个数用二进制进行表示后，对于每一位进行运算：若不同则为 $1$，相同则为 $0$。
即：
$$
\begin{aligned}
0 \oplus 0 = 0\\
0 \oplus 1 = 1\\
1 \oplus 0 = 1\\
1 \oplus 1 = 0
\end{aligned}
$$
该运算被也广泛运用来统计一个数中 $1$ 的位数。
------------
对于本题，我们便可从 $i \oplus x = 0$ 这个条件入手。根据 $\oplus$ 的运算法则可得：当且仅当 $i = x$ 时，这个条件才能被满足。
因此，我们每次操作只需对 $a_x$ 进行操作即可。此外，因为本题的数据范围会爆 `int`，谨记要开 `long long`。
时间复杂度 $\mathcal{O}(m)$。
# Code
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,x,y,a[1000001];
inline ll read()
{
register char c;
register int ans=0,z=1;
while(!isdigit(c=getchar()))z-=2*(c=='-');
do
{
ans=((ans<<3)+(ans<<1)+c-'0');
}
while(isdigit(c=getchar()));
return ans*z;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;++i)
a[i]=read();
while(m--)
{
x=read(),y=read();
a[x]-=y;
}
for(int i=1;i<=n;++i)
printf("%lld ",a[i]);
return 0;
}
```
### 彩蛋
