自动搬运

查看原文

来自洛谷，原作者为

	shinzanmono QQ: 2162579766||欢歌载舞，交换比特，共同庆祝

搬运于2025-08-24 23:16:41，当前版本为作者最后更新于2025-05-24 18:16:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

设 $P=\lfloor\log_2 n\rfloor$，则 $\sum_{i=0}^P2^i=O(n)$。而所有修改操作都是全局操作，说明 $a_i$ 的系数和后来加上的值均相同。

设 $f_{i,j}$ 表示满足 $x \bmod 2^i=j$ 的位置的 $a_x$ 和。显然 $f_{i,j}=f_{i+1,j}+f_{i+1,j+2^i}$，即可 $O(n)$ 预处理。

维护两个懒标记 $add$ 和 $mul$，每次全局加操作直接改变 $add$，全局乘要对 $add$ 和 $mul$ 都 $\times x$。答案即为 $f_{i,j}\times mul+add\times C(i,j)$，$C(i,j)$ 表示 $x\bmod 2^i=j$ 的位置的个数。

#include<iostream>
#include<algorithm>
const int sz=4e7+10;
const int mod=998244353;
unsigned X,Y,Z;
unsigned rnd(){
  X^=Y<<(Z&31),Y^=Z>>(X&31),Z^=X<<(Y&31);
  X^=X>>5,Y^=Y<<17,Z^=Z>>6;
  return X;
}
int a[sz],b[sz<<1],*ptr=b,*sum[30];
int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n,q,vl,vr;
  std::cin>>n>>q>>vl>>vr>>X>>Y>>Z;
  for(int i=0;i<n;i++)a[i]=rnd()%mod;
  int p=std::__lg(n);
  sum[p]=ptr;
  for(int i=0;i<1<<p;i++){
    for(int j=i;j<n;j+=1<<p)sum[p][i]+=a[j];
    sum[p][i]%=mod,ptr++;
  }
  for(int k=p-1;k>=0;k--){
    sum[k]=ptr;
    for(int i=0;i<1<<k;i++)sum[k][i]=(sum[k+1][i]+sum[k+1][i+(1<<k)])%mod,ptr++;
  }
  auto cnt=[&](int k,int p){return n/(1<<k)+(p<n%(1<<k));};
  long long ans=0,addtag=0,multag=1;
  while(q--){
    int op=rnd()%3,x,y;
    if(op==0)x=rnd()%mod,addtag=(addtag+x)%mod;
    if(op==1)x=rnd()%mod,multag=multag*x%mod,addtag=addtag*x%mod;
    if(op==2)x=rnd()%(vr-vl+1)+vl,y=rnd()%(1<<x),ans^=(sum[x][y]*multag+cnt(x,y)*addtag)%mod;
  }
  std::cout<<ans<<"\n";
  return 0;
}