#P3141. [Hnoi2013]旅行

    ID: 2296 传统题 1000ms 512MiB 尝试: 515 已通过: 170 难度: 9 上传者: 标签>难度分类省选/NOI-排序与序列处理一维前缀和贪心保留最优候选单调队列消除被支配候选数据结构链表CF2600

[Hnoi2013]旅行

[HNOI2013] 旅行

题目描述

在遥远的 HX 国,旅行家小 L 想骑自行车游遍编号为 11 到 nn 的城市。每座城市或者有一个他想去的景点,或者没有这样的景点。小 L 用程序规划了一条经过所有这些景点的最短路线。按路线,他依次到达城市 a1,a2,…,ana_1,a_2,\ldots,a_n,在 ana_n 结束旅行。城市的访问顺序已经确定。

到达一座有景点的城市时,小 L 会先游览景点,获得 11 点快乐值。到达一座没有景点的城市时,他会获得 11 点疲劳值。他希望恰好用 mm 个月走完全程。每个月可以到达任意多座城市,但至少要到达一座新城市。他在每个月所到达的最后一座城市休息。

用 xix_i 表示第 ii 个月休息的城市编号,于是 xm=anx_m=a_n。例如,若 n=5n=5、m=3m=3、路线是 (3,2,4,1,5)(3,2,4,1,5),计划 (2,1,5)(2,1,5) 意味着第一个月游历城市 3,23,2,第二个月游历城市 4,14,1,第三个月游历城市 55。

对一份计划,令 did_i 为第 ii 个月获得的快乐值和疲劳值之差的绝对值。小 L 希望 max⁡1≤i≤mdi\max_{1\le i\le m}d_i 尽量小。如果有多份计划达到最小值,输出城市编号序列 (x1,…,xm)(x_1,\ldots,x_m) 字典序最小的一份。两个序列从第一个不同的元素开始比较,那个元素较小的序列字典序较小。

输入格式

第一行包含两个正整数 n,mn,m,分别表示城市数和旅行月数。

接下来 nn 行,第 ii 行包含两个整数 ai,bia_i,b_i。aia_i 是按路线第 ii 个到达的城市编号。bi=1b_i=1 表示该城市有小 L 想去的景点,bi=0b_i=0 表示没有。a1,…,ana_1,\ldots,a_n 是 1,…,n1,\ldots,n 的一个排列。

输出格式

输出一行 mm 个用空格分隔的整数 x1,x2,…,xmx_1,x_2,\ldots,x_m,表示最优计划中每个月休息时所在的城市编号。

样例

8 3
2 0
3 1
4 1
1 0
5 0
6 1
7 1
8 0
1 6 8

按样例输出,第一个月各获得 22 点快乐值和疲劳值,后两个月每月各获得 11 点快乐值和疲劳值。因此最大差值为 00。达到这个值的序列是 (1,6,8)(1,6,8)、(3,6,8)(3,6,8) 和 (3,1,8)(3,1,8),其中 (1,6,8)(1,6,8) 的字典序最小。

数据范围

本题数据满足 1≤m≤n≤5×1051\le m\le n\le 5\times10^5、m≤2×105m\le 2\times10^5。原题叙述给出 m<nm<n,本题数据含 m=nm=n,此时每个月恰好到达一座新城市。