这题真的坑啊
比较好想的做法是把利用差分的思想,把所有区间存进map里
左端点就在对应的位置加加表示多了线段,右端点就减减
最后从左到右扫一遍所有端点,动态维护每两个端点间的线段数累加
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+10; map<ll,int>mp; map<ll,int>::iterator it; ll cnt[maxn],n,l,r; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>l>>r; mp[l]++,mp[r+1]--; } it = mp.begin(); ll last=it->first,ans=it->second;//区间起点和答案 it++; for(;it!=mp.end();it++ ) { cnt[ans]+=it->first-last; last=it->first; ans+=it->second; } for(int i=1;i<=n;i++) cout<<cnt[i]<<" "; return 0; }