## Sunday, June 12, 2016

### [hihoCoder] #1305 : 区间求差 解题报告 - Jonah的专栏 - 博客频道 - CSDN.NET

[hihoCoder] #1305 : 区间求差 解题报告 - Jonah的专栏 - 博客频道 - CSDN.NET

### 输出

```3 2
2 5 4 10 14 18
1 3 8 15```

`8`

vector<pair<int, int> > merge(vector<pair<int, int> >& nums) { vector<pair<int, int> > result; int len = nums.size(), begin = nums[0].first, end = nums[0].second; for(int i =1; i< len; i++) { if(nums[i].first <= end) end = max(end, nums[i].second); else { result.push_back(make_pair(begin, end)); begin = nums[i].first; end = nums[i].second; } } result.push_back(make_pair(begin, end)); return result; } int main() { int N, M, val1, val2; cin>> N >> M; vector<pair<int, int> > A(N), B(M); for(int i =0; i< N; i++) { cin>>val1 >> val2; A[i] = make_pair(val1, val2); } for(int i =0; i< M; i++) { cin>>val1 >> val2; B[i] = make_pair(val1, val2); } sort(A.begin(), A.end()); sort(B.begin(), B.end()); vector<pair<int, int> > vecA = merge(A); vector<pair<int, int> > vecB = merge(B); int begin, end, ans = 0, k =0, lenA = vecA.size(), lenB = vecB.size(); for(int i = 0; i < lenA; i++) { int sum = 0; begin = vecA[i].first, end = vecA[i].second; while(k < lenB && vecB[k].second <= begin) k++; while(k < lenB && vecB[k].second > begin && vecB[k].first < end) { sum += min(end, vecB[k].second) - max(begin, vecB[k].first); k++; } if(k >0 && vecB[k-1].second > end) k--; ans += end-begin - sum; } cout << ans << endl; return 0; }