shobonvip さんの解説と同様の定式化をします。分割統治を行いますが、有理式ではなく多項式で情報を持つことができます。

\([l, r)\) の計算をするとき，再帰のステップで最初に \(p := \min_{l \leq i < r} P_i\) および \(q := \min_{l \leq i < r} Q_i\) を求め、\(l \leq i < r\) に対し \(P_i\) から \(p\) を引き、\(Q_i\) から \(q\) を引きます。このとき、\(P, Q\) の差分が高々 \(1\) であることから、\(\max_{l \leq i < r} P_i\) や　\(\max_{l \leq i < r} Q_i\) は \(r-l\) 以下になります。よって分割統治により得られる多項式の次数は高々 \(2(r-l)\) となり、これに \(x^p (1+x)^q\) をかければ良いです。

時間計算量は全体で \(O(N \log^2 N)\) になります。