各頂点 \(j\) にポテンシャル \(v_j\) を定め、道 \(j\) の強さを \(w_j=v_{j+1}-v_j\) とします。

まず、全ての人が \(S_i<T_i\) を満たすケースを考えます。

このとき、人 \(i\) の要求は、\(v_{S_i} = v_{T_i}\) かつ \(j=S_i+1, S_i+2, \ldots, T_i-1\) に対して \(v_j > v_{S_i}\) となります。

よって、区間 \(i\) を \((S_i, T_i)\) としたとき、全ての人の要求を満たすようなポテンシャルの割り当てが存在するための条件は、全ての \((i,j)\,(1\le i < j \le M)\) について、以下のいずれかが成り立つことです。

• 区間 \(i\) と区間 \(j\) が共通部分を持たない。すなわち、\(T_i\leq S_j\) または \(T_j\leq S_i\)。
• 区間 \(i\) と区間 \(j\) の一方がもう一方に完全に内包されており、かつ両端がどちらも一致しない。すなわち、\(S_i<S_j<T_j<T_i\) または \(S_j<S_i<T_i<T_j\)。

この条件のことを、区間の集合が laminar である、と呼ぶことにします。

次に、一般の場合を考えます。

\(S_i>T_i\) のとき、人 \(i\) の要求は、\(v_{T_i} = v_{S_i}\) かつ \(j=T_i+1, T_i+2, \ldots, S_i-1\) に対して \(v_j < v_{T_i}\) となります。

全ての人の要求を満たすようなポテンシャルの割り当てが存在するための必要条件について考えます。

まず、一つ目の必要条件は以下です。

• \(S_i<T_i\) かつ \(T_j<S_j\) であるような \((i,j)\) について、\(S_i\neq T_j\) かつ \(S_j\neq T_i\)。

この条件が成り立っていなければ、端の道の強さの正負に矛盾が生じます。

次に、二つ目の必要条件は以下です。

• \(S_i<T_i\) を満たす人 \(i\) のみを考えたときの区間 \([S_i,T_i]\) の集合が laminar である。

三つ目の必要条件は以下です。

• \(T_i<S_i\) を満たす人 \(i\) のみを考えたときの区間 \([T_i, S_i]\) の集合が laminar である。

これらの三つの必要条件を満たすとき、条件を満たすポテンシャルの割り当てが必ず存在します（証明の概略は後述）。

よって、クエリを処理するためには、尺取り法を用いて、\(L_k=1,2,\ldots,M\) の順に、条件を満たす \(R_k\) の最大値を求めればよいです。

一つ目の必要条件の確認は簡単です。 二つ目、三つ目の必要条件を確認するためには、区間の集合への追加と削除、そして集合が laminar かどうかの判定ができればよく、これは Zobrist Hash を用いることで実現できます。 区間の XOR を計算するためには BIT などを使えばよく、計算量は \(O((N+M)\log N+Q)\) です。

以下は証明の概略です。

\(N\) 頂点 \(M\) 辺の有向グラフを考えます。辺 \(i\) は頂点 \(S_i\) から頂点 \(T_i\) へ向かう辺です。

上記の三つの条件により、この有向グラフを無向グラフとして連結成分に分解したとき、各連結成分はパスとなっていて、頂点の番号順につながっているということが分かります。

これらのパスどうしに順序付けをします。 パスの左端の頂点を \(l\)、右端の頂点を \(r\) としたとき、区間 \([l,r]\) をそのパスの被覆範囲と呼ぶことにします。

被覆範囲が共通部分を持たないパスどうしにはポテンシャルの大小関係の制約がありません。

被覆範囲が共通部分を持つパス \(i\) とパス \(j\) のポテンシャルの大小関係を考えます。 \(l_i<l_j \leq r_i\) としてよいです。

パス \(i\) に含まれる辺 \(S\rightarrow T\) が存在して \(S<l_j<T\) のとき、パス \(i\) とパス \(j\) のポテンシャルの大小関係は \(i<j\) となります。

このとき、二つ目と三つ目の条件により、パス \(j\) の頂点 \(x_j\) に対して、パス \(i\) に含まれる辺 \(T\rightarrow S\) であって、\(T<x_j<S\) を満たすものが存在しないことが分かります。同様に、パス \(i\) の頂点 \(x_i\) に対して、パス \(j\) に含まれる辺 \(S\rightarrow T\) であって、\(S<x_i<T\) を満たすものが存在しないことが分かります。よって、パス \(i\) とパス \(j\) のポテンシャルの大小関係は一意に定まります。

逆に、パス \(i\) の辺 \(T\rightarrow S\) が存在して \(T<l_j<S\) のとき、パス \(i\) とパス \(j\) のポテンシャルの大小関係は \(i>j\) となります。 このときも、同様の議論によって、パス \(i\) とパス \(j\) のポテンシャルの大小関係は一意に定まります。

これらの大小関係によって得られるグラフは DAG になっています。