洛谷P6225 异或橙子
位运算 思维 树状数组
思路
先看一下这个式子要干什么
例如 \(l=2,u=4\) 的情况，记橙子序列 \(A\) 中第 \(i\) 个橙子的整数是 \(a_i\)，那么他要求的就是：
\[a_2 \oplus a_3 \oplus a_4 \oplus (a_2\oplus a_3)\oplus(a_3\oplus a_4)\oplus(a_2\oplus a_3 \oplus a_4) \]也就是说，对于每一个连续的区间，我们都要或一下，注意一共有\(\frac{n(n + 1)}{2}\)个区间，暴力遍历是\(O(n^2)\)的复杂度肯定会超时
对于这样的所有连续的区间的问题，我们可以考虑每一个元素的贡献是多少。因为是异或运算，所以如果一个元素贡献的次数是偶数次的话相当于没有这个数，贡献的次数是奇数的话相当于就出现了一次
现在我们来看每个元素贡献了多少次
\(a_1, a_2, a_3, a_4, a_5 \dots a_n\)
-
\(a_1\)贡献的区间有\((a_1), (a_1, a_2), (a_1, a_2, a_3), \dots (a_1, a_2, a_3 \dots a_n)\), \(a_1\)贡献了\(n\)次
-
\(a_2\)贡献的区间有\((a_2), (a_2, a_3), (a_2, a_3, a_4), \dots (a_2, a_3, a_4 \dots a_n)\), 有\(n - 2\), 再加上\(a_1\)贡献的区间中包含\(a_2\)的,一共是\((n - 1) * 2\)个\(\dots\)，以此类推，对于一个位置\(i\)，会贡献\((n - i + 1) * i\)次
接着我们还能发现，如果区间长度为偶数时，贡献的次数全都是偶数，结果直接就是\(0\)，区间长度为奇数时，当\(left\)（区间左端点）为奇数时，只有奇数位置有贡献，否则就只有偶数位置有贡献
用两个树状数组分别维护偶数位置和奇数位置就好了
代码
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define lowbit(x) x & -x
const int maxn = 2e5 + 5;
const int inf = 0x7f7f7f7f;
const int mx = 2e5 + 1;
struct custom_hash
{
static uint64_t splitmix64(uint64_t x)
{
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
return x;
}
size_t operator () (uint64_t x) const
{
static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count(); // 时间戳
return splitmix64(x + FIXED_RANDOM);
}
};
// a1, a2, a3, ....... , an有n个数，这 n * (n - 1) / 2 个区间中每一个元素被算了几次
int fenwick1[maxn], fenwick2[maxn];
// fenwick1 奇数位置
// fenwick2 偶数位置
void modify(int t[], int pos, int v)
{
while(pos <= mx)
{
t[pos] ^= v;
pos += lowbit(pos);
}
}
int query(int pos, int t[])
{
int res = 0;
while(pos)
{
res ^= t[pos];
pos -= lowbit(pos);
}
return res;
}
int single_query(int pos, int t[])
{
return query(pos, t) ^ query(pos - 1, t);
}
int range_query(int l, int r, int t[])
{
return query(r, t) ^ query(l - 1, t);
}
void solve()
{
int odd = 0, even = 0;
int n = 0, m = 0;
std::cin >> n >> m;
int tmp = 0;
for (int i = 1; i <= n; i++)
{
std::cin >> tmp;
if (i & 1)
{
modify(fenwick1, ++odd, tmp);
}
else
{
modify(fenwick2, ++even, tmp);
}
}
int op = 0, x = 0, y = 0;
for (int i = 1; i <= m; i++)
{
std::cin >> op >> x >> y;
if (op == 1)
{
int id = 0;
if (x & 1)
{
id = x / 2 + 1;
int delta = y ^ single_query(id, fenwick1);
modify(fenwick1, id, delta);
}
else
{
id = x / 2;
int delta = y ^ single_query(id, fenwick2);
modify(fenwick2, id, delta);
}
}
else
{
int tot = y - x + 1;
if (tot & 1)
{
if (x & 1)
{
int id1 = x / 2 + 1, id2 = y / 2 + 1;
std::cout << range_query(id1, id2, fenwick1) << endl;
}
else
{
int id1 = x / 2, id2 = y / 2;
std::cout << range_query(id1, id2, fenwick2) << endl;
}
}
else
{
std::cout << 0 << endl;
}
}
}
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);
//freopen("out.txt", "w", stdout);
int t = 1;
//std::cin >> t;
while(t--)
{
solve();
}
return 0;
}