题解 | 区间翻转

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

int main() {
    int n, k;
    cin >> n >> k;
    int last = 1, pos = 0;
    deque<int> dq;
    int dir = 0;
    auto push = [&](int x) -> void {
        if (dir == 0) {
            dq.push_back(x);
        }
        else {
            dq.push_front(x);
        }
    };
    auto pop = [&]() -> void {
        if (dir == 0) {
            cout << dq.front() << " ";
            dq.pop_front();
        }
        else {
            cout << dq.back() << " ";
            dq.pop_back();
        }
    };
    while (k--) {
        int l, r;
        cin >> l >> r;
        while (pos < r) {
            push(pos + 1);
            pos++;
        }
        while (last < l) {
            pop();
            last++;
        }
        dir ^= 1;
    }
    while (pos < n) {
        push(pos + 1);
        pos++;
    }
    while (last <= n) {
        pop();
        last++;
    }
}

由于这题翻转的区间的起始点是单调不减的，所以我们可以用一个双端队列来维护翻转的区间，维护的区间右端点向右移动相当于push元素，左端点向右移动相当于pop元素，每次操作完之后更改一下入队出队的方向即可维护翻转的操作。