链接: https://www.lydsy.com/JudgeOnline/problem.php?id=2054
线段树写法:
点的颜色只取决于最后一次染的颜色, 所以我们可以倒着维护, 如果当前区间之前被染过了, 就不用再染了, 对区间染色我们可以暴力在线段树上进行更新, 并用线段树维护下那些区间已经被染色了, 被染色的区间更新的时候直接跳过, 这样可以节省很多时间.
实现代码:
- #include<bits/stdc++.h>
- using namespace std;
- #define lson l,m,rt<<1
- #define rson m+1,r,rt<<1|1
- #define mid int m = (l + r)>> 1
- const int M = 1e6 + 10;
- int sum[M<<2];
- void pushup(int rt){
- sum[rt] = sum[rt<<1]&&sum[rt<<1|1];
- }
- void update(int L,int R,int c,int l,int r,int rt){
- if(sum[rt]) return ;
- if(l == r){
- sum[rt] = c;
- return ;
- }
- mid;
- if(L <= m) update(L,R,c,lson);
- if(R> m) update(L,R,c,rson);
- pushup(rt);
- }
- void ct(int l,int r,int rt){
- if(l == r){
- printf("%d\n",sum[rt]);
- return ;
- }
- mid;
- ct(lson); ct(rson);
- }
- int main()
- {
- int n,m,p,q;
- scanf("%d%d%d%d",&n,&m,&p,&q);
- for(int i = m;i>= 1;i --){
- int x = ((i*p+q)%n)+1;
- int y = ((i*q+p)%n)+1;
- if(x> y) swap(x,y);
- update(x,y,i,1,n,1);
- }
- ct(1,n,1);
- }
并查集写法:
和线段树的思路一样, 我们需要快速跳过已染色区间, 这里用并查集维护已染色的区间, 区间更新时可以利用并查集快跳过被染色的区间.
实现代码:
- #include<bits/stdc++.h>
- using namespace std;
- const int M = 1e6+10;
- int ans[M],f[M];
- int Find(int x){
- if(x == f[x]) return x;
- return f[x] = Find(f[x]);
- }
- int main()
- {
- int n,m,p,q;
- scanf("%d%d%d%d",&n,&m,&p,&q);
- for(int i = 0;i <= n+1;i ++) f[i] = i;
- for(int i = m;i>= 1;i --){
- int x = ((i*p+q)%n)+1,y = ((i*q+p)%n)+1;
- if(x> y) swap(x,y);
- for(int j = Find(x);j <= y;j = Find(j+1)){
- f[j] = Find(j+1); ans[j] = i;
- }
- }
- for(int i = 1;i <= n;i ++)
- printf("%d\n",ans[i]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2996329.html