题解 P2391 【白雪皑皑】

· · 题解

ps:这篇题解一定请过QAQ！！！原因很简单，洛谷数据过水，90%A了的题解其实都是有问题的！！！（本人在本地测了很多组合法数据，几乎所有题解都要1s以上，而本篇题解0.5s左右）

方法：双向链表+缩点

首先很多dalao都说过了，要从后往前染色，遇见染过色的就不管它。但是，这样其实会浪费很多时间，是要T的。

所以我们考虑，在染色的同时，把染过色的区间缩为一个点，这样就能大大节省时间。因为是线性，所以我们采取链表。

之前已经有dalao发过链表的题解了，但是他只将染过色的区间的左右端点连在一起，而中间的点还是没有变化，这样就会造成很多不必要的运算。本题解在此基础上改进，将中间点也直接与左右端点相连，效率为假O（n）（就是很逼近O（n））；

代码如下：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define R register
using namespace std;
int n,m,color[1000010],pre[1000010],nxt[1000010],p,q;
template <typename T> void in(R T &a)
{
    R char c = getchar();R T x=0,f=1;
    while(!isdigit(c)) {if(c == '-') f=-1; c=getchar();}
    while(isdigit(c)) x=(x<<1)+(x<<3)+c-'0',c = getchar();
    a=x*f;
}
int main()
{
    //freopen("color.in","r",stdin);
    //freopen("color.out","w",stdout);
    in(n),in(m),in(p),in(q);
    for(R int i=1;i<=n;i++)
    {
        nxt[i]=i+1;//链表初始化
        pre[i]=i-1;
    }
    for(R int i=m;i>=1;i--)//从后往前
    {
        R int l=(i*p+q)%n+1,r=(i*q+p)%n+1;//计算左右端点
        if(l>r) l^=r,r^=l,l^=r;
        R int now=l;
        while(now<=r)//敲黑板！！！
        {
            R int temp=0;//如果没染过色，就染色、将该点与区间左右端点相连，记录原本的下一个位置为temp
            if(!color[now]) color[now]=i,pre[now]=pre[l],temp=nxt[now],nxt[now]=nxt[r];
            temp==0?now=nxt[now]:now=temp;//temp不为零，则跳到原本的下一个点；为零，则说明该点已经染过色（就是已经缩过点，直接跳到缩点后的下一个端点）
        }
    }
    for(R int i=1;i<=n;i++) printf("%d\n",color[i]);
    return 0;
}
/*
4 3 2 4
*/