#P2082. 区间覆盖(加强版)
区间覆盖(加强版)
题目描述
已知有 个区间,每个区间的范围是 ,请求出区间覆盖后的总长。
输入格式
第一行一个正整数 ,表示区间个数。
接下来 行,每行两个正整数,表示 和 。
输出格式
共一行,一个正整数,为覆盖后的区间总长。
3
1 100000
200001 1000000
100000000 100000001
900002
提示
对于 的数据,,。
对于 的数据 ,,。
已知有 N 个区间,每个区间的范围是 [si,ti],请求出区间覆盖后的总长。
第一行一个正整数 N,表示区间个数。
接下来 N 行,每行两个正整数,表示 si 和 ti。
共一行,一个正整数,为覆盖后的区间总长。
3
1 100000
200001 1000000
100000000 100000001
900002
对于 40% 的数据,N≤1000,1≤si<ti≤10000。
对于 100% 的数据 ,N≤105,1≤si<ti≤1017。