记录编号	269005	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]白雪皑皑	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	1.941 s
提交时间	2016-06-13 06:13:05	内存使用	30.83 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=1000100;
int n,m,p,q;
struct Event{
	bool in;//true表示进入,false表示移出
	int pos,num;
	bool operator<(const Event& x)const{
		if(pos!=x.pos)return pos<x.pos;
		return in;//in必须放在out前面,因为是左闭右开区间[l,r)
	}
}a[maxn<<1];
int r[maxn];
int heap[maxn];
void push(int);
int& top();
int pop();
int main(){
	freopen("winter.in","r",stdin);
	freopen("winter.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&p,&q);
	if(m<=n){
		for(int i=1,s,t;i<=m;i++){
			s=(i*p+q)%n+1;
			t=(i*q+p)%n+1;
			if(s>t)swap(s,t);
			t++;
			r[i]=t;
			a[i].pos=s;
			a[i].in=true;
			a[i+m].pos=t;
			a[i+m].in=false;
			a[i].num=a[i+m].num=i;
		}
		sort(a+1,a+(m<<1)+1);
		heap[heap[0]=1]=0;
		r[0]=0x7ffffff;
		for(int i=1,k=1;i<=n;i++){
			if(k<=(m<<1))while(a[k].pos==i){
				if(a[k].in==true)push(a[k].num);
				else while(i>=r[top()])pop();
				k++;
			}
			printf("%d\n",top());
		}
	}
	else{
		for(int i=1,j,s,t;i<=n;i++){
			j=i+(m-n);
			s=(j*p+q)%n+1;
			t=(j*q+p)%n+1;
			if(s>t)swap(s,t);
			t++;
			r[i]=t;
			a[i].pos=s;
			a[i].in=true;
			a[i+n].pos=t;
			a[i+n].in=false;
			a[i].num=a[i+n].num=i;
		}
		sort(a+1,a+(n<<1)+1);
		push(0);
		r[0]=0x7ffffff;
		for(int i=1,k=1;i<=n;i++){
			if(k<=(m<<1))while(a[k].pos==i){
				if(a[k].in==true)push(a[k].num);
				else while(i>=r[top()])pop();
				k++;
			}
			printf("%d\n",(top()?top()+m-n:0));
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
inline void push(int x){
	heap[++heap[0]]=x;
	push_heap(heap+1,heap+heap[0]+1);
}
inline int& top(){
	return heap[1];
}
inline int pop(){
	int x=heap[1];
	pop_heap(heap+1,heap+heap[0]+1);
	heap[0]--;
	return x;
}