Rephrasing the conditions

\(L \leq X_{A_i} + X_{B_i} \) is equivalent to \(\forall t \in \mathbb{Z}, \lbrack t \leq X_{A_i} \lor L-t+1 \leq X_{B_i} \rbrack \).

(Proof)

When \(L \leq X_{A_i} + X_{B_i} \), if \(\exist t \in \mathbb{Z}, \lbrack t > X_{A_i} \lor L-t+1 > X_{B_i} \rbrack \), then \(\exist t \in \mathbb{Z}, \lbrack t \geq X_{A_i} + 1 \lor L-t+1 \geq X_{B_i} +1\rbrack \); summing them up, we have \(L-1 \geq X_{A_i} + X_{B_i}\), which is a contradiction.
When \(L > X_{A_i} + X_{B_i} \), if we take \(t = X_{A_i} + 1\), we have \(L-t+1 > X_{B_i}\), so it holds that \(\exist t \in \mathbb{Z}, \lbrack t > X_{A_i} \lor L-t+1 > X_{B_i} \rbrack \). \(\square\)

Similarly, we can also prove that \(X_{A_i} + X_{B_i} \leq R\) if and only if \(\forall t \in \mathbb{Z}, \lbrack t > X_{A_i} \lor R-t+1 > X_{B_i} \rbrack \).

2-SAT

Once we have the rephrasing above, we can boil it down to a 2-SAT (2-satisfiability) problem.
Specifically, we consider the assignments of boolean value against conditions \(j \leq X_i\) for each \(1 \leq i \leq N\) and \(0 \leq j \leq M+1\).
In addition to the conditions above, note that \(0 \leq X_i\) is always true, \(M+1 \leq X_i\) is always false, and \(A \leq X_i \Rightarrow A-1 \leq X_i\).
If there is a set of boolean assignments that violates one of them, we can take maximum \(j \leq X_i\) for each \(i\) to let \(X_i = j\); if there is not, no sequence satisfies the conditions in the original problem.
The graph corresponding to the 2-SAT has \(O(NM)\) vertices and \(O((N+Q)M)\) edges, so the problem has been solved in a total of \(O((N+Q)M)\) time.