[bzoj3141] [HNOI2013]旅行

Description

Input

第一行为两个空格隔开的正整数n, m，表示旅行的城市数与旅行所花的月数。接下来n行，其中第 i行包含两个空格隔开的整数Ai和Bi，Ai表示他第i个去的城市编号。Bi为0或1;如果Bi=0则表示城市Ai没有小L想去的景点，如果Bi=1则表示城市Ai有小L想去的景点，
Ai两两不同且有1<=Ai<=N,即{Ai}为1,2....N的一个排列。
例如{2,1,3,4...N}
N<=500000,M<=200000

Output

t仅包括一行，包含m个空格隔开的正整数X1,X2...Xm，t仅包括一行，包含m个空格隔开的正整数X1,X2...Xm，为给小L安排的旅行计划对应的路线。为给小L安排的旅行计划对应的路线。

Sample Input

Sample Output

1 6 8

Solution

由于要计算(0)的个数和(1)的个数，一个很显然的想法就是把(0)改成(-1)。

先不管字典序，考虑下答案应该是多少。

显然有这么两条性质：

若原数列只由(1)或(-1)构成，答案显然就是(lceilfrac{n}{k} ceil)。
否则，必定存在一段和为(0)的子数列，这段其实没有意义，随便和左边或右边合并都行。

所以可以把(-1)或(1)消掉一种，然后就变成了第一种情况。

答案就是：

[lceilfrac{|sum[1]|}{k} ceil ]

其中(sum[x])为数列的后缀和。

当然有一种特殊情况：上面的式子为(0)，但是没有(k)个(sum[x]=0)的点，显然凑不出(k)个和为(0)的段，所以这种情况答案是(1)。

然后考虑字典序怎么做：

如果答案为(0)，单调队列随便搞搞就行了。

否则的话，设上次选的位置为(l)，那么这次选的数的后缀和(s)显然要满足(|sum[l]-s|leqslant ans)，即(sum[l]-ansleqslant s leqslant ans+sum[l])。

所以对于(sum[x])相同的，把他们归为一类处理，然后用单调队列维护就行了。

注意选完这个数之后，后面形成了一个子问题，答案要不大于整个问题的答案，设当前选的数位置为(x)，即：

[lceilfrac{|sum[x+1]|}{n-x} ceilleqslant ans ]

注意负数下标特别处理，具体看代码。

#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}

const int maxn = 1e6+10;

struct data {int l,r,val;}w[maxn<<2];

int tot;

int n,k,id[maxn],t[maxn],sum[maxn],cnt[maxn];

struct Priority_Queue {
	int st,ed,len;
	int empty() {return !len;}
	void push_back(int x) {
		if(len) w[++tot]=(data){ed,0,x},w[ed].r=tot,ed=w[ed].r;
		else w[++tot]=(data){0,0,x},st=ed=tot;
		len++;
	}
	void pop_back() {ed=w[ed].l,len--;}
	void pop_front() {st=w[st].r,len--;}
	int back() {return w[ed].val;}
	int front() {return w[st].val;}
	void push(int x) {
		while(!empty()&&id[w[ed].val]>id[x]) pop_back();
		push_back(x);
	}
}alpha[maxn<<1],beta[maxn<<2],*q1=alpha+maxn,*q=beta+maxn;  //负数下标处理

int main() {
	read(n),read(k);
	for(int i=1;i<=n;i++) {read(id[i]),read(t[i]);if(!t[i]) t[i]--;}
	for(int i=n;i;i--) sum[i]+=sum[i+1]+t[i];
	for(int i=n;i;i--) cnt[i]=cnt[i+1]+(sum[i]==0);
	cnt[n+1]=-1;
	int ans=sum[1]?(abs(sum[1])+k-1)/k:(cnt[1]<k);
	if(!ans) {
		for(int i=1,j=2;i<k;i++) {
			for(;cnt[j+1]>=k-i;j++) if(!sum[j+1]) q[0].push(j);
			printf("%d ",id[q[0].front()]);q[0].pop_front();
		}
	} else {
		int l=0;id[n+1]=n+1;
		for(int i=2;i<=n;i++) q[sum[i]].push_back(i-1);
		for(int i=1;i<k;i++) {
			int s=n+1;
			for(int j=sum[l+1]-ans;j<=sum[l+1]+ans;j++) {
				if((abs(j)+k-i-1)/(k-i)>ans) continue;
				while(!q[j].empty()&&n-q[j].front()>=k-i) {
					if(q[j].front()>l) q1[j].push(q[j].front());
					q[j].pop_front();
				} 
				while(!q1[j].empty()&&q1[j].front()<=l) q1[j].pop_front();
				if(!q1[j].empty()) if(id[s]>id[q1[j].front()]) s=q1[j].front();
			}
			l=s;printf("%d ",id[s]);
		}
	}printf("%d
",id[n]);
	return 0;
}