zoj 3961 Let's Chat

题目链接：Let’s Chat

题目大意：给你一个n,m,a,b，分别代表线段总长度，需要求的连续的长度，第一个集合所有的区间，第二个集合所有的集合，问你长度为m并且两个集合重合的不同线段有多少种

题目思路：这个题目是比较简单的吧，学弟暴力过了，没看他代码太长了，看网上代码发现一个非常好的解法，写两个指针分别从头开始扫，一遍一遍交换区间，感觉是一个很简短的写法，左端点是当前A区间和B区间左端点的最大值，右端点是A区间和B区间右端点的最小值，然后右端点减左端点+1-m就是这一段的贡献，然后判断哪个区间的右端点大，小的那个换到下一个区间里面，就这样一遍一遍扫就可以了，具体可以看代码

#include <bits/stdc++.h>

using namespace std;

int n,m,x,y,ans;
pair<int ,int >a[110],b[110],p;

void solve(){
    ans = 0;
    int ia = 1,ib = 1;
    p.first = max(a[ia].first,b[ib].first);
    while(1){
        p.second = min(a[ia].second,b[ib].second);
        ans += max(0,p.second-p.first+1-m+1);
        if(ia > x||ib > y) return;
        if(p.second == a[ia].second&&ia <= x)
            ia++;
        else if(p.second == b[ib].second&&ib <= y)
            ib++;
        p.first = max(a[ia].first,b[ib].first);
    }
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d%d",&n,&m,&x,&y);
        for(int i = 1;i <= x;i++)
            scanf("%d%d",&a[i].first,&a[i].second);
        for(int i = 1;i <= y;i++)
            scanf("%d%d",&b[i].first,&b[i].second);
        solve();
        printf("%d\n",ans);
    }
    return 0;
}