题解 | 区间翻转

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,k,add=1,fill=1;
    cin>>n>>k;
   vector<int>ans(n+1,0);
   deque<int>dq;
   bool isreverse=false;
   while(k--){
    int l,r;
    cin>>l>>r;
    while(add<=r){
        if(!isreverse){
            dq.push_back(add);
        }
        else dq.push_front(add);
        add++;
    }
    while(fill<l){
        if(!isreverse){
            ans[fill]=dq.front();
            dq.pop_front();
        }
        else {
            ans[fill]=dq.back();
            dq.pop_back();
        }
        fill++;
    }
    isreverse=!isreverse;
   }
   while(add<=n){
    if(!isreverse)dq.push_back(add);
    else dq.push_front(add);
    add++;
   }
   while(fill<=n){
    if(!isreverse){
        ans[fill]=dq.front();
        dq.pop_front();
    }
    else {
        ans[fill]=dq.back();
        dq.pop_back();
    }
    fill++;
   }
   for(int i=1;i<=n;i++){
    cout<<ans[i]<<" ";
   }
}
// 64 位输出请用 printf("%lld")

好题，双端队列模拟翻转，物理上的首尾分别对应逻辑上翻转后的左端和右端，我们总是左端出右端进是不会变的，而我们用双端队列模拟的话，在不借助任何工具下直接通过首尾判断左右端是不准确的，所以引入bool，不同状态下对应不同的入队和出队方式。