题解 | 区间翻转（本蒟蒻的第一篇题解）

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    ll n,k;
    cin>>n>>k;
    deque<ll>dq;
    vector<pair<ll,ll>>all(k+1);
    for(ll i=1;i<=k;i++)
    {
        cin>>all[i].first>>all[i].second;
    }
    vector<ll>ans(n+1);
    for(ll i=1;i<=n;i++)
    {
        ans[i]=i;
    }
    ll dir=1;
    ll prel=0,prer=0;
    for(ll i=1;i<=k;i++)
    {
        ll len=dq.size();
        if(len>0)
        {
            if(dir==1)
            {
                for(ll j=prer+1;j<=all[i].second;j++)
                {
                    dq.push_back(ans[j]);
                }
            }
            else 
            {
                for(ll j=prer+1;j<=all[i].second;j++)
                {
                    dq.push_front(ans[j]);
                }
            }
        }
        else 
        {
            for(ll j=all[i].first;j<=all[i].second;j++)
            {
                dq.push_back(ans[j]);
            }
        }
        if(i<k&&all[i].second>=all[i+1].first)
        {
            for(ll j=all[i].first;j<=all[i+1].first-1;j++)
            {
                if(dir==1)
                {
                    ans[j]=dq.back();
                    dq.pop_back();
                }
                else 
                {
                    ans[j]=dq.front();
                    dq.pop_front();
                }
            }
            dir=-dir;
        }
        else 
        {
            for(ll j=all[i].first;j<=all[i].second;j++)
            {
                if(dir==1)
                {
                    ans[j]=dq.back();
                    dq.pop_back();
                }
                else 
                {
                    ans[j]=dq.front();
                    dq.pop_front();
                }
            }
            dir=1;
        }
        prel=all[i].first;
        prer=all[i].second;
    }

    for(ll i=1;i<=n;i++)
    {
        cout<<ans[i]<<' ';
    }
    cout<<'\n';
    return 0;
}

这道题的区间翻转操作可以形象的理解为一个不定长的线段在一个数组上不断地翻滚。为了模拟这个翻滚的过程，这里使用双端队列来维护。当上一个区间和当前区间有部分重合时，则覆盖上一个区间的线段的的一部分可以截取下来，根据上一次的方向在头或尾加上当前区间的部分，而没有重合的部分对之后的区间没有影响，可以直接录入答案。