本文共 2637 字，大约阅读时间需要 8 分钟。

题意

给出x个a区间和y个b区间，询问a和b交区间的子区间长度为m的个数

分析

类似于双指针，具体见代码

trick

代码

#include <bits/stdc++.h>using namespace std;#define F(i,a,b) for(int i=a;i<=b;++i)#define R(i,a,b) for(int i=a;i<b;++i)#define mem(a,b) memset(a,b,sizeof(a))#pragma comment(linker, "/STACK:102400000,102400000")inline void read(int &x){x=0; char ch=getchar();while(ch<'0') ch=getchar();while(ch>='0'){x=x*10+ch-48; ch=getchar();}}struct node{    int l,r;}a[101],b[101];int t,n,m,x,y;int loca,locb;int ans;int main(){    for(scanf("%d",&t);t--;)    {        scanf("%d %d %d %d",&n,&m,&x,&y);        for(int i=1;i<=x;++i) scanf("%d %d",&a[i].l,&a[i].r);        for(int i=1;i<=y;++i) scanf("%d %d",&b[i].l,&b[i].r);        ans=0;locb=1;        for(int i=1;i<=x;++i)        {            if(locb>y) break;            if(a[i].r<b[locb].l) continue;            while(a[i].l>b[locb].r) locb++;            while(locb<=y&&b[locb].l<=a[i].r)            {                int rr=min(b[locb].r,a[i].r),ll=max(b[locb].l,a[i].l);                if(rr-ll+1>=m) ans+=(rr-ll+2-m);                if(b[locb].l>=a[i].l&&b[locb].r>=a[i].r) break;                if(b[locb].l<=a[i].l&&b[locb].r<=a[i].r) {locb++;continue;}                if(b[locb].l>=a[i].l&&b[locb].r<=a[i].r) {locb++;continue;}                if(b[locb].l<=a[i].l&&b[locb].r>=a[i].r) break;                locb++;            }        }        printf("%d\n",ans);    }    return 0;}

#include <iostream>#include <cstdio>#include <cstring>#include <vector>;using namespace std;struct  points{	int l,r;};vector <points> a,b;int main(){	int cases,n,m,x,y,i,j,s;	points now;	bool flag;	int m1,m2;    scanf("%d",&cases);    while (cases--)    {    	scanf("%d%d%d%d",&n,&m,&x,&y);    	a.clear(); b.clear();    	for (i=1;i<=x;i++)    	{    		scanf("%d%d",&now.l,&now.r);    		if (now.r-now.l+1>=m)    		{    			a.push_back(now);    		}    	}    	for (i=1;i<=y;i++)    	{    		scanf("%d%d",&now.l,&now.r);    		if (now.r-now.l+1>=m)    		{    			b.push_back(now);    		}    	}    	if (a.size()==0 || b.size()==0) printf("0\n");    	else    	{    		m1=0; m2=0; flag=true; s=0;    		while (m1<a.size() && m2<b.size())    		{    			while (flag && a[m1].r<b[m2].l )    			{    				m1++;    				if (m1==a.size()) {flag=false; break;}    			}    			while (flag && b[m2].r<a[m1].l )    			{    				m2++;    				if (m2==b.size()) {flag=false; break;}    			}    			if (flag)    			{    				x=max(a[m1].l,b[m2].l);    				y=min(a[m1].r,b[m2].r);    				if (y-x+1>=m) s+=(y-x+1-m+1);    				if (a[m1].r<b[m2].r) m1++;    					else if (a[m1].r>b[m2].r) m2++;    						else {m1++; m2++; }    			}    		}    		printf("%d\n",s);    	}    }    return 0;}