Official

B - Subsegment Reverse Editorial by en_translator


For beginners

Approach 1. Actually construct an array, and apply reversion

For example, one can solve the problem by construct the sequence \(A=(1,2,\dots,N)\) as an array, reverse the \(L\)-th through \(R\)-th elements, and print the result.
There are several ways to reverse a consecutive subarray of an array.

  • First, let \(l=L\) and \(r=R\). While \(l<r\):
    • Swap the \(l\)-th and \(r\)-th element, and add \(1\) to \(l\) and subtract \(r\) from \(1\).
  • Use a feature of a standard library.

Note that the first element might be treated as the \(0\)-th one depending on a usage of an array.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N,L,R;
  cin >> N >> L >> R;
  vector<int> A(N+5);
  for(int i=1;i<=N;i++){
    A[i]=i;
  }
  while(L<R){
    swap(A[L],A[R]);
    L++; R--;
  }
  for(int i=1;i<=N;i++){
    if(i!=1){cout << " ";}
    cout << A[i];
  }cout << "\n";
  return 0;
}

Sample code 2 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N,L,R;
  cin >> N >> L >> R;
  vector<int> A(N+5);
  for(int i=1;i<=N;i++){
    A[i]=i;
  }
  reverse(A.begin()+L,A.begin()+R+1);
  for(int i=1;i<=N;i++){
    if(i!=1){cout << " ";}
    cout << A[i];
  }cout << "\n";
  return 0;
}

Approach 2: directly construct the sought sequence

The sought sequence has the following structure:

  • First, arrange \(1,2,\dots,L-1\) in this order.
  • Next, arrange \(R,R-1,\dots,L\) in this order.
  • Finally, arrange \(R+1,R+2,\dots,N\) in this order.

One can construct this sequence directly using for loops.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N,L,R;
  cin >> N >> L >> R;
  vector<int> res;

  for(int i=1;i<=L-1;i++){res.push_back(i);}
  for(int i=R;i>=L;i--){res.push_back(i);}
  for(int i=R+1;i<=N;i++){res.push_back(i);}

  for(int i=0;i<N;i++){
    if(i){cout << " ";}
    cout << res[i];
  }cout << "\n";
  return 0;
}

posted:
last update: