典型とはいえだんだん面倒な典型になってきた。
https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_j
問題
整数と加算・乗算からなる式が与えられる。
以下のクエリに順次答えよ。
- 1か所数値を書き換える
- 1か所加算と乗算の演算子を逆にする
- 部分文字列に対し、数式の計算結果を答える
解法
SegTreeを構成し、各ノードに以下のいずれかの形で数値を持たせよう。
- 単一の値A
- 3つの値(A,B,C)でA+B+Cを意味する
横のノードと乗算で連結する場合、AやCは掛け算でかかるようにすればよい。
すなわち、
- (A,B,C)*(A',B',C') = (A, B+CA'+B', C')
- (A,B,C)+(A',B',C') = (A, B+C+A'+B', C')
のように連結される。
int N,Q; int A[202020]; string S; ll mo=1000000007; template<int NV> class SegTree_3 { public: vector<vector<ll>> val; SegTree_3(){ int i; val.resize(NV*2); }; vector<ll> merge(vector<ll> a,vector<ll> b,int id) { char op='+'; if(id<S.size()) op=S[id]; if(a.empty()) return b; if(b.empty()) return a; if(op=='*') { if(a.size()==1&&b.size()==1) { return {a[0]*b[0]%mo}; } else if(a.size()==3&&b.size()==1) { return {a[0],a[1],a[2]*b[0]%mo}; } else if(a.size()==1&&b.size()==3) { return {a[0]*b[0]%mo,b[1],b[2]}; } else{ return {a[0],(a[1]+a[2]*b[0]+b[1])%mo,b[2]}; } } else { if(a.size()==1&&b.size()==1) { return {a[0],0,b[0]}; } else if(a.size()==3&&b.size()==1) { return {a[0],(a[1]+a[2])%mo,b[0]}; } else if(a.size()==1&&b.size()==3) { return {a[0],(b[0]+b[1])%mo,b[2]}; } else { return {a[0],(a[1]+a[2]+b[0]+b[1])%mo,b[2]}; } } } vector<ll> getval(int x,int y,int l=0,int r=NV,int k=1) { int m=(l+r)/2; if(r<=x || y<=l) return {}; if(x<=l && r<=y) return val[k]; auto a=getval(x,y,l,(l+r)/2,k*2); auto b=getval(x,y,(l+r)/2,r,k*2+1); return merge(a,b,m-1); } void update(int x,int y, ll v,int l=0,int r=NV,int k=1) { if(l>=r) return; if(x<=l && r<=y) { val[k]={v}; } else if(l < y && x < r) { update(x,y,v,l,(l+r)/2,k*2); update(x,y,v,(l+r)/2,r,k*2+1); val[k]=merge(val[k*2],val[k*2+1],(l+r)/2-1); } } }; SegTree_3<1<<20> st; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>A[i]; cin>>S; FOR(i,N) st.update(i,i+1,A[i]); cin>>Q; while(Q--) { cin>>i>>x>>y; if(i==1) { x--; A[x]=y; st.update(x,x+1,A[x]); } else if(i==2) { x--; S[x]=(char)('*'+'+'-S[x]); st.update(x+1,x+2,A[x+1]); } else { auto a=st.getval(x-1,y); ll ret=0; FORR(v,a) ret+=v; cout<<ret%mo<<endl; } } }
まとめ
ここらへんさっと解けるの、タコヤキオイシクナーレで苦戦していたのが昔のようだ。