対称性から、\(s < t\) であるクエリについて考えればよいです。

最初の移動について着目し、場合分けを行います。

まず、最初の移動でマスの番号が \(s\) より大きいマスに移動するとき、最初の移動のコストは \(R_s\) であり、コストの合計は \(R_s\) 以上です。一方、マス \(s\) からマス \(t\) に直接 \(1\) 回の移動で辿り着くとき、コストの合計が \(R_s\) となるため、この場合のコストの合計の最小値は \(R_s\) となります。

次に、最初の移動においてマスの番号が \(s\) 未満のマスに移動するときを考えます。このとき、一連の移動においてマスの番号が \(s\) 未満のマスからマスの番号がそれより大きいマスへの移動が必要なことがわかります。この移動のコストは \(\displaystyle\min_{i < s} R_i\) 以上であり、最初の移動のコストが \(L_s\) であることと合わせるとコストの合計は \(L_s + \displaystyle\min_{i < s} R_i\) 以上となります。一方、最初の移動で \(\displaystyle\min_{i < s} R_i = R_u\) かつ \(u < s\) なるマス \(u\) に移動し、次の移動でマス \(t\) に移動すればコストの合計は \(L_s + \displaystyle\min_{i < s} R_i\) となるため、この場合のコストの合計の最小値は \(L_s + \displaystyle\min_{i < s} R_i\) となります。

以上をまとめると、\(s < t\) なるクエリに対する答えは \(\min(R_s, L_s + \displaystyle\min_{i < s} R_i)\) です。\(R\) の先頭から累積 min を前計算しておくことで、各クエリには \(O(1)\) 時間で答えることができます。

なお、\(s > t\) なるクエリに対しては、答えは \(\min(L_s, R_s + \displaystyle\min_{i > s}L_i)\) であり、\(L\) の末尾から累積 min を計算しておくとよいです。

実装例

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, q;
	cin >> n >> q;
	vector<int> L(n), R(n);
	for (int i = 1; i < n; i++) cin >> L[i];
	for (int i = 0; i < n - 1; i++) cin >> R[i];
	vector<int> A = L, B = R;
	for (int i = n - 2; i >= 0; i--) A[i] = min(A[i], A[i + 1]);
	for (int i = 1; i < n; i++) B[i] = min(B[i], B[i - 1]);
	while (q--) {
		int s, t;
		cin >> s >> t;
		s--; t--;
		if (s < t) {
			int ans = R[s];
			if (s > 0) ans = min(ans, L[s] + B[s - 1]);
			cout << ans << '\n';
		}
		else {
			int ans = L[s];
			if (s < n - 1) ans = min(ans, R[s] + A[s + 1]);
			cout << ans << '\n';
		}
	}
}