浅谈队列：https://www.cnblogs.com/AKMer/p/10314965.html
题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=3141
很好的一道单调队列题……
先把\(0\)变成\(-1\)，然后\(sum_i\)表示\([i,n]\)的后缀和。
首先考虑子段和最大值最小是多少。
首先，答案最小不会小于\(\lceil \frac{|sum_1|}{m}\rceil\)
其次，假设相邻的\(1\)或\(-1\)全部合并在一起变成\(0\)抵消掉（因为不管放在哪一段都无影响），留下\(|sum_1|\)个\(1\)或\(-1\)，直接均分，刚好可以使最大值是\(\lceil \frac{|sum_1|}{m}\rceil\)，所以答案就是这个玩意儿。
但是当\(sum_1\)等于\(0\)且后缀和为\(0\)的\(pos\)个数小于\(m\)时答案就是\(1\)，因为分不出那么多段。
在知道答案后，我们再分情况讨论字典序：
当答案等于\(0\)时，直接把后缀和等于\(0\)的前一个点拎出来用单调队列搞搞就行。
当答案不等于\(0\)，我们考虑假设第\(i\)段结尾的是\(lst\)，那么第\(i+1\)段结尾处后一个位置的后缀和\(s\)要满足\(|sum[lst+1]-s|\leqslant ans\)。
展开一下：\(sum[lst+1]-ans\leqslant s \leqslant sum[lst+1]+ans\)
然后对于每种不同的后缀和维护一个单调队列即可。
每次根据上面的等式枚举下一个\(s\)，然后对于子问题\(\lceil\frac{|s|}{m-i}\rceil\)不会超过全局问题的答案，并且后面够分\(m-i\)段，就把他丢到对应的单调队列里面。然后对于每个单调队列的队头拿出来比较选最好的一个就行了。
为啥要开多个单调队列而不是用一个单调队列呢？因为对于每个子问题，所满足的后缀和\(s\)并不一样，不能用当前子问题的\(s'\)把\(s''\)的队头弹掉了，万一下一次只支持\(s''\)而不支持\(s'\)并且之前被你弹掉的那个就是答案呢？
剩下的细节见代码吧。
时间复杂度：\(O(n\sqrt{n})\)
空间复习度：\(O(n)\)
代码如下：
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1e6+6;
int n,m,ans,num,val;
int id[maxn],like[maxn],sum[maxn],cnt[maxn];
int tot[maxn],tmp[maxn],list[maxn],stk[maxn];
int read() {
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
return x*f;
}
struct Queue {
int head,tail;
void push_back(int pos) {
while(head!=tail&&id[list[tail-1]]>id[pos])tail--;
list[tail++]=pos;
}
int front() {return list[head];}
void pop_front() {if(head!=tail)head++;}
bool empty() {return head==tail;}
}alpha[maxn<<1],*q=alpha+maxn;
struct Stack {
int tp,cnt;
void push_back(int pos) {cnt++;stk[++tp]=pos;}
bool empty() {return !cnt;}
int top() {return stk[tp];}
void pop() {tp--;cnt--;}
}beta[maxn<<1],*s=beta+maxn;
int main() {
n=read(),m=read();
for(int i=1;i<=n;i++)
id[i]=read(),like[i]=read();
for(int i=n;i;i--) {
like[i]-=(!like[i]);
tmp[i]=sum[i]=sum[i+1]+like[i];
cnt[i]=cnt[i+1]+(!sum[i]);
}
ans=sum[1]?(abs(sum[1])+m-1)/m:cnt[1]<m;
if(!ans) {
for(int i=1,j=2;i<m;i++) {
for(;j<=n&&cnt[j+1]>=m-i;j++)
if(!sum[j+1])q[0].push_back(j);
int res=q[0].front();q[0].pop_front();
printf("%d ",id[res]);
}
}
else {
sort(tmp+1,tmp+n+1);
num=unique(tmp+1,tmp+n+1)-tmp-1;
for(int i=1;i<=n;i++)
tot[lower_bound(tmp+1,tmp+num+1,sum[i])-tmp]++;
for(int i=1;i<=num;i++) {
s[tmp[i]].tp=val;
q[tmp[i]].head=q[tmp[i]].tail=val;
val+=tot[i];
}
int lst=0;id[n+1]=n+1;
for(int i=n;i>1;i--)s[sum[i]].push_back(i-1);
for(int i=1;i<m;i++) {
int res=n+1;
for(int j=sum[lst+1]-ans;j<=sum[lst+1]+ans;j++) {
if((abs(j)+m-i-1)/(m-i)>ans)continue;
while(!s[j].empty()&&n-s[j].top()>=m-i) {
if(s[j].top()>lst)q[j].push_back(s[j].top());
s[j].pop();
}
while(!q[j].empty()&&q[j].front()<=lst)q[j].pop_front();
if(!q[j].empty()&&id[q[j].front()]<id[res])res=q[j].front();
}
lst=res;printf("%d ",id[res]);
}
}
printf("%d\n",id[n]);
return 0;
}