LOJ
洛谷

---

這題不就是Peaks(加強版)或者歸程么。。這算是\(IOI2018\)撞上\(NOI2018\)的題了？
\(Kruskal\)重構樹（具體是所有點按從小到大/從大到小的順序，依次加入這些點的邊），我們可以得到兩棵樹（和那兩題不一樣的是這題的權值在點上，不需要新建節(jié)點）。
對于詢問\((S,T,L,R)\)，可以倍增找出\(S,T\)可以在哪棵子樹中隨便走。
那么只需要判斷兩棵子樹是否有交就可以惹。
注意到子樹的DFS序是連續(xù)的，我們可以在第一個子樹的某個數據結構上，查第二個子樹的DFS序區(qū)間。用主席樹就可以了，主席樹的下標是每個點在第二棵樹上的DFS序。判斷第一個子樹在第二個子樹的DFS序區(qū)間中是否有值即可。

寫一寫權當復習惹。
另外，這個題的交互有點逗逼啊...為什么是所有詢問一起輸出啊？

---

LOJ上15分，T掉了，不知道為什么（應該是交互的問題）。不管惹。

//656ms 84.03MB #include <cstdio> #include <cctype> #include <algorithm> #define BIT 17 #define gc() getchar() #define MAXIN 300000 //#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++) typedef long long LL; const int N=2e5+5,M=8e5+5;int n,root[N]; char IN[MAXIN],*SS=IN,*TT=IN; struct Graph {int Enum,H[N],nxt[M],to[M];inline void AE(int u,int v){to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;} }G; struct Tree {int fg,fa[N][BIT+1],F[N],H[N],nxt[N],L[N],R[N],Index;int Find(int x){return x==F[x]?x:F[x]=Find(F[x]);}inline void AE(int u,int v){nxt[v]=H[u], H[u]=v;}inline int Jump(int x,int k){if(fg){for(int i=BIT; ~i; --i)if(fa[x][i]&&fa[x][i]<=k) x=fa[x][i];}else{for(int i=BIT; ~i; --i)if(fa[x][i]>=k) x=fa[x][i];}return x;}void DFS(int x,int dep){L[x]=++Index;for(int i=1; 1<<i<=dep; ++i) fa[x][i]=fa[fa[x][i-1]][i-1];for(int v=H[x]; v; v=nxt[v]) fa[v][0]=x, DFS(v,dep+1);R[x]=Index;}void Build(const int n){for(int i=1; i<=n; ++i) F[i]=i;if(fg){for(int x=1,k=1; x<=n; ++x)for(int i=G.H[x],v; i; i=G.nxt[i])if((v=G.to[i])<x){int r1=Find(x),r2=Find(v);//r1==xif(r1!=r2){F[r2]=r1, AE(r1,r2);if(++k==n) break;}}}else{for(int x=n,k=1; x; --x)for(int i=G.H[x],v; i; i=G.nxt[i])if((v=G.to[i])>x){int r1=Find(x),r2=Find(v);if(r1!=r2){F[r2]=r1, AE(r1,r2);if(++k==n) break;}}}DFS(fg?n:1,0);} }T1,T2; struct Segment_Tree {#define ls son[x][0]#define rs son[x][1]#define lson ls,son[y][0],l,m#define rson rs,son[y][1],m+1,r#define S N*19int tot,sz[S],son[S][2];#undef Svoid Modify(int &x,int y,int l,int r,int p){sz[x=++tot]=sz[y]+1;if(l==r) return;int m=l+r>>1;p<=m?(rs=son[y][1],Modify(lson,p)):(ls=son[y][0],Modify(rson,p));}int Query(int x,int y,int l,int r,int L,int R)//y-x{if(sz[y]-sz[x]<=0) return 0;if(L<=l && r<=R) return 1;int m=l+r>>1;if(L<=m)if(m<R) return Query(lson,L,R)||Query(rson,L,R);else return Query(lson,L,R);return Query(rson,L,R);} }T;inline int read() {int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-48,c=gc());return now; } void DFS(int x) {static int Index=0;++Index, T.Modify(root[Index],root[Index-1],1,n,T2.L[x]);for(int v=T1.H[x]; v; v=T1.nxt[v]) DFS(v); }int main() {int n=read(),m=read(),Q=read(); ::n=n;for(int i=1; i<=m; ++i) G.AE(read()+1,read()+1);T1.Build(n), T2.fg=1, T2.Build(n), DFS(1);for(int s,t; Q--; )s=read()+1,t=read()+1,s=T1.Jump(s,read()+1),t=T2.Jump(t,read()+1),putchar(T.Query(root[T1.L[s]-1],root[T1.R[s]],1,n,T2.L[t],T2.R[t])?'1':'0'), putchar('\n');return 0; }

轉載于:https://www.cnblogs.com/SovietPower/p/10685264.html

總結

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

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