題目鏈接：點(diǎn)擊查看

題目大意：給出n個區(qū)間，現(xiàn)在要求輸出覆蓋次數(shù)為1,2,3....n-1,n的點(diǎn)分別有多少個

題目分析：一開始看到區(qū)間問題想用線段樹去做，但想了想又可以直接用差分去做，不過因?yàn)閿?shù)比較大，所以用map代替差分?jǐn)?shù)組，后續(xù)求前綴和的時候就可以實(shí)時維護(hù)答案了

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<cmath> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e5+100;LL ans[N];map<LL,int>mp;int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++){LL l,r;scanf("%lld%lld",&l,&r);mp[l]++;mp[r+1]--;}int cnt=0;for(map<LL,int>::iterator it=mp.begin();it!=mp.end();it++){map<LL,int>::iterator next=it;next++;if(next==mp.end())break;cnt+=it->second;ans[cnt]+=next->first-it->first;}for(int i=1;i<=n;i++)printf("%lld ",ans[i]);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1000C Covered Points Count(差分+思维)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。