给定两个区间集合 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)。
---------------------------------------------------------------------------------------------------------
一看是区间的问题，就写了个线段树800msAC了，可是看了分析才知道大材小用了，线段树适合多次修改多次询问的，而这个只是一次询问也没动态修改，
所以直接：排序然后用两个计数器记录每个区间起点处A和B的覆盖情况就行了。
线段树版 823ms:
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define MAX(a,b) ((a)>=(b)?(a):(b))
#define MIN(a,b) ((a)<=(b)?(a):(b))
#define OO 0x0fffffff
using namespace std;
typedef long long LL;
const int N = 100100;
struct Node{
int l,r;
int lazy;
Node(){lazy=0;}
int mid(){return (l+r)>>1;}
};
Node segtree[N*12];
int uni0[N*4],uni1[N*4],flag[N*4];
int n,m;
void build(int id,int l,int r){
segtree[id].l = l;
segtree[id].r = r;
if(l==r) return ;
int mid = (l+r)>>1;
build(id*2+0,l,mid);
build(id*2+1,mid+1,r);
}
void modify(int id,int spos,int epos,int tag){
if(segtree[id].l==spos&&segtree[id].r==epos){
segtree[id].lazy|=tag;
return ;
}
if(segtree[id].lazy&tag) return ;
if(segtree[id].lazy){
segtree[id*2+0].lazy|=segtree[id].lazy;
segtree[id*2+1].lazy|=segtree[id].lazy;
segtree[id].lazy = 0;
}
int mid = segtree[id].mid();
if(epos<=mid){
modify(id*2+0,spos,epos,tag);
}
else if(spos>mid){
modify(id*2+1,spos,epos,tag);
}
else{
modify(id*2+0,spos,mid,tag);
modify(id*2+1,mid+1,epos,tag);
}
}
void traverse(int id){
if(segtree[id].l==segtree[id].r) {
flag[segtree[id].l]=segtree[id].lazy;
return ;
}
segtree[id*2+0].lazy|=segtree[id].lazy;
segtree[id*2+1].lazy|=segtree[id].lazy;
traverse(id*2+0);
traverse(id*2+1);
}
int main(){
cin>>n>>m;
int cnt=(m+n)*2;
for(int i=0;i<cnt;i++) cin>>uni0[i];
map<int,int> refl;
memcpy(uni1,uni0,sizeof(int)*cnt);
sort(uni1,uni1+cnt);
int maxn = unique(uni1,uni1+cnt)-uni1;
for(int i=0;i<maxn;i++) { refl[uni1[i]] = i; }
build(1,0,maxn-2);
for(int i=0;i<n;i++) {
if(uni0[i*2+0]==uni0[i*2+1]){continue;}
int l = refl[uni0[i*2+0]];
int r = refl[uni0[i*2+1]];
if(l>r) swap(l,r);
modify(1,l,r-1,1);
}
for(int i=n;i<m+n;i++){
if(uni0[i*2+0]==uni0[i*2+1]){continue;}
int l = refl[uni0[i*2+0]];
int r = refl[uni0[i*2+1]];
if(l>r) swap(l,r);
modify(1,l,r-1,2);
}
traverse(1);
long long ans = 0;
for(int i=0;i<maxn-1;i++){
if(flag[i]==1){
ans+=(uni1[i+1]-uni1[i]);
}
}
printf("%lld
",ans);
return 0;
}
简单版 104ms
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define MAX(a,b) ((a)>=(b)?(a):(b))
#define MIN(a,b) ((a)<=(b)?(a):(b))
#define OO 0x0fffffff
using namespace std;
typedef long long LL;
const int N = 100100*4;
struct NODE{
int value;
int type;
friend bool operator<(const NODE &a,const NODE &b){
return a.value<b.value;
}
};
NODE ps[N];
int cnta,cntb;
void check(int type){
switch(type){
case 0 : cnta++; break;
case 1 : cnta--; break;
case 2 : cntb++; break;
case 3 : cntb--; break;
}
}
int main(){
int n,m,cnts;
cin>>n>>m;
cnts = m+n;
for(int i=0;i<n;i++){
scanf("%d%d",&ps[i*2+0].value,&ps[i*2+1].value);
ps[i*2+0].type = 0;
ps[i*2+1].type = 1;
}
for(int i=n;i<cnts;i++){
scanf("%d%d",&ps[i*2+0].value,&ps[i*2+1].value);
ps[i*2+0].type = 2;
ps[i*2+1].type = 3;
}
cnts<<=1;
std::sort(ps,ps+cnts);
int ans = 0;
cnta = cntb = 0;
check(ps[0].type);
int lpos = ps[0].value;
for(int i=1;i<cnts;i++){
if(ps[i].value!=lpos){
if((cnta)&&(!cntb)){
ans += ps[i].value-lpos;
}
lpos = ps[i].value;
}
check(ps[i].type);
}
printf("%d
",ans);
return 0;
}