ABC 221 D（不用桶的差分，求被覆盖了k次点的个数

D - Online games
题意：
给定 $n$ 个区间，起点为 a i a_i ai​，长度为 b i b_i bi​，求被覆盖了 $k$ 次的整数点的个数， 1 < = k < = n , 1 < = a i , b i < = 1 0 9 1<=k<=n,1<=a_i,b_i<=10^9 1<=k<=n,1<=ai​,bi​<=109
思路：
差分
用 $vector$ 存 $pair$ 排序后进行差分速度比较快
code：

#include
#define ll long long
using namespace std;
const int maxn = 2e5 + 9;int ans[maxn];
void work()
{int n;cin >> n;int a, b;vector <pair<int,int> > v;int cnt = 0;for(int i = 1; i <= n; ++i){cin >> a >> b;v.push_back({a, 1});v.push_back({a + b, -1});}sort(v.begin(), v.end());for(int i = 0; i < v.size() - 1; ++i){cnt += v[i].second;ans[cnt] += (v[i + 1].first - v[i].first);}for(int i = 1; i <= n; ++i)cout << ans[i] << " ";
}int main()
{ios::sync_with_stdio(0);work();return 0;
}

更一道一样的题，AcWing周赛

4195. 线段覆盖
题意：
给定 $n$ 个区间，起点 $l$，终点 $r$，求被覆盖了 $k$ 次的整数点有多少个， 1 < = k < = n ， 1 < = l , r < = 1 0 18 1<=k<=n，1<=l,r<=10^{18} 1<=k<=n，1<=l,r<=1018
思路：
用 $map$ 差分，速度比较慢
code：

#include
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define eps 1e-6
using namespace std;
const int maxn = 2e5 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
map <ll, int> ma;
ll ans[maxn];// 开 llvoid work()
{cin >> n;for(int i = 1; i <= n; ++i){ll l, r;cin >> l >> r;ma[l]++; ma[r + l]--;}ll sum = 0, last = -1;for(auto [x, y] : ma){if(last != -1) ans[sum] += x - last;sum += y;last = x;}for(int i = 1; i <= n; ++i) cout << ans[i] << " ";
}int main()
{ios::sync_with_stdio(0);
//	int TT;cin>>TT;while(TT--)work();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！