制約が \(N \leq 2000\) と小さいので、\(O(N^2)\) 回のループによって \(1 \leq i \lt j \leq N\) を満たす整数の組 \((i,j)\) を列挙し、それぞれについて \(O(1)\) で区間 \(i\), \(j\) が共通部分を持つかを判定すればよいです。以降、\(O(1)\) で区間が共通部分を持つかを判定する方法のみについて解説します。

区間が共通部分を持つかの判定には、様々な手法があります。例えば、\((t_i,t_j)\) の組み合わせによって合計 \(16\) 通りの場合分けをするのが最も思いつきやすい方針でしょう。

しかし、このような方針だと実装に時間がかかってしまい、またバグも埋め込みやすくなってしまいます。そこで、各区間を閉区間に直すことを考えましょう。

区間の両端点が整数であるという制約から、

• \([l_i,r_i]\) を \([l_i,r_i]\)
• \([l_i,r_i)\) を \([l_i,r_i-0.5]\)
• \((l_i,r_i]\) を \([l_i+0.5,r_i]\)
• \((l_i,r_i)\) を \([l_i+0.5,r_i-0.5]\)

に置き換えても答えは変わりません。

このような区間の置き換えをすることで共通部分を持つかの判定を高々 \(1\) 通りの場合分けで済ませることができ、実装が非常に軽くなります。

なお、\(2\) つの閉区間 \([a,b],[c,d]\) が共通部分を持つかの判定は \(\max(a,c) \leq \min(b,d)\) と書くことができます。

実装例 (Python)

N = int(input())
l = [0]*N
r = [0]*N
for i in range(N):
    t,l[i],r[i] = map(int,input().split())
    if t == 2:
        r[i] -= 0.5
    elif t == 3:
        l[i] += 0.5
    elif t == 4:
        l[i] += 0.5
        r[i] -= 0.5
ans = 0
for i in range(N):
    for j in range(i+1,N):
        ans += (max(l[i],l[j]) <= min(r[i],r[j]))
print(ans)

以下のように bit 演算を用いて書くとより簡潔です。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
    int N; cin >> N;
    vector<double> l(N),r(N);
    for(int i=0; i<N; i++){
        int t; cin >> t >> l[i] >> r[i];
        t--;
        if(t&1) r[i] -= 0.5;
        if(t&2) l[i] += 0.5;
    }
    int ans = 0;
    for(int i=0; i<N; i++){
        for(int j=i+1; j<N; j++){
            ans += (max(l[i],l[j]) <= min(r[i],r[j]));
        }
    }
    cout << ans << endl;
}

BONUS: \(N \leq 2 \times 10^5\)