C - Covered Points Count CodeForces - 1000C (差分,离散化,统计)
C - Covered Points Count
You are given nn segments on a coordinate line; each endpoint of every segment has integer coordinates. Some segments can degenerate to points. Segments can intersect with each other, be nested in each other or even coincide.
Your task is the following: for every k∈[1..n]k∈[1..n], calculate the number of points with integer coordinates such that the number of segments that cover these points equals kk. A segment with endpoints lili and riri covers point xx if and only if li≤x≤rili≤x≤ri.
Input
The first line of the input contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the number of segments.
The next nn lines contain segments. The ii-th line contains a pair of integers li,rili,ri (0≤li≤ri≤10180≤li≤ri≤1018) — the endpoints of the ii-th segment.
Output
Print nn space separated integers cnt1,cnt2,…,cntncnt1,cnt2,…,cntn, where cnticnti is equal to the number of points such that the number of segments that cover these points equals to ii.
Examples
Input
30 31 33 8
Output
6 2 1
Input
31 32 45 7
Output
5 2 0
Note
The picture describing the first example:
Points with coordinates [0,4,5,6,7,8][0,4,5,6,7,8] are covered by one segment, points [1,2][1,2] are covered by two segments and point [3][3] is covered by three segments.
The picture describing the second example:
Points [1,4,5,6,7][1,4,5,6,7] are covered by one segment, points [2,3][2,3] are covered by two segments and there are no points covered by three segments.
题意:
给你n个线段
让你输出有多少个点被1~n个线段覆盖?
思路:
将线段拆成点,左端点权值为1,右端点权值为-1,离散化端点之后从左往右扫,过程中维护左端点和当前区间被多少个线段覆盖,统计答案就行了。
注意:
因为l~r线段中包括的点数是r-l+1,所以我们可以直接r++
map会根据firstkey 即ll排好序,所以可以直接for(auto : T)
细节见代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2) { ans = ans * a % MOD; } a = a * a % MOD; b /= 2;} return ans;}
inline void getInt(int *p);
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int n;
ll l, r;
map<ll, ll> m;
ll ans[maxn];
int main()
{
//freopen("D:\\code\\text\\input.txt","r",stdin);
//freopen("D:\\code\\text\\output.txt","w",stdout);
gbtb;
cin >> n;
repd(i, 1, n) {
cin >> l >> r;
r++;
m[l]++;
m[r]--;
}
ll cnt = 0ll;
l = 0ll;
for (auto x : m) {
ll len = x.fi - l;
ans[cnt] += len;
l = x.fi;
cnt += x.se;
}
repd(i, 1, n) {
cout << ans[i];
if (i != n) {
cout << " ";
} else {
cout << endl;
}
}
return 0;
}
inline void getInt(int *p)
{
char ch;
do {
ch = getchar();
} while (ch == ' ' || ch == '\n');
if (ch == '-') {
*p = -(getchar() - '0');
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 - ch + '0';
}
} else {
*p = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 + ch - '0';
}
}
}
最新文章
- Daily Scrum Meeting ——SixthDay
- Python开发【十一章】:RabbitMQ队列
- 转行做开发的Wiki:找好方向
- Back-propagation, an introduction
- Java继承,多态,组合应用
- Oracle中可以nologging执行的操作
- Extension 代表的是私有成员变量
- 如何使用数据库保存session的方法简介
- 【jmeter】JMeter处理Cookie与Session
- 对ArrayList 进行深拷贝
- flappy bird游戏源代码揭秘和下载
- 编绎报错,解决方法objc_msgSend too many arguments to function call,expected 0, have3 (转)
- 网易云课堂_C语言程序设计进阶_第5周:链表
- 2015 多校联赛 ——HDU5301(技巧)
- LaTeX 公式编辑
- Linux下mysql的远程连接(转)
- 【Android】 导入项目报错的解决方案
- enumerate的简单使用
- swift swift学习笔记--函数和闭包
- Android异步下载