Educational Codeforces Round 89 (Rated for Div. 2) B. Shuffle (数学,区间)

• 题意:有长为\(n\)的排列,其中\(x\)位置上的数为\(1\),其余位置全为\(0\),询问\(m\)次,每次询问一个区间,在这个区间内可以交换任意两个位置上的数,问\(1\)最后出现在不同位置的次数.

• 题解:维护区间即可,如果某个区间包含了\(1\),更新最大的答案区间,(每次更新后说明这整个区间都能取到\(1\)).

• 代码:

  #include <iostream>
  #include <cstdio>
  #include <cstring>
  #include <cmath>
  #include <algorithm>
  #include <stack>
  #include <queue>
  #include <vector>
  #include <map>
  #include <set>
  #include <unordered_set>
  #include <unordered_map>
  #define ll long long
  #define fi first
  #define se second
  #define pb push_back
  #define me memset
  const int N = 1e6 + 10;
  const int mod = 1e9 + 7;
  const int INF = 0x3f3f3f3f;
  using namespace std;
  typedef pair<int,int> PII;
  typedef pair<ll,ll> PLL;
  
  int t;
  int l,r;
  int n,x,m;
  
  
  int main() {
      ios::sync_with_stdio(false);cin.tie(0);
  	cin>>t;
  	 while(t--){
  	 	cin>>n>>x>>m;
  	 	int mi=x;
  	 	int mx=x;
  	 	 for(int i=1;i<=m;++i){
  	 	 	cin>>l>>r;
  	 	 	if(l<=mi&&r>=mi){
  	 	 		mi=l;
  	 	 	}
  	 	 	if(l<=mx&&r>=mx){
  	 	 		mx=r;
  	 	 	}
  	 	 }
  	 	 printf("%d\n",mx-mi+1);
  	 }
  
      return 0;
  }