题解：CF2071D1 Infinite Sequence (Easy Version)

· · 题解

异或前缀和 + 性质挖掘 + 递归

设 s 数组为 a 数组的异或前缀和，即 s_i=\oplus_{k=1}^i a_k。

显然当 m \le n 时直接输出 a_i 即可。所以本题难点自然是在于 m \gt n 的部分如何求。

由题意当 m \gt n 时，\large a_m=s_{\lfloor \frac{m}{2} \rfloor}。

当 i 为奇数时：显然 \lfloor \frac{i}{2} \rfloor= \lfloor \frac{i-1}{2} \rfloor，又当 m \gt n 时 \large a_m=s_{\lfloor \frac{m}{2} \rfloor}，故当 i-1 \gt n 且 i 为奇数时有 a_{i}=a_{i-1}。

根据 s 数组的递推定义：s_i=s_{i-1} \oplus a_i。结合刚刚分析的性质，当 i 为奇数且 i-1 \gt n 时：有 a_i=a_{i-1}，为了用上这个条件于是将 s_i=s_{i-1} \oplus a_i 转化为 s_i=s_{i-2} \oplus a_{i-1} \oplus a_i，而 a_{i-1}=a_i，故 s_i=s_{i-2}。

即对于所有 \ge n 的奇数项都相等。（因为当 n 为偶数时，s_{n+1},s_{n+2},\dots 均相等；当 n 为奇数时，s_n,s_{n+1},\cdots 均相等。）

接着考虑当 i \gt n 且 i 为偶数时：s_{i}=s_{i-1} \oplus a_i，因为 i \gt n，故 s_i=s_{i-1} \oplus s_{\lfloor \frac{m}{2} \rfloor}，其中 s_{i-1} 是确定的值，就等于第一个 \ge n 的奇数项对应的值，而 s_{\lfloor \frac{m}{2} \rfloor} 则可继续递归得到，显然递归层数最多也只有 \log 层。

时间复杂度 O(n +\log l)。

#define rep(x,y,z) for(int x=y;x<=z;x++)
typedef long long LL;
const int N=2e5+5;
LL n,l,r;
int a[N];
LL prexor[N];
LL dfs(LL now){ // 递归首层求>n的now对应的值a[now],由于a[now]=prexor[now/2],进而不断递归求解
    if(now<=n) return prexor[now];
    else if(now/2<=n) return dfs(now/2);
    now/=2;
    LL odd;
    if(n&1) odd=prexor[n];
    else odd=prexor[n]^dfs(n+1);
    if(now&1) return odd;
    else return odd^dfs(now);
}
void solve(){
    cin>>n>>l>>r;
    rep(i,1,n) cin>>a[i];
    rep(i,1,n) prexor[i]=prexor[i-1]^a[i];
    if(l<=n) return cout<<a[l],void();
    cout<<dfs(l);
}