#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+100; 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[0].r=0; for(i=1,j=0; 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=1; 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=1; 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+1,a+n+1,cmp); sort(b+1,b+m+1,cmp); memset(va,0,sizeof(va)); memset(va,0,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=0,sum=0; for(int i=1,j=1; i<=vn; i++) { while(j<=vm&&vb[j].r<=va[i].l) j++; sum=0; 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>1&&vb[j-1].r>va[i].r) j--; ans+=va[i].r-va[i].l-sum; } cout<<ans<<endl; } return 0; }