p3295 [SCOI2016]萌萌哒-白红宇

p3295 [SCOI2016]萌萌哒

阅读量：6306 次

发布时间：2019-06-22

本文共 1229 字，大约阅读时间需要 4 分钟。

分析

我们可以将一个点拆成logN个点，分别代表从点i开始，长度为2^k的子串那么当我们处理两个区间相等的关系时，对区间做二进制拆分，拆成log个区间，分别并起来即可

当然我们这样做修改是省心了，但是同时查询的时候也会带来一些麻烦……因为，我们要求的信息是最底层的，只能是长度为1的区间，而不能有奇奇怪怪的区间不过没关系，我们这时运用等式1，拆分并查集

具体来讲，我们从最长的区间开始逐个枚举，每次查找他和他的父亲，然后把它和父亲都劈成两半，前一半和前一半连边，后一半和后一半连边即可，这样相当于把较长区间并查集拆成两个一半的并查集

最后我们就有了一些关于那些点相等的信息，直接计算并查集个数即可

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;const int mod = 1e9+7;const int LOG = 20;int fa[LOG+2][100010],n,m,l1,l2,r1,r2,cnt;long long Ans=9;inline int sf(int x,int y){ return fa[y][x]==x?x:fa[y][x]=sf(fa[y][x],y);}inline void mer(int x,int y,int k){ if(sf(x,k)!=sf(y,k))fa[k][sf(x,k)]=sf(y,k);}int main(){ int i,j,k; scanf("%d%d",&n,&m); for(i=0;i<=LOG;i++) for(j=1;j<=n;j++)fa[i][j]=j; for(i=1;i<=m;i++){ scanf("%d%d%d%d",&l1,&r1,&l2,&r2); for(j=LOG;j>=0;j--) if(l1+(1<
                   
                    <=r1){ mer(l1,l2,j); l1+=(1<
                    
                     0;i--) for(j=1;j+(1<
                     
                      <=n;j++){ mer(j,sf(j,i),i-1); mer(j+(1<<(i-1)),fa[i][j]+(1<<(i-1)),i-1); } for(i=1;i<=n;i++) if(sf(i,0)==i)cnt++; for(i=1;i

转载于:https://www.cnblogs.com/yzxverygood/p/10354458.html

你可能感兴趣的文章