嘤嘤不想求异或喵
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！ 
题目描述
嘤嘤有两个整数
l
,
r
l,r
l,r ，她想知道区间
[
l
,
r
]
[l,r]
[l,r] 所有整数的异或和是多少喵~。
输入描述：
第一行输入一个正整数
T
(
1
≤
T
≤
2
×
10
5
)
T(1≤T≤2×10^5)
T(1≤T≤2×105) ，表示询问次数。
接下来
T
T
T 行，每行输入两个正整数
l
,
r
(
1
≤
l
≤
r
≤
10
18
)
l,r(1≤l≤r≤10^{18})
l,r(1≤l≤r≤1018) 表示询问。
输出描述：
对于每个询问，在一行中输出一个整数表示答案。
示例1
输入：
3
1 1
1 2
1 3
输出：
1
3
0
解题思路
本题要求在最多
2
×
10
5
2 \\times 10^5
2×105 次询问中，快速求出任意区间
[
l
,
r
]
[l, r]
[l,r] 内所有整数的异或和，其中
l
,
r
l, r
l,r 可高达
10
18
10^{18}
1018。暴力遍历区间显然不可行，必须利用异或运算的数学性质和周期性规律来实现
O
(
1
)
O(1)
O(1) 查询。
1. 异或前缀和技巧
对于任意区间
[
l
,
r
]
[l, r]
[l,r] 的异或和，可以利用前缀异或数组简化计算。定义：
f
(
x
)
=
1
⊕
2
⊕
3
⊕
⋯
⊕
x
f(x) = 1 \\oplus 2 \\oplus 3 \\oplus \\cdots \\oplus x
f(x)=1⊕2⊕3⊕⋯⊕x
即从
1
1
1 到
x
x
x 的异或结果。那么区间
[
l
,
r
]
[l, r]
[l,r] 的异或和就等于：
[
l
,
r
]
⊕
=
f
(
r
)
⊕
f
(
l
−
1
)
[l, r]_{\\oplus} = f(r) \\oplus f(l-1)
[l,r]⊕=f(r)⊕f(l−1)
这是因为异或运算满足结合律，且
a
⊕
a
=
0
a \\oplus a = 0
a⊕a=0，将
1
…
r
1 \\dots r
1…r 的异或结果异或上
1
…
(
l
−
1
)
1 \\dots (l-1)
1…(l−1) 的异或结果，就会消去
1
…
l
−
1
1 \\dots l-1
1…l−1 部分的贡献，剩下
l
…
r
l \\dots r
l…r 的部分。
因此，原问题转化为：快速计算
f
(
x
)
f(x)
f(x) 的值，其中
x
x
x 可以为任意正整数（甚至
0
0
0，此时
f
(
0
)
=
0
f(0)=0
f(0)=0）。
2. 找出
f
(
x
)
f(x)
f(x) 的规律
直接计算
f
(
x
)
f(x)
f(x) 需要
O
(
x
)
O(x)
O(x) 的时间，依然不可接受。我们尝试写出前若干项，观察是否存在周期性规律：
| 0 | 0 |
| 1 | 1 |
| 2 | 1
⊕ \\oplus ⊕ 2 = 3 |
| 3 | 3
⊕ \\oplus ⊕ 3 = 0 |
| 4 | 0
⊕ \\oplus ⊕ 4 = 4 |
| 5 | 4
⊕ \\oplus ⊕ 5 = 1 |
| 6 | 1
⊕ \\oplus ⊕ 6 = 7 |
| 7 | 7
⊕ \\oplus ⊕ 7 = 0 |
| 8 | 0
⊕ \\oplus ⊕ 8 = 8 |
| 9 | 8
⊕ \\oplus ⊕ 9 = 1 |
| 10 | 1
⊕ \\oplus ⊕ 10 = 11 |
| 11 | 11
⊕ \\oplus ⊕ 11 = 0 |
| 12 | 0
⊕ \\oplus ⊕ 12 = 12 |
可以观察到明显的4为周期的规律：
- 当
x
m
o
d
4
=
0
x \\bmod 4 = 0
xmod4=0 时，f
(
x
)
=
x
f(x) = x
f(x)=x - 当
x
m
o
d
4
=
1
x \\bmod 4 = 1
xmod4=1 时，f
(
x
)
=
1
f(x) = 1
f(x)=1 - 当
x
m
o
d
4
=
2
x \\bmod 4 = 2
xmod4=2 时，f
(
x
)
=
x
+
1
f(x) = x + 1
f(x)=x+1 - 当
x
m
o
d
4
=
3
x \\bmod 4 = 3
xmod4=3 时，f
(
x
)
=
0
f(x) = 0
f(x)=0
这个规律可以通过数学归纳法证明，或者由二进制位运算的性质推导得出。例如，对于任意四个连续整数
4
k
,
4
k
+
1
,
4
k
+
2
,
4
k
+
3
4k, 4k+1, 4k+2, 4k+3
4k,4k+1,4k+2,4k+3，其异或结果恒为
0
0
0，这导致了周期性出现
0
0
0 的现象。
利用该规律，我们可以用
O
(
1
)
O(1)
O(1) 时间计算出任意
f
(
x
)
f(x)
f(x)。
3. 算法步骤
- 读入
l
,
r
l, r
l,r。 - 计算
f
(
r
)
f(r)
f(r) 和f
(
l
−
1
)
f(l-1)
f(l−1) 的值（调用一个函数，根据x
m
o
d
4
x \\bmod 4
xmod4 返回相应结果）。 - 输出
f
(
r
)
⊕
f
(
l
−
1
)
f(r) \\oplus f(l-1)
f(r)⊕f(l−1)。
l
=
1
l = 1
l=1 时，
l
−
1
=
0
l-1 = 0
l−1=0，此时
f
(
0
)
f(0)
f(0) 应定义为
0
0
0，我们的函数中处理
x
≤
0
x \\le 0
x≤0 返回
0
0
0 即可。
4. 复杂度分析
- 时间：每次查询仅进行常数次算术运算和按位异或，时间复杂度
O
(
1
)
O(1)
O(1)。总时间复杂度O
(
T
)
O(T)
O(T)，完全满足T
≤
2
×
10
5
T \\le 2\\times 10^5
T≤2×105 的要求。 - 空间：仅使用若干临时变量，空间复杂度
O
(
1
)
O(1)
O(1)。
5. 代码实现细节
- 使用 long long 类型存储
x
x
x 和结果，因为r
≤
10
18
r \\le 10^{18}
r≤1018，x
x
x 可能达到10
18
10^{18}
1018，x
+
1
x+1
x+1 可能超出32
32
32 位范围，必须用 64 位整数。 - 输入输出需要快速（ios::sync_with_stdio(false); cin.tie(0);），否则可能因为
T
T
T 较大而超时。 - 封装 getxor(x) 函数实现上述规律，代码简洁清晰。
6. 总结
本题的核心是将区间异或问题转化为前缀异或问题，并利用异或运算的周期性实现
O
(
1
)
O(1)
O(1) 求解。该思路不仅适用于本题，也是处理大量区间异或查询的经典方法，值得熟练掌握。
代码内容
#include <bits/stdc++.h>
using namespace std;
#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;
ll getxor(ll x)
{
if(x<0) return 0;
ll mod=x%4;
if(mod==0) return x;
if(mod==1) return 1;
if(mod==2) return x+1;
return 0;
}
void solve()
{
ll l,r;
cin>>l>>r;
cout<<(getxor(r)^getxor(l–1))<<'\\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
ll t;
cin>>t;
while(t—) solve();
return 0;
}
