いろはちゃんコンテスト Day2 : J - ライ麦畑で待ちながら

典型とはいえだんだん面倒な典型になってきた。
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;
		}
	}
	
	
}

まとめ

ここらへんさっと解けるの、タコヤキオイシクナーレで苦戦していたのが昔のようだ。