洛谷P2391 白雪皑皑 题解

题目链接：P2391 白雪皑皑

题意：

现在有 $n$ 片雪花排成一列。 pty 要对雪花进行 $m$ 次染色操作，第 $i$ 次染色操作中，把第 $((i\times p+q)\bmod n)+1$ 片雪花和第 $((i\times q+p)\bmod n)+1$ 片雪花之间的雪花（包括端点）染成颜色 $i$。其中 $p,q$ 是给定的两个正整数。他想知道最后 $n$ 片雪花被染成了什么颜色。没有被染色输出 $0$。

$1\leq n\leq 10^6,~1\leq m\leq 10^7$。

保证 $1\leq m\times p+q,m\times q+p\leq 2\times 10^9$。

一句话题意：线性区间推平（区间赋同一个值），全局询问。

我们模拟赛t3，也是我想了几个月结果有原题的东西，不写题解亏大了

考虑倒序处理修改，因为一个位置的值一定由它最后一次被修改的数决定

暴力推平？对于被推平的点，不可以再推了，所以我们要跳过它

这就需要维护每个点右侧的那个未被推平的结点

可以考虑链表或者并查集维护，这里用并查集

时间复杂度 $O(n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e6+25)

int n,m,p,q,val[N],f[N];
void init(int n){for(int i=1; i<=n; i++) f[i]=i;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
signed main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    
    read(n);init(n+5);
    read(m);read(p);read(q);
    for(int i=m; i>=1; i--)
    {
        int l=(1ll*i*p+q)%n+1;
        int r=(1ll*i*q+p)%n+1;
        if(l>r)swap(l,r);
        for(int j=l; j<=r;)
        {
            int k=find(j); if(k>r)break;
            val[k]=i; f[k]=find(k+1); j=f[k];
        }
    }
    for(int i=1; i<=n; i++) write(val[i]),pc('\n');
    return 0;
}

是不是很神奇，我之前还想过差分、单调栈、线段覆盖、二维凸包(?等一大堆东西