題目描述：
現在有 \(N\) 片雪花排成一列。 Pty 要對雪花進行$ M $次染色操作，第 \(i\)次染色操作中，把\((i*p+q）%N+1\) 片雪花和第\(（i*q+p）%N+1\)片雪花之間的雪花（包括端點）染成顔色 \(i\)。其中 \(p\),\(q\) 是給定的兩個正整數。他想知道最後 \(N\) 片雪花被染成了什麼顔色。
輸入格式
包含 4 行：
\(N M p q\) 意義如題中所述。
輸出格式
包含 \(N\) 行:
第 \(i\) 行表示第 \(i\) 片雪花被染成的顔色 c
100%的資料滿足：1<=n<=1000000,1<=m<=10000000
保證 \(1<=M*p+q\)，\(M*q+p<=2*10^9\)
思路分析
第一眼看到這道題，這不就是線段樹裸題嗎？
再看一眼資料範圍，發現過不去，我們可以看到所給的修改區間是特殊的
，然後就開始快樂的打表找規律，經過打表，我們發現，針對區間的修改
是多個最大長度為\(n\)的循環節，(~我也不會證~)然後區間修改就從1e7降
為了1e6，剩下的就是線段樹模闆了。
看了一下題解，大部分都是連結清單，并查集(~可我沒想出來~)
就用線段樹水了一發
本題的資料還是很水的(之前錯誤的暴力都能過，現在過不了了)
注意餘數處理喲!
代碼
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int maxn=1e6+100;
inline int read(){
int ret=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-f;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
ret=ret*10+(ch^'0');
ch=getchar();
}
return ret*f;
}
int n,m,p,q;
struct node{
int clo;
int laz;
int l,r;
node(){
clo=0;
laz=0;
l,r=0;
}
}tre[maxn*4];
void build(int rt,int l,int r){
tre[rt].l=l;
tre[rt].r=r;
if(l==r){
return ;
}
int mid=(l+r)>>1;
build(rt*2,l,mid);
build(rt*2+1,mid+1,r);
}
void pushdown(int rt){
if(tre[rt].laz){
tre[rt*2].clo=tre[rt].laz;
tre[rt*2+1].clo=tre[rt].laz;
tre[rt*2].laz=tre[rt].laz;
tre[rt*2+1].laz=tre[rt].laz;
tre[rt].laz=0;
}
return ;
}
void update(int rt,int l,int r,int ql,int qr,int k){
if(r<ql||l>qr){
return;
}
if(ql<=l&&qr>=r){
tre[rt].clo=k;
tre[rt].laz=k;
return;
}
int mid=(l+r)>>1;
pushdown(rt);
if(ql<=mid){
update(rt*2,l,mid,ql,qr,k);
}
if(qr>mid){
update(rt*2+1,mid+1,r,ql,qr,k);
}
return ;
}
void out(int rt,int l,int r){
if(l==r){
cout<<tre[rt].clo<<endl;
return;
}
int mid=(l+r)>>1;
pushdown(rt);
out(rt*2,l,mid);
out(rt*2+1,mid+1,r);
}
int main(){
// freopen("a.in","r",stdin);
n=read();
m=read();
p=read();
q=read();
int ll,rr;
int lr=1;
if(m>n){
lr=m-(m%n+n);
}
for(int i=lr;i<=m;i++){
ll=min((i*p+q)%n+1,(i*q+p)%n+1);
rr=max((i*p+q)%n+1,(i*q+p)%n+1);
update(1,1,n,ll,rr,i);
}
out(1,1,n);
return 0;
}
完結撒花！！