結果

問題 No.2265 Xor Range Substring Sum Query
ユーザー lgswdnlgswdn
提出日時 2023-05-04 17:09:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,844 ms / 5,000 ms
コード長 2,548 bytes
コンパイル時間 2,314 ms
コンパイル使用メモリ 198,324 KB
最終ジャッジ日時 2025-02-12 16:54:54
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:81:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   81 |   scanf("%lld%s",&n,s); int lim=(1<<n)-1;
      |   ~~~~~^~~~~~~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define fi first
#define se second
#define eb emplace_back
#define popc __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef unsigned long long ull;
typedef long double ld;

int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
  return x*w;
}

const int N=(1<<18)+9,mod=998244353,inv2=(mod+1)/2;
int n,a[N],w[N],q,t[N],tick;
char s[N];

int ksm(int x,int y,int r=1) {
  for(;y;y>>=1,x=x*x%mod) if(y&1) r=r*x%mod;
  return r;
}

namespace BLT {
  int S,b[N],c[N],l[N],id[N],tot,bs;
  vi s[520];
  void build(int p,int l,int r) {
    s[p].resize(bs);
    rep(x,0,bs-1) {
      s[p][x]=0;
      rep(j,l,r) c[j^x]=a[j];
      rep(j,l,r) s[p][x]=(s[p][x]+c[j]*w[j-l+1])%mod;
    }
  }
  void bmdf(int p,int l,int r,int x,int y) {
    rep(z,0,bs-1) {
      int pos=z^x;
      s[p][z]=(s[p][z]+y*w[pos-l+1])%mod;
    }
  }
  pii bqry(int p,int l,int r,int x,int y,int z) {
    if(r<x||l>y) return pii(0,0);
    else if(x<=l&&r<=y) return pii(r-l+1,s[p][z]);
    else {
      x=max(x,l), y=min(y,r); int cnt=0,res=0;
      rep(i,x,y) res=(res+a[i^z]*w[++cnt])%mod;
      return pii(cnt,res);
    }
  }
  void build(int n) {
    S=(1<<n)-1; bs=1<<(n/2);
    rep(i,0,S) b[i]=i/bs; tot=b[S];
    rep(i,0,tot) l[i]=i*bs;
    rep(i,0,tot) build(i,l[i],l[i]+bs-1);
  }
  void mdf(int x,int y) {
    bmdf(b[x],l[b[x]],l[b[x]]+bs-1,x,(y-a[x]+mod)%mod); a[x]=y;
  }
  int qry(int x,int y,int z) {
    int z1=z/bs, z2=z&(bs-1), cnt=0, ans=0;
    rep(i,0,tot) id[i]=i^z1;
    rep(i,0,tot) {
      int p=id[i]; int x0=max(x,l[i]), y0=min(y,l[i]+bs-1);
      if(x0>y0) continue; x0^=z1*bs, y0^=z1*bs;
      auto [c,r]=bqry(p,l[p],l[p]+bs-1,x0,y0,z2);
      if(c) ans=(ans+w[cnt]*r)%mod, cnt+=c;
    } return ans;
  }
}

signed main() {
  scanf("%lld%s",&n,s); int lim=(1<<n)-1;
  rep(i,0,lim) a[i]=s[i]-'0';
  w[0]=t[0]=1; q=2*ksm(11,mod-2)%mod;
  rep(i,1,lim+1) t[i]=t[i-1]*11%mod;
  rep(i,1,lim+1) t[i]=t[i]*ksm(2,mod-2)%mod;
  rep(i,1,lim+1) w[i]=w[i-1]*q%mod;
  BLT::build(n);
  for(int Q=read();Q;Q--) {
    int op=read();
    if(op==1) {
      int x=read(), y=read();
      BLT::mdf(x,y);
    } else {
      int l=read(), r=read(), b=read();
      int res=BLT::qry(l,r,b);
      printf("%lld\n",res*t[r-l+1]%mod);
    }
  }
  return 0;
}
0