题解：CF2071D2 Infinite Sequence (Hard Version)

未来姚班zyl · 2025-03-05 15:26:30 · 题解

先差分转为前缀和。

D1

由于向下取整对相邻两个数 2x 与 2x+1 是相同的，所以对于 2x>n，有 a_{2x}=a_{2x+1}。

把 n 补为奇数，设前 n 个 a_i 的异或和为 P。我们发现，从 n 之后，a 的组成变为两个两个相同的数顺次相接，它们会在异或和中两两抵消，最终最多剩一个多余的，所以：

对于 a_m，设 d=\lfloor\frac{m}{2}\rfloor，则：

递归即可做到 O(n+\log V)。

D2

差分转前缀和是习惯。

在 D1 的基础上，我们先把前 2n+1 个位置补齐，并处理对应的前缀和与前缀异或和。因为对于大于 2n+1 的位置 m，\lfloor\frac{m}{2}\rfloor>n，其形式将更加统一。

经过简单的草稿发现，从 a_{2n+2} 开始，数组的形式如下：

即按照 \bmod 4 分组，每组前两个是 P\oplus a_{x}，后两个是 P，而 x 从第一组开始依次加二。

将 r 调整到一组的末尾，求的就是这些组的前缀和。

于是我们可以将 a_{2n+1} 之前的前缀和预处理，a_{2n+2}\sim r 递归到 a_{n+1}\sim a_{\lfloor\frac{r}{2}\rfloor-1} 中偶数位置的和。

偶数位置前缀和，对于 i\le 2n+1，可以预处理前缀和，对于 i>2n+1，相当于把两两相等的位置合并，本质求法相同。

总复杂度 O(n+\log^2 V)。

#include<bits/stdc++.h>
#define ll long long
#define int ll
#define L x<<1
#define R x<<1|1
#define mid ((l+r)>>1)
#define lc L,l,mid
#define rc R,mid+1,r
#define Root 1,1,n
#define OK Ll<=l&&r<=Rr
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define repn(x) rep(x,1,n)
#define repm(x) rep(x,1,m)
#define pb push_back
#define e(x) for(int i=h[x],y=to[i];i;i=nxt[i],y=to[i])
#define E(x) for(auto y:p[x])
#define Pi pair<int,int>
#define ui unsigned ll
inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57) {if(c=='-') w=-1;c=getchar();}while(c>=48&&c<=57)s=(s<<1)+(s<<3)+c-48,c=getchar();return s*w;}
inline void pf(int x){if(x<0) putchar('-'),x=-x;if(x>9)pf(x/10);putchar(x%10+48);}
using namespace std;
const int N=5e5+5,M=1e6+5,inf=(1LL<<30)-1,mod=998244353;
const ll llf=1e18;
inline void add(int &a,int b){((a+=b)>=mod) and (a-=mod);}
inline int Add(int a,int b){return add(a,b),a;}
inline int mul(int a,int b){return 1LL*a*b%mod;}
inline void Mul(int &a,int b){a=mul(a,b);}
inline void red(int &a,int b){add(a,mod-b);}
inline int Red(int a,int b){return red(a,b),a;}
inline int qp(int a,ll b){if(!b)return 1;int c=qp(a,b>>1LL);Mul(c,c);if(b&1)Mul(c,a);return c;}
inline int INV(int x){return qp(x,mod-2);}
int n,l,r,a[N],xr[N],pr[N],P,pe[N];
inline int Get(int x){
    if(x<=n*2+1)return a[x];
    if(x/2<=n*2+1)return xr[x/2];
    if(x/2%2==1)return P;
    return P^Get(x/2);
}
inline int calc(int r){
    if(r<=n*2+1)return pe[r]-pe[n-1];
    int ans=pe[n*2]-pe[n-1];
    while(r%4!=2)r+=2,ans-=Get(r);
    if(P)ans+=(r-n*2)/2,ans-=calc(r/2-1);
    else ans+=calc(r/2-1);
    return ans;
}
inline int Calc(int r){
    if(r<=n*2+1)return pr[r];
    int ans=pr[n*2+1];
    while(r%4!=3)r++,ans-=Get(r);
    int ps=n*2+5,Ct=(r-ps)/4+1;
    if(P)ans+=(r-(n*2+1)),ans-=calc(r/2-1)*2;
    else ans+=calc(r/2-1)*2;
    return ans;
}
inline void Main(){
    n=read(),l=read(),r=read();
    repn(i)a[i]=read(),xr[i]=xr[i-1]^a[i],pr[i]=pr[i-1]+a[i];
    if(n%2==0)n++,a[n]=xr[n/2],pr[n]=pr[n-1]+a[n],xr[n]=xr[n-1]^a[n];
    P=xr[n];
    rep(i,n+1,n*2+1)a[i]=xr[i/2],xr[i]=xr[i-1]^a[i],pr[i]=pr[i-1]+a[i];
    for(int i=2;i<=n*2+1;i+=2)pe[i]=pe[i-2]+a[i];
    cout <<Calc(r)-Calc(l-1)<<'\n';
}
signed main(){
    int T=read();
    while(T--)Main();
    return 0;
}