这应该是这道题最易懂的题解了

题意粗解：

我们想要对一段连续递增的序列1,2,3...n进行[l, r]区间k次翻转，其中翻转区间可以不同。

暴力枚举：

我们很容易想到进行暴力枚举，即将每次将序列[l,r]区间进行枚举，将其进行翻转。利用reverse即可做到这一点。

但显然，时间复杂度为o(n*k)，在 n,k <= 1e5 的情况下，即便是吸氧也无法保证不超时，所以我们必须换一个思路。

题目再观察：

观察题目可以发现：保证每次翻转的区间的起始点与终点都是非递减的，也就是说每次的l与r必定大于等于前一个l与r。

不难看出，这种情况是无后效性的。什么意思呢？

即：对于所有的i < l（这次操作的左端点），序列a_i在之后的操作中均不会再次发生变化，即进行翻转。他就被抛弃了

而对于r（右端点）来说，r只能加，也就是只能向右探索更多元素，而无法从右边舍弃已探索的元素。

所以，这实际上是滑动窗口问题。

开始构造：

鉴于滑动窗口问题的模版，我们考虑双端队列。

也就是说，我们不需要考虑一个元素被翻转了多少次，翻转到了哪里，只需考虑在某个特定区间内，该区间处于正序还是逆序。

比如在这个样例：1 2 3 4 5

假如我们想要对[2,4]区间进行翻转，我们就可以将{2,3,4}这个想要翻转的连续子区间储存下来，将其“逆序”。

然后逆序输出，即：1 {4 3 2} 5

接下来，假如出现了同样的操作[2,4]，那么我们再将其从逆序转为正序输出即可。

那如果未来出现了[3,4]呢？

同样的可以观察：l从2变为了3，而方才我们注意到无后效性。也就是说，序列a[2]在进行翻转后永远不会再发生变化了。我们可以理解为：它不再活跃了。此时我们可以将它甩出去并输出。

比如： 1 {4 3 2} 5

滑动后：1 4 {3 2} 5

逆序： 1 4 {2 3} 5

可以看见，窗口滑动后，逆序的窗口滑出了第一个元素，即滑出了原来正序窗口中的最后一个元素。

但是，我们一味地将窗口进行逆序，k次操作下来仍然是o（n*k）的时间复杂度。那有没有办法进行优化呢？

我们可以考虑用nx储存该窗口是否逆序。每翻转一次，就将nx 变为 !nx。nx为1时代表该窗口逆序，否则该窗口为正序。

当该窗口逆序时，我们从滑出最后的元素，否则滑出最前面的元素。这与双端队列的操作恰好吻合。

同样的，加入新来的元素，当该窗口正序时，我们从后面加入元素，否则从前面加入元素。

样例分析：

1 3

2 4

2 5

实际数组翻转后数组

第一步：{1 2 3} 4 5，nx = 0 {3 2 1} 4 5

第二步：3 {1 2} 4 5，nx = 1 3 {2 1} 4 5 滑出旧元素

3 {4 1 2} 5，nx = 1 3 {2 1 4} 5 加入新元素

3 {4 1 2} 5，nx = 0 3 {4 1 2} 5 翻转

第三步：3 {4 1 2 5}，nx = 0 3 {4 1 2 5}

3 {4 1 2 5}，nx = 1 3 {5 2 1 4}

最终数组：3 5 2 1 4

所以，构造完成~~~

你看这个赞，他又大又圆qwq

新人，码风不好望大佬们见谅0rz

#include<iostream>
#include<deque>
using namespace std;

int main(){
    deque<int> huo;//储存活跃的元素
    int n, k, l = 1, r = 1;
    bool nx = 0;//逆序标记
    cin >> n >> k;
    while(k--){
        int left, right;
        cin >> left >> right;
        //滑出并输出旧元素
        while(l < left){
            if(huo.empty()) cout << l << ' ';//若窗口没元素，说明该元素位置不变
            else{
                if(nx){cout << huo.back() << ' ';huo.pop_back();}
                else {cout << huo.front() << ' ';huo.pop_front();}
            }
            l++;
            if(r < l) r++;//如果l>r，同时更新l与r
        }
        //添加新元素
        while(r <= right){
            if(nx) huo.push_front(r);
            else huo.push_back(r);
            r++;
        }
        nx = !nx;//逆序正序互换
    }
    //如果活跃的元素没有输出完
    while(!huo.empty()){
        if(nx){cout << huo.back() << ' ';huo.pop_back();}
        else {cout << huo.front() << ' ';huo.pop_front();}
    }
    //特殊情况：右边还有一些元素并未进行翻转
    while(r <= n){
        cout << r << ' ';
        r++;
    }
    return 0;//好习惯
}