传送门：

思路：一道杂技题....证明杂技，写的也杂技，13年最神的题

首先有一个结论

设S为+1和-1的总和，记sum为后缀和（为什么是后缀？因为做的时候要判后面是还否有解）

如果S！=0，那么ans=ceil(S/m)

否则如果sum[i]==0的个数>=m则为0，否则为1

证明及具体做法见一个详细的题解

deque是不能用的....

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define min(x,y) ((a[x])<(a[y])?(x):(y))#define abs(a) (a>=0?a:-(a))const int maxn=500010;using namespace std;int n,m,a[maxn],tot,sum[maxn],cnt[maxn];char ch;void read(int &x){	for (ch=getchar();!isdigit(ch);ch=getchar());	for (x=0;isdigit(ch);ch=getchar()) x=x*10+ch-'0';}struct node{int l,r,x;}line[maxn<<1];struct Tline{	int head,tail,len;	Tline(){head=tail=len=0;}	bool empty(){return !len;}	int newnode(int l,int r,int x){line[++tot]=(node){l,r,x};return tot;}	int front(){return line[head].x;}	int back(){return line[tail].x;}	void pop_back(){tail=line[tail].l,len--;}	void pop_front(){head=line[head].r,len--;}	void push_back(int x){		if (!len) head=tail=newnode(0,0,x);		else line[tail].r=newnode(tail,0,x),tail=line[tail].r;		len++;	}	void push(int x){		while (len&&a[back()]>a[x]) pop_back();		push_back(x);	}}Q[maxn<<1],Qu[maxn<<1],*q=Q+maxn,*qu=Qu+maxn;//是后缀和为i的单调队列，存有哪些点的后缀和为ivoid work(){	int S=sum[1],d=S?(abs(S)-1)/m+1:cnt[1]
         
          =m-i;j++) if (!sum[j+1]) q[0].push(j); printf("%d ",a[q[0].front()]); q[0].pop_front(); } } else{ for (int i=2;i<=n;i++) qu[sum[i]].push_back(i-1); int last=0;a[n+1]=n+1; for (int i=1;i
          
           d) continue; for (;!qu[j].empty()&&n-qu[j].front()>=m-i;qu[j].pop_front()) if (qu[j].front()>last) q[j].push(qu[j].front()); for (;!q[j].empty()&&q[j].front()<=last;q[j].pop_front()); if (!q[j].empty()) ans=min(ans,q[j].front()); } last=ans,printf("%d ",a[ans]); } } printf("%d\n",a[n]);}int main(){ read(n),read(m); for (int i=1;i<=n;i++) read(a[i]),read(sum[i]),sum[i]=sum[i]?1:-1; for (int i=n-1;i>=1;i--) sum[i]+=sum[i+1]; for (int i=n;i>=1;i--) cnt[i]=cnt[i+1]+(!sum[i]); work(); return 0;}/*8 32 13 14 11 05 06 17 18 0*/