题目链接：

题目大意：给出一张$n$个点$m$条边的无向图，点和边可重复经过，一个狼人初始为人形，有$q$次询问，每次询问要求人形态只能处于编号不小于$L$的点，狼形态只能处于编号不大于$R$的点，询问能否从$S$处于人形态然后在编号在$[L,R]$内的点变身一次成为狼人然后到达 $E$。

题目中编号都是从0开始，太不舒服了，我们按编号从1开始讲QAQ。

题目大意就是询问每次从一个点开始走只能走编号在[l,n]中的点，在任意点变成狼，之后只能走[0,r]中的点，是否能到达另一个点。

后一部分其实就是找有哪些点只走[0,r]中的点能到达终点，那么反过来看，就是终点只走[0,r]中的点能到达哪些点。

那么只要起点能到达的点和终点能到达的点中有交集就有解。

因为起点只能走一些编号较大的点，那么我们求出原图的最大生成树，建出kruskal重构树，求出重构树的dfs序，每次询问在重构树上倍增找能到达的联通块在dfs序上的区间就好了。

相反，从终点走就求出原图的最小生成树，然后也按上述方法找。

找到两段dfs序区间后只要这两段区间中有相同点就能判有解。

我们将每个点在第一个dfs序中的位置作为横坐标，在第二个dfs序中的位置作为纵坐标，剩下的就是一个简单的二维数点问题了。

等会，上面是不是差点什么？原图没有边权啊？

我们以最大生成树为例，对于一条边(x,y)，两个点能否通过这条边互相到达，由这两个点中较小的点决定，因此求最大生成树时每条边边权就是边两端点中较小的那个。最小生成树边权就是两端点中较大的那个。

整体思路就是分别建出原图最小生成树和最大生成树的重构树，分别求出每个点在两个重构树中的dfs序位置，然后可持久化线段树二维数点。

kruskal重构树在这里就不赘述了，如果不是太了解可以参考我的另一篇博客，那道题和这道题思想很像。

题面似乎没说保证整张图联通，因此可能是kruskal重构森林。

#include"werewolf.h"#include#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #define ll long longusing namespace std;struct miku{ int u,v,x,y;}a[400010];int cnt;int n,m,k;int s,t,l,r;int num1,num2;int sum1,sum2;int s1[400010];int s2[400010];int t1[400010];int t2[400010];int q1[400010];int q2[400010];int v1[400010];int v2[400010];int fa1[400010];int fa2[400010];int ls1[400010];int rs1[400010];int ls2[400010];int rs2[400010];int ls[5000010];int rs[5000010];int vis1[400010];int vis2[400010];int sum[5000010];int root[200010];int f1[400010][18];int f2[400010][18];vector
                
                 res;int find1(int x){ if(fa1[x]==x) { return x; } return fa1[x]=find1(fa1[x]);}int find2(int x){ if(fa2[x]==x) { return x; } return fa2[x]=find2(fa2[x]);}bool cmp1(miku a,miku b){ return a.x>b.x;}bool cmp2(miku a,miku b){ return a.y
                 
                  >1; build(ls[rt],l,mid); build(rs[rt],mid+1,r);}void updata(int &rt,int pre,int l,int r,int k){ rt=++cnt; sum[rt]=sum[pre]+1; if(l==r) { return; } ls[rt]=ls[pre]; rs[rt]=rs[pre]; int mid=(l+r)>>1; if(k<=mid) { updata(ls[rt],ls[pre],l,mid,k); } else { updata(rs[rt],rs[pre],mid+1,r,k); }}int query(int x,int y,int l,int r,int L,int R){ if(L<=l&&r<=R) { return sum[y]-sum[x]; } int mid=(l+r)>>1; int res=0; if(L<=mid) { res+=query(ls[x],ls[y],l,mid,L,R); } if(R>mid) { res+=query(rs[x],rs[y],mid+1,r,L,R); } return res;}void dfs1(int x){ vis1[x]=1; s1[x]=sum1; if(x<=n) { q1[++sum1]=x; } for(int i=1;i<=17;i++) { f1[x][i]=f1[f1[x][i-1]][i-1]; } if(ls1[x]) { dfs1(ls1[x]); } if(rs1[x]) { dfs1(rs1[x]); } t1[x]=sum1;}void dfs2(int x){ vis2[x]=1; s2[x]=sum2; if(x<=n) { q2[++sum2]=x; } for(int i=1;i<=17;i++) { f2[x][i]=f2[f2[x][i-1]][i-1]; } if(ls2[x]) { dfs2(ls2[x]); } if(rs2[x]) { dfs2(rs2[x]); } t2[x]=sum2;}int ST1(int x,int val){ for(int i=17;i>=0;i--) { if(v1[f1[x][i]]>=val&&f1[x][i]!=0) { x=f1[x][i]; } } return x;}int ST2(int x,int val){ for(int i=17;i>=0;i--) { if(v2[f2[x][i]]<=val&&f2[x][i]!=0) { x=f2[x][i]; } } return x;}vector
                  
                    check_validity(int N,vector
                   
                     X,vector
                    
                      Y,vector
                     
                       S,vector
                      
                        E,vector
                       
                         L,vector
                        
                          R){ n=N; m=X.size(); k=S.size(); for(int i=1;i<=m;i++) { a[i].u=X[i-1]; a[i].v=Y[i-1]; a[i].u++; a[i].v++; a[i].x=min(a[i].u,a[i].v); a[i].y=max(a[i].u,a[i].v); } for(int i=1;i<2*n;i++) { fa1[i]=i; fa2[i]=i; } num1=num2=n; sort(a+1,a+1+m,cmp1); for(int i=1;i<=m;i++) { int fx=find1(a[i].u); int fy=find1(a[i].v); if(fx!=fy) { num1++; v1[num1]=a[i].x; ls1[num1]=fx; rs1[num1]=fy; f1[fx][0]=num1; f1[fy][0]=num1; fa1[fx]=num1; fa1[fy]=num1; if(num1==2*n-1) { break; } } } for(int i=1;i<=n;i++) { if(!vis1[i]) { dfs1(find1(i)); } } sort(a+1,a+1+m,cmp2); for(int i=1;i<=m;i++) { int fx=find2(a[i].u); int fy=find2(a[i].v); if(fx!=fy) { num2++; v2[num2]=a[i].y; ls2[num2]=fx; rs2[num2]=fy; f2[fx][0]=num2; f2[fy][0]=num2; fa2[fx]=num2; fa2[fy]=num2; if(num2==2*n-1) { break; } } } for(int i=1;i<=n;i++) { if(!vis2[i]) { dfs2(find2(i)); } } build(root[0],1,n); for(int i=1;i<=n;i++) { updata(root[i],root[i-1],1,n,s2[q1[i]]+1); } for(int i=0;i

转载于:https://www.cnblogs.com/Khada-Jhin/p/9751803.html

你可能感兴趣的文章