差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:重构树 [2020/10/08 15:01]
jxm2001 [例题一]
+++ 2020-2021:teams:legal_string:jxm2001:重构树 [2020/10/08 15:16] (当前版本)
jxm2001
@@ 行 146: / 行 146: @@
 </hidden>
+==== 例题二 ====
+[[https://www.luogu.com.cn/problem/P4899|洛谷p4899]]
+=== 题意 ===
+给定 $n$ 个点和 $m$ 条边，每个点的点权等于该点的编号，保证图连通。接下来 $q$ 个询问。
+每次询问从 $S$ 点出发只经过点权不小于 $l$ 的点能到达的点集与从 $E$ 点出发只经过点权不大于 $r$ 的点能到达的点集是否有交集。
+=== 题解 ===
+考虑建两棵重构树。对第一棵重构树，按点权从大到小枚举各个点。
+对每个点，枚举它的所有连边，如果该连边的另一端点所在树的根节点大于该点，则将树的根节点连向该结点，同时将该结点作为新树的根节点。
+最后可以得到一棵树，满足从叶子结点到根节点的结点点权递减，且图中任意两结点必须经过该两结点在树上的 $\text{LCA}$ 才能互达。
+于是从 $S$ 点出发只经过点权不小于 $l$ 的点能到达的点集等价于 $S$ 点的点权不小于 $l$ 的最小祖先的子树。
+同理可以建立第二棵重构树，最多问题等价于询问是否存在点满足该点在第一棵树的 $\text{dfs}$ 序 $\in [l_1,r_1]$，在第二棵树的 $\text{dfs}$ 序 $\in [l_2,r_2]$。
+发现这是一个二维偏序问题，可以主席树求解，时间复杂度 $O(m+n\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=2e5+5,MAXM=4e5+5,MAXL=20;
+struct Edge{
+	int to,next;
+}edge[MAXM<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+struct Tree{
+	vector<int> g[MAXN];
+	int p[MAXN],anc[MAXN][MAXL],dfn[MAXN],dfe[MAXN],dfv[MAXN],type,dfs_t;
+	int Find(int x){return x==p[x]?x:p[x]=Find(p[x]);}
+	void dfs(int u,int fa){
+		dfn[u]=++dfs_t;dfv[dfs_t]=u;anc[u][0]=fa;
+		_for(i,1,MAXL){
+			if(!anc[anc[u][i-1]][i-1])break;
+			anc[u][i]=anc[anc[u][i-1]][i-1];
+		}
+		_for(i,0,g[u].size())
+		dfs(g[u][i],u);
+		dfe[u]=dfs_t;
+	}
+	void build(int n,bool flag){
+		type=flag;
+		_rep(i,1,n)p[i]=i;
+		if(!type){
+			_rep(u,1,n){
+				for(int i=head[u];i;i=edge[i].next){
+					int v=Find(edge[i].to);
+					if(v>=u)continue;
+					p[v]=u;
+					g[u].push_back(v);
+				}
+			}
+			dfs(n,0);
+		}
+		else{
+			for(int u=n;u;u--){
+				for(int i=head[u];i;i=edge[i].next){
+					int v=Find(edge[i].to);
+					if(v<=u)continue;
+					p[v]=u;
+					g[u].push_back(v);
+				}
+			}
+			dfs(1,0);
+		}
+	}
+	int query(int u,int k){
+		if(!type){
+			for(int i=MAXL-1;i>=0;i--){
+				if(anc[u][i]&&anc[u][i]<=k)
+				u=anc[u][i];
+			}
+		}
+		else{
+			for(int i=MAXL-1;i>=0;i--){
+				if(anc[u][i]&&anc[u][i]>=k)
+				u=anc[u][i];
+			}
+		}
+		return u;
+	}
+}t1,t2;
+struct Node{
+	int sz,ch[2];
+}node[MAXN*MAXL];
+int root[MAXN],node_cnt;
+void update(int &k,int p,int lef,int rig,int pos){
+	node[k=++node_cnt]=node[p];
+	node[k].sz++;
+	if(lef==rig)return;
+	int mid=lef+rig>>1;
+	if(pos<=mid)
+	update(node[k].ch[0],node[p].ch[0],lef,mid,pos);
+	else
+	update(node[k].ch[1],node[p].ch[1],mid+1,rig,pos);
+}
+int query(int k1,int k2,int ql,int qr,int vl,int vr){
+	if(vl>qr||vr<ql)return 0;
+	if(ql<=vl&&vr<=qr)return node[k2].sz-node[k1].sz;
+	int vm=vl+vr>>1;
+	return query(node[k1].ch[0],node[k2].ch[0],ql,qr,vl,vm)+query(node[k1].ch[1],node[k2].ch[1],ql,qr,vm+1,vr);
+}
+int main()
+{
+	int n=read_int(),m=read_int(),q=read_int();
+	while(m--){
+		int u=read_int()+1,v=read_int()+1;
+		Insert(u,v);Insert(v,u);
+	}
+	t1.build(n,true);
+	t2.build(n,false);
+	_rep(i,1,n)
+	update(root[i],root[i-1],1,n,t2.dfn[t1.dfv[i]]);
+	while(q--){
+		int be=read_int()+1,en=read_int()+1,l=read_int()+1,r=read_int()+1;
+		be=t1.query(be,l),en=t2.query(en,r);
+		if(query(root[t1.dfn[be]-1],root[t1.dfe[be]],t2.dfn[en],t2.dfe[en],1,n))
+		enter(1);
+		else
+		enter(0);
+	}
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具