【思路】

每次我们染了一个区间，下一次如果还要染这个区间或者它的子区间的话，我们就不用处理了。这样我们可以把每一个区间抽象成一个点，用并查集来维护。合并时将[L,R]区间全部合并，[L,R]区间的每个点的父节点都通过路径合并变成L-1,然后n–。这样每个点只会被合并一次，复杂度O(nα(n)) ，跑得很快。

如 3 3

• fa[3]=2,操作一次

    5 7,

• fa[7]=fa[6]=fa[5]=4，操作三次

    2 8：

• fa[8]=fa[7]，操作一次；
• 由于5,6,7已经被合并到了4这个点，所以下一次直接跳到4；
• fa[4]=3,操作一次；
• fa[3]=2,直接调到2；
• fa[2]=1,操作一次。

【Accepted】

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 using namespace std;10 const int maxn=2e5+3;11 int fa[maxn];12 int n,m;13 int find(int x)14 {15 return fa[x]==x?x:fa[x]=find(fa[x]); 16 }17 void init()18 {19 for(int i=0;i<=n;i++)20 {21 fa[i]=i;22 }23 }24 int main()25 {26 while(~scanf("%d%d",&n,&m))27 {28 init();29 for(int i=0;i