真的好久好久没写题解啦……真是不好意思！

　　emmm……立刻岔开话题……

　　这道题真的是一道很好很好的倍增优化并查集的题！

　　首先对于暴力，就是每一个点都暴力并查集，每一次判断这个点的祖先是不是自己就可以了，30分。

　　我么当然不能止步于30分啊，所以自然要想想优化啦！

　　我一开始是想单独考虑每一个子问题，考虑这段区间是否包含原来修改的部分，但是发现需要维护的东西太多了……不能简单明了的解决问题。

　　再回头看看题面，我们由于不能每一次都一个个地维护每一个点的并查集，就想到了倍增优化。

　　对于状态 fa [ i ] [ j ] 意思是从 i 开始 2^j - 1 的长度，i 的父亲是谁（和 i 相同的区间左端点）。 那么我们只要将这段区间拆成若干个（logn）个子区间，再一一对应维护并查集即可。

　　由于我们最后是要小的状态 fa [ i ] [ 0 ]，所以对于一个区间的父亲，我们再分别将父亲的状态分开再转给儿子，就保证了最后能维护到最短的这个区间（长度为1，fa [ x ] [ 0 ] ）。

　　最后统计独立点个数就行。

　　代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define maxn 100005#define int long longconst int mod = 1e9+7;int fa[maxn][25];int n,m;int find(int x,int i){ return x == fa[x][i] ? x : fa[x][i] = find(fa[x][i],i);}void merge(int x,int y,int i){ x=find(x,i); y=find(y,i); if(x!=y) fa[x][i]=y;}main(){ int ans=9; scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++) for(int j=0;j<=20;j++) fa[i][j]=i; for(int i=1;i<=m;i++) { int l1,r1,l2,r2; scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2); for(int j=20;j>=0;j--) { if(l1+(1<
            
             <=r1) { merge(l1,l2,j); l1+=(1<