#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 题目连接：http://hihocoder.com/problemset/problem/1305
题意：A-B区间求差集
思路：a，b本身区间去重。相对来说，交集容易求出来。差集=本身-交集。
代码：#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1e6+;
struct node
{
int l,r;
} a[MAXN],b[MAXN],va[MAXN],vb[MAXN];
int cmp(node x,node y)
{
return x.l<y.l;
}
void change(int *x,int *y)
{
int sign=*x;
*x=*y;
*y=sign;
}
int removal(node *a,int n,node *va)
{
int i,j;
va[].r=;
for(i=,j=; i<=n; i++)
{
if(a[i].l<=va[j].r)
va[j].r=max(va[j].r,a[i].r);
else
{
j++;
va[j].l=a[i].l;
va[j].r=a[i].r;
}
}
return j;
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
for(int i=; i<=n; i++)
{
scanf("%d%d",&a[i].l,&a[i].r);
if(a[i].l>a[i].r) change(&a[i].l,&a[i].r);
}
for(int i=; i<=m; i++)
{
scanf("%d%d",&b[i].l,&b[i].r);
if(b[i].l>b[i].r) change(&b[i].l,&b[i].r);
}
sort(a+,a+n+,cmp);
sort(b+,b+m+,cmp);
memset(va,,sizeof(va));
memset(va,,sizeof(vb));
int vn=removal(a,n,va),vm=removal(b,m,vb);
/*
for(int i=1; i<=vn; i++)
cout<<va[i].l<<" "<<va[i].r<<" ";
cout<<endl;
for(int i=1; i<=vm; i++)
cout<<vb[i].l<<" "<<vb[i].r<<" ";
cout<<endl;
*/
int ans=,sum=;
for(int i=,j=; i<=vn; i++)
{
while(j<=vm&&vb[j].r<=va[i].l) j++;
sum=;
while(j<=vm&&vb[j].r>va[i].l&&vb[j].l<va[i].r)
{
sum+=min(va[i].r,vb[j].r)-max(va[i].l,vb[j].l);
j++;
}
if(j>&&vb[j-].r>va[i].r) j--;
ans+=va[i].r-va[i].l-sum;
}
cout<<ans<<endl;
}
return ;
}区间去重