3 条题解

  • 3
    @ 2026-10-23 10:54:05

    提供一个 O(nlogV)O(nlogV) 的做法

    Solution

    首先一个重要的性质: $\text{对于 }x=0,1,2\dots,x \text{ 在二进制第 }k\text{ 位上的数变化呈周期性。}$ 如:

    k=1:0,0,1,1,0,0,1,1,0,0,1,1…k=1:0,0,1,1,0,0,1,1,0,0,1,1\dots

    k=2:0,0,0,0,1,1,1,1,0,0,0,0…k=2:0,0,0,0,1,1,1,1,0,0,0,0\dots

    k=3:0,0,0,0,0,0,0,0,1,1,1,1,1…k=3:0,0,0,0,0,0,0,0,1,1,1,1,1\dots

    所以我们可以预处理出 对于每个 ai,(ai+x)&2j 的值 \text{对于每个 }a_i,(a_i+x)\&2^j\text{ 的值 }

    for(int i=1;i<=n;i++){
    		cin>>a[i];
    		for(int j=0;j<L;j++){
    			int x=a[i]%(1<<j),t=a[i]/(1<<j);
    			if(t&1){
    				c[(1<<j)-x][j]++;
    				c[1<<j][j]--;
    			}
    			else{
    				c[0][j]++;
    				c[(1<<j)-x][j]--;
    			}
    		}
    	}
    	for(int j=0;j<L;j++)
    		for(int i=1;i<(1<<j);i++)
    			c[i][j]+=c[i-1][j];
    

    其中c[x][j]表示 $\text{满足 }(a_i+x)\&2^j=x\&2^j\text{ 的 }a_i\text{ 的个数}$ ,时间复杂度为 O(nlogV)O(nlogV)

    对于每次操作 AA ,用偏移量 delatdelat 累加 xx ,每次询问时,通过 cc 数组 O(1)O(1) 统计。

    Code

    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10,L=20,mod=1<<16;
    int n,m;
    long long ans;
    int a[N],c[1<<L][L];
    int main(){
    	ios::sync_with_stdio(0);
    	cin.tie(0);
    	cout.tie(0);
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    		for(int j=0;j<L;j++){
    			int x=a[i]%(1<<j),t=a[i]/(1<<j);
    			if(t&1){
    				c[(1<<j)-x][j]++;
    				c[1<<j][j]--;
    			}
    			else{
    				c[0][j]++;
    				c[(1<<j)-x][j]--;
    			}
    		}
    	}
    	for(int j=0;j<L;j++)
    		for(int i=1;i<(1<<j);i++)
    			c[i][j]+=c[i-1][j];
    	int x,delta=0;
    	string op;
    	while(m--){
    		cin>>op>>x;
    		if(op[0]=='A')
    			delta=(delta+x)%mod;
    		else{
    			int t=delta/(1<<x);
    			int s=delta%(1<<x);
    			if(t&1) ans+=c[s][x];
    			else ans+=n-c[s][x];
    		}
    	}
    	cout<<ans;
    	return 0;
    }
    
    • 0
      @ 2026-10-24 9:59:39

      SOLUTION

      显然直接放到值域上考虑,令 V=65536V=65536。

      题目所述其实就是第 ii 位是 11 的数的数量。

      观察 i=0i=0,得这样的数有:

      x∈1,3,5,7,9,11,13,15,...x \in {1,3,5,7,9,11,13,15,...}

      观察 i=1i=1:

      x∈2,3,6,7,10,11,14,15,18,19,22,23,...x \in {2,3,6,7,10,11,14,15,18,19,22,23,...}

      更一般地,对于 i=ti=t:

      x∈[2t+1k+2t,2t+1k+2t+1−1],k∈Nx \in [2^{t+1}k+2^t,2^{t+1}k+2^{t+1}-1],k \in \N

      可以发现,xx 所在的是一段一段的前缀和,考虑预处理出 si,j,fi,js_{i,j},f_{i,j},其中 si,js_{i,j} 代表要求的是第 jj 位,以 ii 为结尾的 xx 的数量,fi,jf_{i,j} 是以 ii 为开头的,其他同理。

      在修改操作时维护偏移量 deltadelta,查询时令 V′V' 为 VV 偏移到的位置,于是答案就是 sV′,i+fV′+1,is_{V',i}+f_{V'+1,i}。

      总复杂度为预处理与查询 O(M+Vlog⁡V)O(M+V \log V)。

      CODE

      #include<bits/stdc++.h>
      using namespace std;
      #define int long long
      #define fi first
      #define se second
      int T,n,m;
      int N=65536;
      int a[101000],s[101000][17],f[101000][17];
      int del=0;
      signed main(){
          ios::sync_with_stdio(0);
          cin.tie(0),cout.tie(0);
          cin>>n>>m;
          for(int i=1;i<=n;i++){
              int x;
              cin>>x;
              a[x+1]++;
          }
          for(int i=1;i<=N;i++){
              s[i][0]=s[i-1][0]+a[i];
              for(int j=1;j<=16;j++){
                  s[i][j]=s[max(0ll,i-(1<<j))][j]+s[i][0]-s[max(0ll,i-(1<<(j-1)))][0];
              }
          }
          for(int i=N;i>=1;i--){
              for(int j=1;j<=16;j++){
                  f[i][j]=f[min(N+1,i+(1<<j))][j]+s[min(N+1,i+(1<<j))-1][0]-s[min(N+1,i+(1<<(j-1)))-1][0];
              }
          }
          int ans=0;
          while(m--){
              char op;
              int x;
              cin>>op>>x;
              if(op=='A') del=(del+x)%N;
              else{
                  if(x>=16) continue;
                  int t=(N-1-del+N)%N+1;
                  ans+=s[t][x+1]+f[t+1][x+1];
              }
          }
          cout<<ans<<'\n';
          return 0;
      }
      
      • 0
        @ 2026-10-23 8:16:49

        洛谷P4641 [BJWC2008] 序列

        • 1

        信息

        ID
        937
        时间
        1000ms
        内存
        256MiB
        难度
        9
        标签
        (无)
        递交数
        147
        已通过
        8
        上传者