4195. 线段覆盖 差分 离散化 遍历map

4195. 线段覆盖 差分 离散化 遍历map 题目

题解思路

直接差分即可。
我的做法被卡常了，这里利用map的自己排序的特性，节省时间。
最后遍历map出答案。
这题其实是简单题，但是我写的很复杂，甚至蠢到用哈希表去了，明明会大概率哈希错误（大于1e8）。

AC代码

#include 
//#include 
//priority_queue
#define PII pair
#define ll long long

using namespace std;

const  int  INF =  0x3f3f3f3f;
const  int  N =  200100;
long long ans[N] ; 

int main()
{
    map  mp ; 
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n ;
    cin >> n ; 
    for (int i = 1 ; i <= n ; i++ )
    {
        long long t1 , t2 ;
        cin >> t1 >> t2 ; 
        mp[t1]++ ;
        mp[t2+1]--;
    }
    long long  last = -1 ; 
    long long st = 0 ; 
    for ( auto& [key,val] : mp )
    {
        //cout << st << "n" ; 
        if (last != -1 )
        {
            ans[st] += key - last ; 
            //cout << key << " " << last << "n" ; 
        }
        last = key ; 
        st += val ;
    }
    for (int i = 1 ; i <= n ; i++ )
        cout << ans[i] << " " ; 
    cout << "n" ; 
    return 0 ;
}