这个题真的很神奇。

数据10000000，所以肯定是线性做法，然后我就不会了，一看题解，并查集，看完了之后，发现真的很巧妙，就是像一个链表一样用并查集。

copy一段：

这道题可以用并查集来打（然而我一开始脑抽竟然用了双向链表-.-），从最后开始往前进行涂色，因为显然后面的优先级大于前面，后面的会将前面涂的颜色覆盖。这样我们只要快速查找下一个没被涂的点就行了，因此我想到了并查集，只要保证每个集合的fa没被涂过就行了。这样就避免了复杂度过高。

我的代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define ll long longusing namespace std;int n,m,p,q;int a[1000101];int fa[1000101];int find(int x){ return (fa[x]<0)?x:fa[x]=find(fa[x]);}int main(){ scanf("%d %d %d %d",&n,&m,&p,&q); memset(fa,-1,sizeof(fa)); for(int i=m;i>=1;i--){ int l=(i*p+q)%n+1; int r=(i*q+p)%n+1; if(r