离散化/差分

分析题目发现上下车的状态是连续的，即上车加一，下车减一，同一个人在车上不动也不会发生什么变化，所以考虑用差分+前缀和来计算此刻车上的人数，看到1<a[i]<1e9,数组内存超限，不能直接用数组存储。考虑用离散化，我这里的方法比较直观，直接重新按照从小到大映射新的坐标，比insert()方法更直观。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10,M=1e9+10;
int a[N];
typedef pair<int,int>PII;
vector<int>all;
int find(int x)
{
	int mid, l = 0, r = all.size()-1;
	while (l < r)
	{
		mid = l + r >> 1;
		if (all[mid] >=x)r = mid;
		else l = mid + 1;
	}
	return r + 1;
}
signed main()
{
    int T,n;
    cin>>T;
    while(T--)
    {
        int t;
        memset(a,0,sizeof(a));
        map<int,bool>st;
         all.clear();
        vector<PII>add;
        cin>>t;
        int cnt=0;
        int xmin=1e9+10,xmax=0;
        for(int i=1;i<=t;i++)
        {
            int x,y;
            cin>>x>>y;
            add.push_back({x,y});
            all.push_back(x);
            all.push_back(y);
            if(st[x]==false)
            st[x]=true,cnt++;
            if(st[y]==false)
            st[y]=true,cnt++;
        }
        int ans=0;
             sort(all.begin(), all.end());
	       all.erase(unique(all.begin(), all.end()), all.end());
        for(int i=0;i<add.size();i++)
        {
            a[find(add[i].first)]++,a[find(add[i].second)]--;
        }
        for(int i=1;i<all.size();i++)
        {
            a[find(all[i])]+=a[find(all[i-1])];
           
            ans=max(ans, a[find(all[i])]);
        }
        cout<<cnt<<" "<<ans<<endl;
        
    }
    
    return 0;
    
}