是

*问题分析
本题的核心是最小化最大值 + 字典序最小构造，需将旅行路线分割为 m 个连续段，满足每个段的快乐值与疲劳值差值的绝对值的最大值最小，且分割后的休息城市序列字典序最小。
关键转化
定义前缀和 s[i]：前 i 个城市中，有景点（b=1）的数量减去无景点（b=0）的数量。
对于段 [l, r]，快乐值 - 疲劳值 = s[r] - s[l-1]，其绝对值为 |s[r] - s[l-1]|。
问题转化为：将 1~n 分割为 m 个连续段，使各段的 |s[r]-s[l-1]| 的最大值最小，且分割点的城市编号序列字典序最小。
解题思路

1. 二分查找最小最大值 D
   通过二分枚举 D（差值绝对值的最大值），判断是否存在分割方式将 1~n 分为 m 段，每段的 |s[r]-s[l-1]| ≤ D。
2. 线段树优化可行性检查
   用线段树维护s值对应的最小分段数，快速查询满足条件的分段数，保证检查效率为 O(n log n)。
3. ST 表构造字典序最小分割
   预处理城市编号的区间最小值位置（ST 表），在满足条件的分割点中选择城市编号最小的，保证字典序最小。
   完整代码*

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

typedef long long ll;
const int MAXN = 5e5 + 10;
const int INF = 0x3f3f3f3f;
const int LOG = 20;

int n, m;
int a[MAXN], b[MAXN];
int s[MAXN]; // 前缀和：s[0]=0, s[i] = s[i-1] + (b[i]==1 ? 1 : -1)
int f[MAXN]; // f[i]：从i到n恰好需要分几段（-1表示不可行）

// 线段树：维护区间最小值（用于check函数）
struct SegTree {
    int n;
    vector<int> tree;
    SegTree(int size) : n(size) {
        tree.assign(2 * n, INF);
    }
    void update(int pos, int val) {
        pos += n;
        if (val < tree[pos]) tree[pos] = val;
        for (pos >>= 1; pos >= 1; pos >>= 1) {
            tree[pos] = min(tree[2*pos], tree[2*pos+1]);
        }
    }
    int query(int l, int r) { // [l, r]闭区间查询最小值
        l += n;
        r += n;
        int res = INF;
        while (l <= r) {
            if (l % 2 == 1) res = min(res, tree[l++]);
            if (r % 2 == 0) res = min(res, tree[r--]);
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
};

// ST表：维护区间内a[r]最小的位置（字典序用）
int st[MAXN][LOG];
int lg[MAXN];

void init_st() {
    lg[1] = 0;
    for (int i = 2; i <= n; ++i) lg[i] = lg[i/2] + 1;
    for (int i = 1; i <= n; ++i) st[i][0] = i;
    for (int j = 1; j < LOG; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            int p1 = st[i][j-1];
            int p2 = st[i + (1 << (j-1))][j-1];
            st[i][j] = (a[p1] < a[p2]) ? p1 : p2;
        }
    }
}

// 查询[l, r]中a值最小的位置
int get_min_pos(int l, int r) {
    if (l > r) return -1;
    int k = lg[r - l + 1];
    int p1 = st[l][k];
    int p2 = st[r - (1 << k) + 1][k];
    return (a[p1] < a[p2]) ? p1 : p2;
}

// 检查D是否可行：能否将1~n恰好分为m段，每段|s[r]-s[l-1]| ≤ D，且每段至少1个城市
bool check(int D) {
    memset(f, -1, sizeof(f));
    f[n] = 0; // 从n到n恰好0段
    int offset = n; // s∈[-n,n] → 偏移为[0,2n]
    int seg_size = 2 * n + 2; // 确保覆盖所有偏移
    SegTree seg(seg_size);
    seg.update(s[n] + offset, f[n]);

    // 从后往前计算f[i]：i到n恰好需要分几段
    for (int i = n - 1; i >= 0; --i) {
        int L = s[i] - D + offset;
        int R = s[i] + D + offset;
        L = max(L, 0);
        R = min(R, 2 * n);
        int min_f = seg.query(L, R);
        if (min_f != INF) {
            f[i] = min_f + 1;
        }
        // 仅当f[i]有效时更新线段树
        if (f[i] != -1) {
            seg.update(s[i] + offset, f[i]);
        }
    }
    // 必须恰好m段，且每段至少1个城市（f[0]=m且分割点间隔≥1）
    return f[0] == m;
}

// 构造字典序最小的分割序列
vector<int> construct(int D) {
    // 重新计算f数组（确保恰好分段）
    memset(f, -1, sizeof(f));
    f[n] = 0;
    int offset = n;
    int seg_size = 2 * n + 2;
    SegTree seg(seg_size);
    seg.update(s[n] + offset, f[n]);

    for (int i = n - 1; i >= 0; --i) {
        int L = s[i] - D + offset;
        int R = s[i] + D + offset;
        L = max(L, 0);
        R = min(R, 2 * n);
        int min_f = seg.query(L, R);
        if (min_f != INF) {
            f[i] = min_f + 1;
        }
        if (f[i] != -1) {
            seg.update(s[i] + offset, f[i]);
        }
    }

    init_st();
    vector<int> res;
    int prev = 0; // 上一个分割点（初始为0）

    for (int k = 1; k <= m; ++k) {
        int target = m - k; // 剩余需要恰好分target段
        int start = prev + 1; // 本段至少1个城市，起始≥prev+1
        int end = n;
        if (k == m) end = n; // 最后一段必须到n

        // 第一步：找所有满足条件的r ∈ [start, end]
        // 条件1: |s[r] - s[prev]| ≤ D
        // 条件2: f[r] == target（剩余恰好分target段）
        vector<int> valid_r;
        int best_pos = -1;
        int min_val = INF;

        // 优化：二分找valid_r的范围，避免遍历
        int l = start, r = end;
        int left = -1;
        // 找第一个满足条件的r
        while (l <= r) {
            int mid = (l + r) / 2;
            if (abs(s[mid] - s[prev]) <= D && f[mid] == target) {
                left = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if (left == -1) { // 无合法r，退而求其次找f[r]<=target（容错）
            l = start, r = end;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (abs(s[mid] - s[prev]) <= D && f[mid] <= target) {
                    left = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
        }
        if (left == -1) left = start;

        // 找最后一个满足条件的r
        l = start, r = end;
        int right = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (abs(s[mid] - s[prev]) <= D && f[mid] == target) {
                right = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if (right == -1) {
            l = start, r = end;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (abs(s[mid] - s[prev]) <= D && f[mid] <= target) {
                    right = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        if (right == -1) right = end;

        // 确保区间有效
        left = max(left, start);
        right = min(right, end);

        // 找[left, right]中a[r]最小的位置
        best_pos = get_min_pos(left, right);
        if (best_pos == -1) best_pos = left;

        res.push_back(a[best_pos]);
        prev = best_pos;

        // 最后一段强制到n
        if (k == m - 1) prev = n - 1;
    }

    // 确保最后一个元素是a[n]
    if (!res.empty()) res.back() = a[n];
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
    }

    // 计算前缀和s
    s[0] = 0;
    for (int i = 1; i <= n; ++i) {
        s[i] = s[i-1] + (b[i] == 1 ? 1 : -1);
    }

    // 二分找最小的D
    int left = 0, right = n, D_min = n;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (check(mid)) {
            D_min = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    // 构造答案
    vector<int> ans = construct(D_min);
    for (int i = 0; i < ans.size(); ++i) {
        if (i > 0) cout << " ";
        cout << ans[i];
    }
    cout << endl;

    return 0;
}