题解 P2391 【白雪皑皑】

· · 题解

Youngsc

楼下说他一来是用的是链表，可能是因为写的不太对就改成并查集了，其实双向链表对于这道题是可做的。

从最后一个操作往前扫这个不用多说，当我们对一个区间进行染色之后，我们就将其从链表中删除，然后进行下一次染色，如果说此时的左端点已经被删除，会不会影响我的染色，答案是不会的，因为链表中所谓的删除无非是将两个端点两边的节点相互连接起来，也就是说我虽然不能从保留下来的节点找到已经删除节点，因为他的指针已经改变，但我依然可以从已经删除的节点找到保留的节点，因为此时的指针并没有发生改变，我只需要判断有没有染过颜色就行了。右端点已经染色同理。

代码如下

# include <algorithm>
# include <iostream>
# include <cstring>
# include <cstdio>
# include <queue>
# include <cmath>
# define R register
# define LL long long

using namespace std;

int n,m,col[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;
}

inline int youngsc(){
    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)
        {
            if(!col[now]) col[now] = i;
            now = nxt[now];
        }
        nxt[pre[l]] = nxt[r];
        pre[nxt[r]] = pre[l];
    }
    for(R int i=1; i<=n; ++i) printf("%d\n",col[i]);
    return 0;
}
int yg = youngsc();
int main(){;}