嘤嘤不想求异或喵【牛客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\mod40xmod40时结果为x xx 1 11时为1 11 2 22时为x 1 x1x1 3 33时为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)前缀异或函数、运用区间异或公式、快速处理多组查询。效率保障常数级运算线性处理查询轻松应对百万级查询与超大数值范围。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;llgetxor(ll x){if(x0)return0;ll modx%4;if(mod0)returnx;if(mod1)return1;if(mod2)returnx1;return0;}voidsolve(){ll l,r;cinlr;cout(getxor(r)^getxor(l-1))\n;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll t;cint;while(t--)solve();return0;}