题目描述：
现在有 \(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;
}
完结撒花！！