まずは \(A\) に関する条件の存在しない次の問題を考えます。

問題：
\(B=(B_1,\ldots,B_N)\) が与えられます。\(Q\) 個のクエリが与えられるので順に処理してください。

• \(B_p\) を \(x\) に変更する
• \(B\) の区間和の最大値を出力する

解法：
この問題は次の情報 \(4\) つの情報を各ノードを持つセグメントツリーにより解くことができます。

• prefix 和の最大値 \(L\)
• suffix 和の最大値 \(R\)
• 区間和の最大値 \(M\)
• 総和 \(S\)

区間のマージは \((L_1,R_1,M_1,S_1)\cdot(L_2,R_2,M_2,S_2)=(\max(L_1,S_1+L_2),\max(R_1+S_2,R_2), \max(M_1,M_2,R_1+L_2), S_1+S_2)\) により行えます。

元の問題を考えます。先程の問題に加え \(A\) も考慮して

• \(A\) の和の \(\bmod 3\) が \(i\) であるような prefix に対応する \(B\) の和の最大値 \(L_i\)
• \(A\) の和の \(\bmod 3\) が \(i\) であるような suffix に対応する \(B\) の和の最大値 \(R_i\)
• \(A\) の和の \(\bmod 3\) が \(i\) であるような区間に対応する \(B\) の和の最大値 \(M_i\)
• \(A\) の総和、\(B\) の総和 \(S_A,S_B\)

の \(11\) 個の情報を各ノードに持たせることで同様に解くことができます。