记录编号	416501	评测结果	AAAATTTTTT
题目名称	[HZOI 2016]白雪皑皑	最终得分	40
用户昵称	JustWB	是否通过	未通过
代码语言	C++	运行时间	6.365 s
提交时间	2017-06-21 20:56:54	内存使用	118.57 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
const int maxn=1e6+5;
const int maxm=1e7+5;
using namespace std;
struct zjg
{
    int l,r;
    int color;
    bool operator < (const zjg you)const{return l<you.l;}
}me[maxm];
int n,m,p,q,c;
int al,bl,ar,br,ac,bc;
int N[maxn];
priority_queue<zjg> heap;
void water(int now,int l,int r);
int main()
{
     freopen("winter.in","r",stdin);
     freopen("winter.out", "w", stdout);
    scanf("%d%d%d%d",&n,&m,&p,&q);
    for(int i=1;i<=m;i++)
    {
        int a=(i*p+q)%n+1,b=(i*q+p)%n+1;
        me[i].l=min(a,b);
        me[i].r=max(a,b);
//        printf("%d %d\n",me[i].l,me[i].r);
    }
    for(int i=1;i<=m;i++){c=i;water(i+1,me[i].l,me[i].r);}
    bl=-heap.top().l;br=heap.top().r;bc=heap.top().color;
    al=-1;ar=1;ac=0;
    heap.pop();
    while(!heap.empty())
    {
        if(al==-1)
        {
            for(int i=ar+1;i<bl;i++)printf("%d\n",ac);
            al=bl,ar=br,ac=bc;
            bl=-heap.top().l;br=heap.top().r;bc=heap.top().color;
            continue;
        }
        heap.pop();
        for(int i=al;i<=ar;i++)printf("%d\n",ac);
        for(int i=ar+1;i<bl;i++)printf("0\n");
        al=bl;ar=br;ac=bc;
        if(heap.empty())break;
        bl=-heap.top().l;br=heap.top().r;bc=heap.top().color;
    }
    if(al==bl&&ar==br&&ac==bc)
    {
        for(int i=bl;i<=br;i++)printf("%d\n",bc);
        for(int i=br+1;i<=n;i++)printf("0\n");
        return 0;
    }
    for(int i=al;i<=ar;i++)printf("%d\n",ac);
    for(int i=ar+1;i<bl;i++)printf("0\n");
    for(int i=bl;i<=br;i++)printf("%d\n",bc);
    for(int i=br+1;i<=n;i++)printf("0\n");
    return 0;
}
void water(int now,int l,int r)
{
    for(int i=now;i<=m;i++)
    {
        if(l>r)return;
        if(l<me[i].l&&r>=me[i].l&&r<me[i].r)r=me[i].l-1;
        else if(l<=me[i].r&&r>me[i].r&&l>me[i].l)l=me[i].r+1;
        else if(l>=me[i].l&&r<=me[i].r)return;
        else if(l<=me[i].l&&r>=me[i].r)
        {
            water(i+1,l,me[i].l-1);
            water(i+1,me[i].r+1,r);
            return;
        }
    }
    if(l>r)return;
    zjg wb;
    wb.l=-l;wb.r=r;wb.color=c;
    heap.push(wb);
}