P2391 白雪皑皑
XichenOC
·
·
题解
P2391 白雪皑皑
题目翻译：
给定n,m,p,q，先进行m次染色操作，将
# 题目分析：
我们分析区间$l$和$r$可以发现，$(i\times p+q)$ $mod$ $n+1$与 $(i$ $mod$ $n$ $ \times p+q)$ $mod$ $n+1$ $ $ $mod$ $n$是等价的，也就是说只有最后$n$次的染色有意义，而$n \le 10^6$,因此我们只需要维护一线段树，区间修改，单点查询即可。
# 完整代码：
```cpp
#include<bits/stdc++.h>
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int N=1e6+5;
int tr[4*N];
void push_down(int p){
if(tr[p]){
tr[lc]=tr[rc]=tr[p];
tr[p]=0;
}
}
void update(int p,int l,int r,int ll,int rr,int x){
if(ll<=l && r<=rr){
tr[p]=x;
return;
}
push_down(p);
int mid=(l+r)>>1;
if(ll<=mid)update(lc,l,mid,ll,rr,x);
if(mid<rr)update(rc,mid+1,r,ll,rr,x);
}
int query(int p,int l,int r,int x){
if(l==r){
return tr[p];
}
push_down(p);
int mid=(l+r)>>1;
if(x<=mid)query(lc,l,mid,x);
else query(rc,mid+1,r,x);
}
int main(){
int n,m,p,q;
cin>>n>>m>>p>>q;
int k=m>n?m-n+1:1;
for(int i=k;i<=m;i++){
int l=(i*p+q)%n+1,r=(i*q+p)%n+1;
if(l>r)swap(l,r);
update(1,1,n,l,r,i);
}
for(int i=1;i<=n;i++){
cout<<query(1,1,n,i)<<endl;
}
}
```
### [线段树讲解](https://www.luogu.com.cn/article/ojh62kc0)