非常非常非常NOIp的模拟赛（吐槽完毕）
小X现在正准备刷墙，墙的长度为n。
但是刷墙不是一蹴而就的，所以他会刷m次墙，每次刷的是墙的连续的一段，有时候也会覆盖之前刷的部分。
终于，墙刷完了，先在小X想问你从 1~n 块墙分别是什么时候刷的
输入文件名为paint.in
第一行两个数n，m表示墙的长度和刷墙次数
第二行两个数p,q表示种子
第i次询问的两个端点分别是 (i*p+q)%n+1 , (i*q+p)%n+1
输出文件名为paint.out
共n行，每行一个整数表示第i块墙最后被刷的时间，如果没被刷到输出0
4 3
2 4
2
3
3
0
对于30%的数据, 1<=n,m<=3000
对于50%的数据, 1<=n<=8000,m<=104
对于80%的数据,1<=n<=5*105,m<=106
对于100%的数据,1<=n<=106,1<=m<=107
数据保证运算过程中不会爆int
sol：首先经过漫长的思考，发现正着做怎么也弄不了
于是就考虑倒过来做：此时惊喜的发现每个点只要染色一次就OK了，这就用并查集随便处理一下，如果x被染色了，Father[x]就是x+1，下次直接跳过就可以了
#include <bits/stdc++.h> using namespace std; typedef int ll; inline ll read() { ll s=0; bool f=0; char ch=‘ ‘; while(!isdigit(ch)) { f|=(ch==‘-‘); ch=getchar(); } while(isdigit(ch)) { s=(s<<3)+(s<<1)+(ch^48); ch=getchar(); } return (f)?(-s):(s); } #define R(x) x=read() inline void write(ll x) { if(x<0) { putchar(‘-‘); x=-x; } if(x<10) { putchar(x+‘0‘); return; } write(x/10); putchar((x%10)+‘0‘); return; } #define W(x) write(x),putchar(‘ ‘) #define Wl(x) write(x),putchar(‘\n‘) const int N=10000005; int n,m,seed1,seed2; int Cor[N]; int Father[N]; inline int Get_Father(int x) { int Fa=Father[x]; while(Fa!=Father[Fa]) Fa=Father[Fa]; while(x!=Father[x]) { int oo=x; x=Father[x]; Father[oo]=Fa; } return Fa; } int main() { freopen("paint.in","r",stdin); freopen("paint.out","w",stdout); int i,j; R(n); R(m); R(seed1); R(seed2); for(i=1;i<=n+1;i++) Father[i]=i; for(i=m;i>=1;i--) { int l=((long long)(seed1*i+seed2))%n+1,r=((long long)(seed2*i+seed1))%n+1; if(l>r) swap(l,r); for(j=l;j<=r;) { int Fa=Get_Father(j); if(Fa==j) { Cor[j]=i; Father[j]=j+1; } j=Fa; } } for(i=1;i<=n;i++) { Wl(Cor[i]); } return 0; } /* input 4 3 2 4 output 2 3 3 0 */
原文：https://www.cnblogs.com/gaojunonly1/p/10402762.html
