2020-2021:teams:legal_string:jxm2001:重构树
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
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> | </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> | ||
2020-2021/teams/legal_string/jxm2001/重构树.1602140461.txt.gz · 最后更改: 2020/10/08 15:01 由 jxm2001
