题解：CF1366B Shuffle

暴力

先从暴力写起。枚举 $l\sim r$，如果区间内有一个$1$，那么就将给区间内的所有数字都变成 $1$。

#include<bits/stdc++.h>
#include<cstring>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<map>
#define ll long long
#define lhs printf("\n");
using namespace std;
const int N=1e7+10;
const int M=2024;
const int inf=0x3f3f3f3f;
int t,n,m,x; 
bool a[N];
int l,r,ans;
int main()
{scanf("%d",&t);while(t--){ans=0;memset(a,0,sizeof a);scanf("%d%d%d",&n,&x,&m);a[x]=1;for(int i=1;i<=m;i++){scanf("%d%d",&l,&r);bool flag=0;for(int j=l;j<=r;j++){if(a[j]==1){flag=1;break;}}if(flag){	for(int j=l;j<=r;j++){a[j]=1;} }}for(int i=1;i<=n;i++)if(a[i])ans++;printf("%d\n",ans);}return 0;
}

但是看到数据范围 $n\le 10^9$，这个范围,数组不仅开不下，而且还会超时。那么考虑正解。

思路

由于每次扩充区间都是连续的，所以只需要记录该序列的左端点坐标与右端点坐标。每次更新两端的坐标即可。

代码

#include<bits/stdc++.h>
#include<cstring>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<map>
#define ll long long
#define lhs printf("\n");
using namespace std;
const int N=1e7+10;
const int M=2024;
const int inf=0x3f3f3f3f;
int t,n,m,x; 
bool a[N];
int l,r,ansl,ansr;
int main()
{scanf("%d",&t);while(t--){memset(a,0,sizeof a);scanf("%d%d%d",&n,&x,&m);ansl=ansr=x;//初始区间for(int i=1;i<=m;i++){scanf("%d%d",&l,&r);if(l<=ansl and ansl<=r){ansl=min(ansl,l);}if(l<=ansr and ansr<=r){ansr=max(ansr,r);}}printf("%d\n",ansr-ansl+1);}return 0;
}