C. Covered Points Count (线段问题---差分、排序)

悠悠 2021-07-16 20:35 210阅读 0赞

[题目][Link 1]

两种解法：

1.用差分思想，l—r所有点加1用map\[l\]+1,mdp\[r+1\]-1表示，前缀和即是当前点所对应覆盖线段数。

Code:

#include<iostream>
    #include<stack>
    #include<map>
    #include<string>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    ll a[Max], b[Max];
    pair<ll, ll> lst[Max];
    map<ll, ll> ma, mp;
    
    int main()
    { 	
    	int n;cin >> n;
    	for (int i = 1;i <= n;i++)
    	{ 
    		ll l, r;cin >> l >> r;
    		ma[l]++;
    		ma[r + 1]--;
    	}
    	ll last = ma.begin()->first;
    	ll sum = ma.begin()->second;
    	for (auto i = ma.begin();i != ma.end();i++)
    	{ 
    		if (i == ma.begin())continue;
    		mp[sum] += i->first - last;
    		last = i->first;
    		sum += i->second;
    	}
    	for (int i = 1;i <= n;i++)cout << mp[i] << " ";
    }

排序模拟算贡献：

先将所有的左右端点排序，相同坐标起点放终点前面。每次遇到一个左端当前覆盖线段数+1，遇到右端当前覆盖线段数-1，每遇到一个改变的地方处理一批点，就是说之前那一批点覆盖的线段数量都相同。还有些细节处理，如果前面的改变处是左端则前面的左端那个点还没计算过点数+1，是右端表示前面的那个点已经计算过点数-1，同理现在的这个改变处是左端点数-1，右端点数+1，细节见代码。

Code:

#include<iostream>
    #include<stack>
    #include<map>
    #include<string>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    ll a[Max], b[Max];
    pair<ll, ll> lst[Max];
    map<ll, ll> ma;
    int main()
    { 	
    	int n;cin >> n;
    	for (int i = 1;i <= n;i++)
    	{ 
    		ll l, r;cin >> l >> r;
    		lst[i * 2 - 1] = make_pair(l, ll(0));
    		lst[i * 2] = make_pair(r, ll(1));
    	}
    	sort(lst + 1, lst + 1 + 2 * n);
    	ll sum = 1;
    	for (int i = 2;i <= n*2;i++)
    	{ 
    		ll q = 0;
    		if (lst[i].second == 0)
    		{ 
    			q = lst[i].first - lst[i - 1].first - 1;
    			if (lst[i - 1].second == 0)q++;
    			ma[sum] += q;
    			sum++;
    		}
    		else
    		{ 
    			q = lst[i].first - lst[i - 1].first ;
    			if (lst[i - 1].second == 0)q++;
    			ma[sum] += q;
    			sum--;
    		}
    	}
    	for (int i = 1;i <= n;i++)
    	{ 
    		cout << ma[i] << " ";
    	}
    }

[Link 1]: https://codeforc.es/problemset/problem/1000/C