括弧列に置き換えて解く方法を紹介します。

まず、公式解説の冒頭と同様に、この問題を数直線上の区間の包含関係の問題に置き換えて考えます。その上で、全ての区間\([A_{i}, B_{i}]\)について、\(A_{i}\)番目の文字を(、\(B_{i}\)番目の文字を)とした長さ\(2N\)の文字列\(S\)を考えます(どの文字も割り当てられなかった位置は空白文字とします)。区間\([A_{i}, B_{i}]\)は互いに交差しないため、この空白文字を含む括弧列\(S\)上で文字\(S_{A_{i}}\)と \(S_{B_{i}}\)は対応する括弧となります。

この時、区間\([C_{i}, D_{i}]\)に交差する区間の数は、\(S\)の部分文字列\(S_{C_{i}...D_{i}}\)を空白文字を含む正しい括弧列にするために削除する必要のある最小の括弧の数と等しくなります。

\(S_{C_{i}...D_{i}}\)を空白文字を含む正しい括弧列にするために削除する必要のある最小の括弧の数は以下のように求めることができます。

\(S\) の(を\(+1\) 、)を\(−1\)、空白文字を\(0\)に置き換えた数列を\(T=(T_{1}, T_{2}, ... ,T_{2N})\)とし、\(T\)の前から累積和をとった数列を \(U=(U_{0},U_{1}, U_{2}, ... ,U_{2N})\)とします。この時、

• 削除する必要のある)の数：\(U_{C_{i}} - \min(U_{C_{i}}, U_{C_{i}+1}, ... , U_{D_{i}})\)
• 削除する必要のある(の数：\(U_{D_{i}} - \min(U_{C_{i}}, U_{C_{i}+1}, ... , U_{D_{i}})\)

です。

区間最小値の取得にセグメントツリーを利用することで、時間計算量\(O(N + Q\log(N))\)で解くことができます。

実装例(C++):

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

int op(int a, int b) { return min(a, b); }
int e() { return numeric_limits<int>::max(); }

int main() {
	int N, M;
	cin >> N >> M;
	vector<pair<int, int>> ab(M);
	for (auto&& e : ab) cin >> e.first >> e.second;

	vector<int> T(N * 2 + 1, 0);
	for (auto&& e : ab) {
		T[e.first]++;
		T[e.second]--;
	}
	vector<int> U(N * 2 + 1, 0);
	for (int i = 1; i < ssize(U); ++i) U[i] = T[i] + U[i-1];
	segtree<int, op, e> seg(U);

	int Q;
	cin >> Q;
	while (Q--) {
		int C, D;
		cin >> C >> D;
		const int E = seg.prod(C, D + 1);
		cout << U[C] - E + U[D] - E << '\n';
	}
}