Hellc

【题目描述】

给定一个序列，每次把其中一段区间染成某种颜色，求序列最后的样子。

【题目链接】

BZOJ 2054 疯狂的馒头

【解题思路】

我们考虑倒着进行染色，每次染色时只染 还没有颜色 的位置，即 跳过 之前染过色的位置。

怎样实现跳过的操作呢，我们可以把连在一起的染过色的位置看成一个联通块，用类似并查集的方法维护每个连通块的 右端点 （的下一个位置），这样每次跳过一整个联通块即可。

【AC代码】

#include <cstdio>
#include <algorithm>
 
const int MAXN = 1000000;
 
int color[MAXN];
int f[MAXN];
 
int n, m, p, q;
 
inline void init(){
    for(int i = 0; i <= n; i++){
        color[i] = 0;
        f[i] = i;
    }
}
 
int find(int x){
    return x == f[x] ? x : f[x] = find(f[x]);
}
 
inline void paint(int l, int r, int x){
    for(int i = find(l); i <= r; i = find(i)){
        color[i] = x;
        f[i] = i + 1;
    }
}
 
int main(){
    scanf("%d%d%d%d", &n, &m, &p, &q);
 
    init();
 
    for(int i = m; i; i--){
        int l = (i * p + q) % n + 1;
        int r = (i * q + p) % n + 1;
        if(l > r) std::swap(l, r);
 
        l--, r--;
        paint(l, r, i);
    }
 
    for(int i = 0; i < n; i++){
        printf("%d\n", color[i]);
    }
 
    return 0;
}

就是这样啦