#1305 : 区间求差
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定两个区间集合 A 和 B，其中集合 A 包含 N 个区间[ A1, A2 ], [ A3, A4 ], ..., [ A2N-1, A2N ]，集合 B 包含 M 个区间[ B1, B2 ], [ B3, B4 ], ..., [ B2M-1, B2M ]。求 A - B 的长度。
例如对于 A = {[2, 5], [4, 10], [14, 18]}, B = {[1, 3], [8, 15]}, A - B = {(3, 8), (15, 18]}，长度为8。
输入
第一行：包含两个整数 N 和 M (1 ≤ N, M ≤ 100000)。
第二行：包含 2N 个整数 A1, A2, ..., A2N (1 ≤ Ai ≤ 100000000)。
第三行：包含 2M 个整数 B1, B2, ..., B2M (1 ≤= Bi ≤ 100000000)。
输出
一个整数，代表 A - B 的长度。
- 样例输入
-
3 2
2 5 4 10 14 18
1 3 8 15 - 样例输出
-
8
#include"iostream"
#include"algorithm"
#include"cstring"
#define MAX 400001
using namespace std; struct point
{
int x;
int state;
}; point nn[MAX]; bool cmp(point p1, point p2)
{
return p1.x < p2.x;
} int main()
{
int n, m;
int start, len=;
int A = , B = ;
cin >> n >> m; for (int i = ; i < * n; i += )
{
cin >> nn[i].x;
nn[i].state = ;
cin >> nn[i + ].x;
nn[i + ].state = ;
} for (int i = *n; i < * (n+m); i += )
{
cin >> nn[i].x;
nn[i].state = ;
cin >> nn[i + ].x;
nn[i + ].state = ;
} n = * (n + m);
sort(nn, nn + n, cmp); for (int i = ; i<n; i++)
{
switch (nn[i].state)
{
case :
if (!B && !A)
start = nn[i].x;
A++;
break;
case :
A--;
if (!B && !A)
len += nn[i].x - start;
break;
case :
if (A && !B)
len += nn[i].x - start;
B++;
break;
case :
B--;
if (A && !B)
start = nn[i].x;
break;
}
} cout << len; return ;
}