P2391 白雪皑皑

思路:经典的一个并查集维护区间连通性问题,倒序处理时,我们发现每个点有且只能被染色一次.如果染色过了,我们应当跳过这个点前往下个点,以便保证每个点只被访问一次. 我们用 f [ i ] f[i] f[i]代表 i i i点后边第一个被染色的点, i 被染色后 , 令 f [ i ] = i + 1 i被染色后,令f[i]=i+1 i被染色后,令f[i]=i+1用并查集维护这个 f 数组 f数组 f数组就可以了.

#include
using namespace std;
const int maxn = 1e6+15;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector G[maxn];
//前向星
// for(int i=head[u];i!=-1;i=nxt[i]) v = to[i]
//int nxt[maxn],head[maxn],to[maxn];// head[u],cnt 初始值是-1
//int tot = -1;
//void add(int u,int v){
//	nxt[++tot] = head[u];
//	head[u] = tot;
//	to[tot] = v;
//}
int f[maxn];
int find(int k){
	return f[k]==k?k:f[k]=find(f[k]);
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m,p,q;
	cin>>n>>m>>p>>q;
	for(int i=1;i=1;i--){
		int l = (i*p+q)%n+1;int r = (i*q+p)%n+1;
		if(r