結果
問題 | No.2265 Xor Range Substring Sum Query |
ユーザー |
![]() |
提出日時 | 2023-03-10 10:24:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 445 ms / 5,000 ms |
コード長 | 1,653 bytes |
コンパイル時間 | 1,788 ms |
コンパイル使用メモリ | 198,892 KB |
最終ジャッジ日時 | 2025-02-11 07:16:42 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/modint>#define elif else ifusing mint=atcoder::modint998244353;mint pow11[1<<18];mint pow2[1<<18];mint node[10][1<<18];mint calc(mint fL,int Lsize,mint fR,int Rsize){return fL*pow11[Rsize]+fR*pow2[Lsize];}void merge(int i,int j){int L=j;int R=L^(1<<(i-1));node[i][L]=calc(node[i-1][L],1<<(i-1),node[i-1][R],1<<(i-1));}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin>>n;int N=1<<n;int m=n/2;string S;cin>>S;for(int i=0;i<N;i++){node[0][i]=S[i]-'0';}pow11[0]=1;pow2[0]=1;for(int i=1;i<=N;i++){pow11[i]=pow11[i-1]*11;pow2[i]=pow2[i-1]*2;}for(int i=0;i<m;i++){for(int j=0;j<N;j++){merge(i+1,j);}}int q,t,x,y,L,R,X,s,l,r;cin>>q;for(int tc=0;tc<q;tc++){cin>>t;if(t==1){cin>>x>>y;node[0][x]=y;for(int i=0;i<m;i++){s=1<<(i+1);l=(x/s)*s;r=l+s;for(int j=l;j<r;j++){merge(i+1,j);}}}else{cin>>L>>R>>X;R++;mint res=0;int size=0;for(int i=0;i<m;i++){if(((L>>i)&1)&&(L+(1<<i)<=R)){res=calc(res,size,node[i][L^X],1<<i);L+=1<<i;size+=1<<i;}}s=(1<<m);while(L+s<=R){res=calc(res,size,node[m][L^X],s);L+=s;size+=s;}for(int i=m-1;i>=0;--i){if(L+(1<<i)<=R){res=calc(res,size,node[i][L^X],1<<i);L+=1<<i;size+=1<<i;}}cout<<res.val()<<'\n';}}}