嘤嘤不想求异或喵【牛客tracker 每日一题】
嘤嘤不想求异或喵
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
嘤嘤有两个整数l , r l,rl,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 TT行，每行输入两个正整数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解题思路
本题核心是前缀异或性质 + 周期性规律，高效解决超大范围、高频率查询的区间异或问题。根据异或运算特性，区间[ l , r ] [l,r][l,r]的异或和 =1 ∼ r 1\sim r1∼r的异或和⊕ \oplus⊕1 ∼ l − 1 1\sim l-11∼l−1的异或和。而1 ∼ x 1\sim x1∼x的异或和存在固定4周期规律：x m o d 4 = 0 x\mod4=0xmod4=0时结果为x xx，= 1 =1=1时为1 11，= 2 =2=2时为x + 1 x+1x+1，= 3 =3=3时为0 00。该规律可O ( 1 ) O(1)O(1)计算结果，无需遍历。搭配快速IO优化，算法时间复杂度O ( T ) O(T)O(T)，完美适配T ≤ 2 × 10 5 T≤2×10^5T≤2×105、数值达10 18 10^{18}1018的严苛约束。
总结
核心逻辑：区间异或和转化为两个前缀异或的异或，用4周期规律实现O(1)计算。
关键操作：封装O(1)前缀异或函数、运用区间异或公式、快速处理多组查询。
效率保障：常数级运算+线性处理查询，轻松应对百万级查询与超大数值范围。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;llgetxor(ll x){if(x<0)return0;ll mod=x%4;if(mod==0)returnx;if(mod==1)return1;if(mod==2)returnx+1;return0;}voidsolve(){ll l,r;cin>>l>>r;cout<<(getxor(r)^getxor(l-1))<<'\n';}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll t;cin>>t;while(t--)solve();return0;}