モノイドを(区間の最小値, 区間内の最小値を取る値)を持ち、区間への作用を加算としたものは遅延セグメント木で処理することができます。（詳細は割愛します。 ABC346G - Aloneなどが類題です。）

したがって、以下の手順で \(O((N + M) \log N)\) で \(K\) 個を除く方法全てを試すことができます。

1. 長さ \(N\) の遅延セグメント木の各ノードを \((0, 1)\) （最小値が \(0\), 最小値を取る値の個数が \(1\) 個）として初期化する。
2. 最初、\(i = K+1, K+2, \dots, M\) について \([L_i, R_i]\)に対して\(1\) を加える作用を行う。その後、遅延セグメント木の全体クエリを行うことで区間内の最小値が \(0\) であるか、その場合 \(0\) をとるような区間はいくつかが分かるため \(s = 1\) を選んだ場合の塗られる板の枚数を計算できる。
3. \(i = 1, 2, \dots, M - K\)について、\([L_i, R_i]\) に対して \(1\) を加え \([ L_{i+K} , R_{i+K} ]\) に対して \(-1\) を加える作用を行う。その後同様に全体クエリを行い \(s = i+1\) に対する解を計算する。
4. 手順2および3で計算された値の最大値を解として出力する。

この解法では計算量に \(N\) が寄与してしまいますが、区間を座標圧縮することで \(O(M)\) 個の区間に分割しても容易にこの解法を拡張できます。（定数倍は厳しいですが、動的遅延セグメント木などを用いてもよいです。）以上によりこの問題を \(O(M \log M)\) などで解くことができます。