BZOJ2054:疯狂的馒头&BZOJ2375:疯狂的涂色

题目大意:

一个长度为\(n\)的序列,进行\(m\)次操作,第\(i\)次将区间\([l_i,r_i]\)染成颜色\(i\).求最终每个位置被染成什么颜色.

思路:

倒着处理,那么我们只需将当前区间内没染色的染成当前的颜色即可.

那么我们事实上是要维护那些位置还没有染色.由于每次染色都是一段连续区间,我们用并查集不断合并即可.能够保证总的时间复杂度为\(O(n)\).

因此总的复杂度为\(O(m+n)\).

注意当所有位置全部染色后及时退出.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
 
#define N 1000010
int r[N],v[N];
int find(int x){int q=x,rq;for(;x!=r[x];x=r[x]);for(;q!=x;q=rq)rq=r[q],r[q]=x;return x;}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    int n,m,q,p;cin>>n>>m>>q>>p;
    register int i,j;for(i=1;i<=n+1;++i)r[i]=i;
    int L,R;
    for(i=m;i>=1;--i){
        L=((LL)i*p+q)%n+1,R=((LL)i*q+p)%n+1;if(L>R)swap(L,R);
        //printf("%d %d\n",L,R);
        for(j=find(L);j<=R;j=r[j]){
            if(!v[j])v[j]=i;
            r[j]=find(j+1);
        }
        if(find(1)==n+1)break;
    }
    for(i=1;i<=n;++i)printf("%d\n",v[i]);
    return 0;
}