Luogu p2391 snow covered problem solution

Luogu P2391 snow gleams white Answer key

Topic link ：P2391 snow gleams white

The question ：

Now there is $n$ Snowflakes in a row . pty The snowflakes should be $m$ Secondary staining operation , The first $i$ Secondary dyeing operation , The first $((i\times p+q)\mathrm{mod}n)+1$ A snowflake and $((i\times q+p)\mathrm{mod}n)+1$ Snowflakes between snowflakes （ Include endpoints ） Dye into color $i$. among $p,q$ Are given two positive integers . He wants to know in the end $n$ What color is a snowflake dyed . Not dyed output $0$.

$1\le n\le 10^6,1\le m\le 10^7$.

Guarantee $1\le m\times p+q,m\times q+p\le 2\times 10^9$.

One sentence question ： Linear interval smoothing （ The interval is assigned the same value ）, Global query .

We have a mock race t3, It's also something I've been thinking about for months, and the result is the original question , If you don't write a question, you'll lose a lot

Consider modifying in reverse order , Because the value of a position must be determined by the number it was last modified

Violent leveling ？ For the flattened point , No more pushing , So we have to skip it

This requires maintaining the node on the right side of each point that has not been pushed flat

You can consider linked list or parallel query set maintenance , Use and search set here

Time complexity $O(n)$

Code ：

#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;
}

Isn't that amazing , I thought about difference before 、 Monotonic stack 、 Line segments cover 、 Two dimensional convex hull (? Wait for a lot of things