正題

題目鏈接:https://www.luogu.com.cn/problem/P4899

---

題目大意

$n$個點的一張無向圖，每次詢問$(s,t,l,r)$表示詢問能否找到一條$s～t$的路徑使得該路徑可以分割成點的序號在$[l,n]$和$[1,r]$的兩段。

---

解題思路

首先對原圖構造兩棵$Kruskal$生成樹，分別是最小序號最大的和最大序號最小的路徑，然后我們每次詢問是可以分別在樹上跳到一個最高的位置。

然后問題就轉換為詢問兩個樹的子樹交集，考慮使用主席樹，對于第$dfn{1}_x$棵主席樹上的第$dfn{2}_x$個位置加權值($dfn{1}_x$和$dfn{2}_x$分別表示$x$在第$1/2$棵樹上的$dfs$序)。然后主席樹詢問即可。

時間復雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=6e5,T=20; struct edge{int x,y,w; }e[N]; struct node{int to,next; }; struct Kul{node a[N<<1];int tot,cnt,num,fa[N],ls[N],w[N],dfn[N],rfn[N],ed[N],f[N][T+1];void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;//printf("%d %d\n",x,y);return;}int find(int x){return (fa[x]==x)?x:(fa[x]=find(fa[x]));}void addp(int x,int y,int val){if(find(x)==find(y))return;w[++num]=val; addl(num,find(x));addl(num,find(y));fa[find(y)]=num;fa[find(x)]=num;return;}void dfs(int x){dfn[++cnt]=x;rfn[x]=cnt;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;f[y][0]=x;dfs(y);}ed[x]=cnt;}void init(){for(int i=num;i>=1;i--)if(!f[i][0])dfs(i);w[0]=num+1;for(int j=1;j<=T;j++)for(int i=1;i<=num;i++)f[i][j]=f[f[i][j-1]][j-1];return;}int jump(int x,int val){for(int i=T;i>=0;i--)if(w[f[x][i]]<=val)x=f[x][i];return x;} }k1,k2; int n,m,q,cnt,rt[N],x[N],y[N],w[N<<5],ls[N<<5],rs[N<<5]; int Insert(int y,int l,int r,int pos){int x=++cnt;w[x]=w[y]+1;if(l==r)return x;int mid=(l+r)>>1;if(pos<=mid)ls[x]=Insert(ls[y],l,mid,pos),rs[x]=rs[y];else rs[x]=Insert(rs[y],mid+1,r,pos),ls[x]=ls[y];return x; } int Ask(int x,int y,int L,int R,int l,int r){if(!(w[y]-w[x]))return 0;if(l==L&&R==r)return w[y]-w[x];int mid=(L+R)>>1;if(r<=mid)return Ask(ls[x],ls[y],L,mid,l,r);if(l>mid)return Ask(rs[x],rs[y],mid+1,R,l,r);return Ask(ls[x],ls[y],L,mid,l,mid)+Ask(rs[x],rs[y],mid+1,R,mid+1,r); } bool cmp(edge x,edge y) {return x.w<y.w;} int main() {scanf("%d%d%d",&n,&m,&q);k1.num=k2.num=n;for(int i=1;i<=n+m;i++)k1.fa[i]=k2.fa[i]=i;for(int i=1;i<=m;i++)scanf("%d%d",&e[i].x,&e[i].y),e[i].x++,e[i].y++,e[i].w=max(e[i].x,e[i].y);sort(e+1,e+1+m,cmp);for(int i=1;i<=m;i++)k1.addp(e[i].x,e[i].y,e[i].w),e[i].w=min(e[i].x,e[i].y);sort(e+1,e+1+m,cmp);for(int i=m;i>=1;i--)k2.addp(e[i].x,e[i].y,n-e[i].w+1);k1.init();k2.init();for(int i=1;i<=k1.num;i++)if(k1.dfn[i]<=n)rt[i]=Insert(rt[i-1],1,k2.num,k2.rfn[k1.dfn[i]]);else rt[i]=rt[i-1];while(q--){int l,r,s,t;scanf("%d%d%d%d",&s,&t,&l,&r);s++;t++;l++;r++;r=k1.jump(t,r);l=k2.jump(s,n-l+1);//printf("%d %d\n",l,r);if(Ask(rt[k1.rfn[r]-1],rt[k1.ed[r]],1,k2.num,k2.rfn[l],k2.ed[l])) printf("1\n");else printf("0\n");}return 0; }

總結

以上是生活随笔為你收集整理的P4899-[IOI2018]werewolf 狼人【Kruskal重构树,主席树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。