1. 关键观察

记第 i 个区间为 Ii = [li , ri]（li ≤ ri）。

因为 li , ri 都是单调不降的，任意两区间 不可能相交（即不会出现 li < lj ≤ ri < rj 的情形），只能在右侧出现以下两种情形：

  • 左间隙 li > l{i‑1} → 位置 l{i‑1} … li‑1 已经不再被后面的任何区间覆盖。
  • 右扩展 ri > r{i‑1} → 位置 r{i‑1}+1 … ri 第一次被区间覆盖。

于是我们得到一个「滑动窗口」式的过程：在整个扫描过程中，所有 尚未确定最终位置 的元素恰好构成 当前区间 [li , ri]（左端可能已经被弹出）。
对这些元素我们只需要知道 它们是否已经被翻转奇数次，即它们的相对顺序是 正序还是逆序。用一个布尔变量 rev（rev = true 表示逆序）来记录即可。

2. 线性算法（deque + rev）

状态

  • deque<int> dq —— 当前仍可能被后续区间翻转的子序列。
  • bool rev    —— rev == false 表示 dq 的头部对应子序列的左端；rev == true 表示 dq 的尾部对应子序列的左端（因为整段已被翻转奇数次）。
  • int preL = 1 , preR = 0 —— 上一个已经处理完的区间的左右端（初始时为空区间）。

对单个区间 [l , r] 的处理（设上一个区间为 [preL , preR]）

1. 处理右扩展（如果 r > preR）
      对 p = max(preR+1 , l) … r   // 这些位置第一次出现
          若 rev == false 则 dq.push_back(p);   // 正序
          否则               dq.push_front(p);  // 反序，实际在右端

2. 处理左间隙（如果 l > preL）
      对 p = preL … l‑1        // 这些位置已经被完全确定
          若 rev == false 则 answer.push_back(dq.pop_front());
          否则               answer.push_back(dq.pop_back());

3. 翻转当前区间
      rev = !rev;               // 等价于把 [l , r] 内部顺序翻转

4. 更新 preL = l , preR = r;

全部区间结束后

  • 位置 preR+1 … n 从未被任何区间覆盖，直接按原始顺序加入答案。
  • 还有一段仍留在 dq 中（对应最后一个区间的左端 lk 到 rk），根据 rev 决定弹出方向，依次加入答案。

3. 代码实现

#include <iostream>
#include <vector>
#include <deque>

int main() {
    // 1. 开启快速 I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, k;
    std::cin >> n >> k;

    // 存放最终结果的数组 (使用1-based索引，所以大小为 n+1)
    std::vector<int> result(n + 1);

    // 维护活跃区间的双端队列
    std::deque<int> dq;

    int num_to_add = 1; // 下一个要被加入活跃区间的数字 (从 1 开始)
    int fill_idx =
        1;   // 下一个要被填充的 result 数组的索引 (从 1 开始)
    bool is_reversed = false; // 活跃区间的翻转标记

    // 2. 处理 k 次操作
    for (int i = 0; i < k; ++i) {
        int l, r;
        std::cin >> l >> r;

        // 步骤 B : 添加新的活跃元素 (包括"空隙"中的元素)
        // 必须先把所有直到 r 的数字都加入 dq，才能安全地填充直到 l-1 的索引
        while (num_to_add <= r) {
            if (!is_reversed) {
                // 正序时，新数字加到队尾 (右端)
                dq.push_back(num_to_add);
            } else {
                // 逆序时，新数字加到队首 (右端)
                dq.push_front(num_to_add);
            }
            num_to_add++;
        }

        // 步骤 A : 确定 "最终" 的前缀
        // 将索引 [fill_idx, l-1] 范围内的元素从 dq 中取出，放入 result
        // 此时 dq 必定不为空 (因为 num_to_add > r >= l > fill_idx)
        while (fill_idx < l) {
            // if (dq.empty()) break; // <-- 移除这个错误的检查

            if (!is_reversed) {
                // 正序时，左端在队首
                result[fill_idx] = dq.front();
                dq.pop_front();
            } else {
                // 逆序时，左端在队尾
                result[fill_idx] = dq.back();
                dq.pop_back();
            }
            fill_idx++;
        }


        // 步骤 C: 执行翻转 (O(1) 操作)
        is_reversed = !is_reversed;
    }

    // 3. 处理 k 次操作后剩下的元素

    // 步骤 2.A: 添加所有剩余的数字 (从 num_to_add 到 n)
    while (num_to_add <= n) {
        if (!is_reversed) {
            dq.push_back(num_to_add);
        } else {
            dq.push_front(num_to_add);
        }
        num_to_add++;
    }

    // 步骤 2.B: 确定所有剩余的位置
    // 将 deque 中所有剩余元素按当前顺序填入 result 数组
    while (fill_idx <= n) {
        if (dq.empty()) break; // 最后的安全检查

        if (!is_reversed) {
            result[fill_idx] = dq.front();
            dq.pop_front();
        } else {
            result[fill_idx] = dq.back();
            dq.pop_back();
        }
        fill_idx++;
    }

    // 4. 输出结果
    for (int i = 1; i <= n; ++i) {
        std::cout << result[i] << (i == n ? "" : " ");
    }
    std::cout << "\n";

    return 0;
}