Codeforces Round 904 (Div. 2) C. Medium Design
思路:
因为出现的线段应该为不相同的线段,所以最小值应该为 \(1\) 或 \(m\)
因此我们可以通过差分储存线段范围内的加值,再用前缀和表示这个范围内的最大加值
sl为不包含\(1\)的线段的差分,sr为不包含\(m\)的线段差分
记录用于差分的端点在 \(s1\) \(s2\)
遍历\(s1\)和\(s2\),res+=\(sl_{nod}\)(\(sr_{nod}\))则为 不到1的线段差分前缀和 与 不到m的线段差分前缀和
对于所取节点差分前缀和取\(max\)即可得到最大差值
#define int long long
#define ld long double
#define fr(i,l,r) for(int i=l;i<=r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)
#define pb push_back
#define so(a) sort(a.begin(),a.end())
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
const int N = 1e5 + 10;
int t, n, m;
map<int, int>sl, sr;
set<int>s1;
set<int>s2;
void solve()
{
sl.clear();
sr.clear();
s1.clear();
s2.clear();
cin >> n >> m;
fr(i, 1, n)
{
int l, r;
cin >> l >> r;
if (l > 1)
{
sl[l]++, sl[r+1]--;
s1.insert(l), s1.insert(r+1);
}
if (r < m)
{
sr[l]++, sr[r+1]--;
s2.insert(l), s2.insert(r+1);
}
}
int ans = 0, res = 0;
for (auto it:s1)
{
res += sl[it];
ans = max(ans, res);
}
res = 0;
for (auto it : s2)
{
res += sr[it];
ans = max(ans, res);
}
cout << ans << endl;
}
signed main()
{
//t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}