P2391 白雪皑皑题目背景“柴门闻犬吠风雪夜归人”冬天不期而至。千里冰封万里雪飘。空中刮起了鸭毛大雪。雪花纷纷降落人间。 美能量星球pty 在 spore 上的一个殖民地上的人们被这美景所震撼。但是 pty 却不高兴他不喜欢白色的世界他觉得这样太单调了。所以他想对雪花进行染色让世界变得多彩些。题目描述现在有nnn片雪花排成一列。 pty 要对雪花进行mmm次染色操作第iii次染色操作中把第((i×pq) mod n)1((i\times pq)\bmod n)1((i×pq)modn)1片雪花和第((i×qp) mod n)1((i\times qp)\bmod n)1((i×qp)modn)1片雪花之间的雪花包括端点染成颜色iii。其中p,qp,qp,q是给定的两个正整数。他想知道最后nnn片雪花被染成了什么颜色。没有被染色输出000。输入格式输入共四行每行一个整数分别为n,m,p,qn,m,p,qn,m,p,q意义如题中所述。输出格式输出共nnn行每行一个整数第iii行表示第iii片雪花的颜色。输入输出样例 #1输入 #14 3 2 4输出 #12 2 3 0说明/提示对于20%20\%20%的数据满足n,m≤1000n,m\leq 1000n,m≤1000。对于40%40\%40%的数据满足n≤8000n\leq 8000n≤8000m≤106m\leq 10^6m≤106。对于80%80\%80%的数据满足n≤5×105n\leq 5\times 10^5n≤5×105m≤107m\leq 10^7m≤107。对于100%100\%100%的数据满足1≤n≤1061\leq n\leq 10^61≤n≤1061≤m≤1071\leq m\leq 10^71≤m≤107。保证1≤m×pq,m×qp≤2×1091\leq m\times pq,m\times qp\leq 2\times 10^91≤m×pq,m×qp≤2×109。代码#includebits/stdc.husingnamespacestd;constintMAXN1e65;// 常量名更语义化structSnowflake{intcolor;// 雪花最终染色编号0表示未染色intnext;// 以当前位置为起点首个未染色的位置路径压缩用}snow[MAXN];// 并查集查找找到x位置开始的首个未染色位置路径压缩优化intfind(intx){if(snow[x].next!x){snow[x].nextfind(snow[x].next);// 路径压缩直接指向最终未染色位置}returnsnow[x].next;}intmain(){ios::sync_with_stdio(false);// 加速cin/cout应对1e6量级数据cin.tie(nullptr);intn,m,p,q;// n:雪花总数 m:染色操作数 p/q:随机数参数cinnmpq;// 初始化所有雪花未染色每个位置的首个未染色位置是自身n1作为边界哨兵for(inti1;in1;i){snow[i].color0;snow[i].nexti;}// 逆序处理染色操作后执行的操作覆盖先执行的保证每个位置只染最后一次for(intopm;op1;--op){// 计算当前操作的染色区间 [l, r]保证1lrnintpos1((1LL*op*pq)%n)1;// 1LL防止乘法溢出intpos2((1LL*op*qp)%n)1;intlmin(pos1,pos2);intrmax(pos1,pos2);// 遍历区间内所有未染色位置通过find直接跳转到未染色位置避免重复遍历for(intjfind(l);jr;jfind(j)){snow[j].colorop;// 标记为当前操作的颜色逆序保证是最后一次染色snow[j].nextj1;// 染完后该位置的首个未染色位置指向右侧}}// 输出每个雪花的最终颜色for(inti1;in;i){coutsnow[i].color\n;// \n比endl快避免刷新缓冲区}return0;}总结并查集「非连通性问题」的经典应用非常规的合并 / 查找而是路径压缩的灵活复用解决了大量区间覆盖 / 跳过已处理元素的问题。用并查集的「路径压缩」特性跳过已处理区间将区间染色的时间复杂度从暴力O(mn) 优化到O(nα(n))(α(n) 是阿克曼反函数近乎常数逆序处理覆盖类操作保证每个位置只处理最后一次有效操作避免重复计算初始化到n1 作为「哨兵位置」避免处理最后一个位置时的越界判断简化逻辑。