Poi 的新加法（Easy Version）【牛客tracker 每日一题】

Poi 的新加法（Easy Version）

时间限制：2秒 空间限制：128M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

本题为问题的简单版本，两题的唯一区别在于询问的次数及询问的数据范围。

P o i PoiPoi发明了一种新的加法：二进制只进位加法（下文用f ( x , y ) f(x,y)f(x,y)指代）。在这种加法下（为了便于理解，本表中数字使用二进制表达）：

需要注意的是，我们只考虑一次进位，即不考虑进位造成的其他位的变动导致的再次进位，比如f ( 11 , 01 ) = 10 f(11,01)=10f(11,01)=10。

简而言之，f ( x , y ) = x + y − ( x ⊕ y ) f(x,y)=x+y−(x⊕y)f(x,y)=x+y−(x⊕y)，其中⊕ ⊕⊕代表二进制按位异或运算。

现在，给定一个长度为n nn的序列{ a 1 , a 2 , … , a n } \{a_1,a_2,…,a_n\}{a1​,a2​,…,an​}。你需要处理q qq个查询，每个查询会给定l ll和r rr，求解：

f ( f ( f ( ⋯ f ( f ( a l , a l + 1 ) , a l + 2 ) , ⋯ ) , a r − 1 ) , a r ) f(f(f(⋯f(f(a_l,a_{l+1}),a_{l+2}),⋯),a_{r−1}),a_r)f(f(f(⋯f(f(al​,al+1​),al+2​),⋯),ar−1​),ar​)

输入描述：

每个测试文件均包含多组测试数据。第一行输入一个整数T ( 1 ≤ T ≤ 10 6 ) T(1≤T≤10^6)T(1≤T≤106)代表数据组数，每组测试数据描述如下：
第一行输入两个整数n , q ( 1 ≤ n ≤ 10 6 ; q = 1 ) n,q(1≤n≤10^6; q=1)n,q(1≤n≤106;q=1)，代表序列中的元素个数、查询次数。
第二行输入n nn个整数a 1 , a 2 , … , a n ( 0 ≤ a i < 2 60 ) a_1,a_2,…,a_n(0≤a_i<2^{60})a1​,a2​,…,an​(0≤ai​<260)，代表序列中的元素。
此后q qq行，第i ii行输入两个整数l i , r i ( l i = 1 ; r i = n ) l_i,r_i(l_i=1; r_i=n)li​,ri​(li​=1;ri​=n)，代表第i ii次询问的区间。

除此之外，保证单个测试文件的n nn之和不超过10 6 10^6106，q qq之和不超过10 6 10^6106。

输出描述：

对于每个查询，新起一行。输出一个整数，代表该次查询的结果。

示例1

输入：

3 2 1 1 1 1 2 3 1 2 3 3 1 3 5 1 31 31 31 31 31 1 5

输出：

2 0 48

解题思路

本题核心是新加法公式化简+顺序迭代计算，高效解决区间运算问题。首先通过位运算公式推导，将题目定义的新加法简化为核心规律：f ( x , y ) = 2 × ( x & y ) f(x,y)=2 \times (x \& y)f(x,y)=2×(x&y)，即两数按位与后左移一位。题目中所有查询均为整个序列区间[ 1 , n ] [1,n][1,n]，因此无需预处理数据结构，直接顺序遍历序列计算即可：以第一个元素为初始值，依次对后续每个元素执行当前结果与元素按位与，再左移一位的操作，遍历完成后得到的数值就是最终答案。算法时间复杂度为O ( n ) O(n)O(n)，完美适配大数据量的时间与空间约束。

总结

核心逻辑：化简新加法为2 ∗ ( x & y ) 2*(x\&y)2∗(x&y)，顺序遍历区间完成迭代运算。
关键操作：位运算公式推导、顺序迭代计算区间嵌套新加法结果。
效率保障：线性时间复杂度，无额外空间开销，高效处理大规模输入。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e6+10;constll p=1e9+7;constll INF=1e18;constll M=1e6+10;ll a[N];voidsolve(){ll n,q;cin>>n>>q;for(ll i=1;i<=n;i++)cin>>a[i];while(q--){ll l,r,ans;cin>>l>>r;ans=a[l];for(ll i=l+1;i<=r;i++)ans=(ans&a[i])<<1;cout<<ans<<endl;}}intmain(){ll t=1;cin>>t;while(t--)solve();return0;}