题解

设原序列中第 $i$ 个城市的“快乐值–疲劳值”贡献分别为 $+1/-1$，对其做前缀和即可把任意一段的净快乐值写成 b[r] - b[l-1]，其中 $b[i]$ 表示前 $i$ 个城市的净差。我们要把整条路线划成 $m$ 段，使得每段的净差绝对值的最大值最小，再在最优值下取字典序最小的分割点。

首先观察答案的下界：整段旅行的净差为 |b[n]|，即使用 $m$ 段至少也要有一段的绝对值不小于 $\lceil |b[n]| / m \rceil$。证明可知这个下界总是可行的，因此直接把它当成目标上限 $ans$。
随后，把所有 $b[i]$ 的取值离散化到区间 $[l, r]$，按照差值把下标分桶，并为每个桶维护一个单调队列（队列中按出现顺序存放当前还未“过期”的城市编号并保持编号递增）。我们沿着原路线扫描，当指针 $j$ 向前移动时，就把城市 $j$ 放入对应桶的队列中——这意味着我们允许本月在城市 $j$ 结束。

在选择第 $i$ 个月的休息城市时，既要保证本段的净差不超过 $ans$，也要保证剩余月份仍有希望完成旅程。前一个条件对应 $|b[j] - b[lst]| \le ans$；后一个条件可以转化成当前结束时的前缀差 $b[j]$ 与终点的差 $b[n]$ 在剩余月份内仍有可能被摊平，即 $|b[n] - b[j]| \le ans \times (m - i)$。满足条件的候选在对应桶的队列里取（由于队列维护的是递增的城市编号且及时弹出已经被划分到前面月份的“过期城市”，我们总能拿到字典序最小的方案）。

依次确定 $m-1$ 个分割点，最后一个月必然停在 $a_n$。该做法始终在线性时间内扫描序列及桶，总复杂度 $O(n \log n)$（由离散化带来的排序开销）即可解决问题。

#include <bits/stdc++.h>
using namespace std;
int n,m,a[500005],b[500005],head[500005],tail[500005],pos[500005],l,r;
vector<int> v[500005],stk[500005];
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i]>>b[i],pos[a[i]]=i,b[i]+=1-3*b[i]+b[i-1],l=min(l,b[i]),r=max(r,b[i]);
	for(int i=0;i<=r-l;i++) v[i].push_back(0),head[i]=1;
	for(int i=1;i<=n;i++) v[b[i]-l].push_back(i);
	for(int i=0;i<=r-l;i++) stk[i].resize(v[i].size());
	if(!b[n]&&v[-l].size()>m){
		for(int i=1,j=1;i<m;i++){
			for(;j<v[-l].size()-m+i;j++){
				while(head[-l]<=tail[-l]&&stk[-l][tail[-l]]>a[v[-l][j]]) tail[-l]--;
				stk[-l][++tail[-l]]=a[v[-l][j]];
			}
			cout<<stk[-l][head[-l]]<<' ',head[-l]++;
		}
		cout<<a[n]<<'\n';
		return 0;
	} 
	int ans=(abs(b[n])-1)/m+1;
	for(int i=1,j=1,lst=0;i<m;i++){
		for(;j<=n-m+i;j++){
			int x=b[j]-l;
			while(head[x]<=tail[x]&&stk[x][tail[x]]>a[j]) tail[x]--;
			stk[x][++tail[x]]=a[j];
		}
		int L=max(l,b[lst]-ans),R=min(r,b[lst]+ans),res=n+1;
		for(int j=L;j<=R;j++)
			if(abs(b[n]-j)<=ans*(m-i)){
				while(head[j-l]<=tail[j-l]&&pos[stk[j-l][head[j-l]]]<=lst) head[j-l]++;
				if(head[j-l]<=tail[j-l]) res=min(res,stk[j-l][head[j-l]]);
			}
		cout<<res<<' ',lst=pos[res];
	}
	cout<<a[n]<<'\n'; 
	return 0;
}