YZOJ P3392 越野赛车问题
时间限制:1000MS 内存限制:262144KB
难度: \(6.0\)
-
问题描述
某山上一共有 \(n\) 个广场,编号依次为 \(1\) 到 \(n\),这些广场之间通过 \(n-1\) 条双向车道直接或间接地连接在一起。对于每条车道 \(i\),可以用四个正整数 \(u_i, v_i, l_i, r_i\) 描述,表示车道连接广场 \(u_i\) 和 \(v_i\),其速度承受区间为 \([l_i, r_i]\),即汽车必须以不小于 \(l_i\) 且不大于 \(r_i\) 的速度经过车道 \(i\) 。
现计划进行 \(m\) 次训练,每次选择某山上的一条简单路径,然后在这条路径上行驶,且每次训练时的车速都是固定的。现在有在 m 次训练中分别计划使用的车速,要求一条合法的路径(车速在所有车道的速度承受区间的交集内),使得路径上经过的车道数最大。
-
数据输入
输入文件的第一行包含两个正整数 \(n, m\),表示广场数和训练次数。接下来 \(n-1\) 行,每行四个正整数 \(u_i, v_i, l_i, r_i ( \leq n)\),描述所有车道。最后 \(m\) 行,每行一个正整数 \(v (\leq n)\) ,表示每次训练是的车速。
-
结果输出
输出 \(m\) 行,输出每次训练时的行驶路径经过的最大车道数。
-
样例输入
1 2 3 4 5 6 7 8 |
5 3 3 2 2 4 1 5 2 5 4 5 2 2 1 2 3 5 1 2 3 |
-
样例输出
1 2 3 |
0 2 3 |
-
数据范围
数据点 | \(n\) | \(m\) | 约定 |
1 | \(=5\) | \(5\) | – |
2 | \(=20\) | \(20\) | |
3 | \(=50000\) | \(=50000\) | \(l_i = 1, u_i = i, v_i = i +1\) |
4 | \(=70000\) | \(=70000\) | |
5 | \(=50000\) | \(=50000\) | \(u_i = i, v_i = i +1\) |
6 | \(=70000\) | \(=70000\) | |
7 | \(=50000\) | \(=50000\) | \(l_i = 1\) |
8 | \(=70000\) | \(=70000\) | |
9 | \(=50000\) | \(=50000\) | – |
10 | \(=70000\) | \(=70000\) |
首先对于 \(n,m \leq 20\) 的数据,随便乱搜都能过。
然后是对于 \(l_i = 1\) 的数据,也就是说最小允许的速度都是 \(1\) ,只要考虑 \(r_i\) 造成的影响。
所以可以想到按照边的 \(r_i\) 降序排序,同时把询问离线也按照 \(v_i\) 降序排序,每次只需要把所有 \(r\) 比当前询问 \(v\) 大的边加入某个数据结构维护,然后更新答案即可。
由于这里维护的是连通性,所以很自然的想到并查集。但是要求的答案是最长链的长度,所以需要对并查集中的每一个连通子树维护其中最长链的两个端点,设为 \(\{x, y\}\) 。
合并两个并查集的时候,假设另一个并查集最长链的两个端点为 \(\{s, t\}\) ,那么合并后子树的最长链只有六种情况:\(\{x,y\}, \{s,t\}, \{x,s\}, \{x,t\}, \{y,s\}, \{y,t\}\) ,求两点距离的时候用树链剖分或倍增 lca 转换一下。
证明请见YJC同学的补充题解。
这样时间复杂度就是 lca \(+\) 并查集 \(+\) std::sort \(= O(nlogn)\) 。
对于所有的数据,\(l_i\) 不一定都为 \(1\) ,也就是说必须考虑 \(l_i\) 造成的影响。若此时还是按照之前的做法,那就需要带权并查集支持任意撤销一条边的连接,这是非常不现实的。
换一种思考方法,把区间 \([l_i, r_i]\) 看作时间区间,那么一条边将在 \(l_i\) 时刻出现,并在 \(r_i\) 时刻后消失,询问 \(v\) 就是询问 \(v\) 时刻的答案。
同时注意到 \(l_i, r_i, v_i \leq n \leq 70000\) ,所以想到线段树分治。
线段树分治其实就是按照时间分治,因为分治的区间 \([l, mid], (mid, r]\) 极其类似于线段树分治的区间形式(几乎是一样的),所以可以用分治的方法遍历线段树,同时合并(利用)线段树上维护的信息进行答案的更新。
对于此题来说,对 \(v\) 进行分治,分治区间 \([l, r]\) 维护速度在 \([l, r]\) 范围时的合法的边。显然不能对每个这样的区间(总共不超过 \(4n\) 个)都存下所有的合法的边,这时候线段树的思想就派上用场了。
线段树查询的复杂度只有 \(logn\) ,因为若区间 \([l, r]\) 已经被询问区间完全包含,那么就不用继续往下寻找,直接利用这个区间点的信息更新答案即可。同理,线段树分治也是如此。若一条边在速度为区间 \([l, r]\) 的范围内已经合法,那么就不用对于 \([l, r]\) 内的其余所有子区间都添加这条边了,因为只有分治到 \([l, r]\) 时需要添加这条边的信息,之后分治进的子区间就再也不需要了。这样一条边就最多只会被 \(O(logn)\) 个区间所添加,时间和空间复杂度都是可以接受的。
现在还剩最后一个问题,分治时需要在返回之前撤销在这一层中并查集添加的边。发现只要简单的按栈序撤销即可,所以并查集不能有路径压缩,写一个按秩合并(启发式合并),还原时记得把 \(f\) 数组,\(size\) 或 \(rank\) ,维护的最长链的两个端点,所有连通子树中最长链最大长度(答案) 全部还原!
这样时间复杂度就是 lca \(+\) 并查集 \(+\) 线段树分治 \(= O(nlogn)\) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <algorithm> #define _max(_a_,_b_) ((_a_)>(_b_)?(_a_):(_b_)) #ifdef ONLINE_JUDGE char __B[1<<15],*__S=__B,*__T=__B; #define getchar() (__S==__T&&(__T=(__S=__B)+fread(__B,1,1<<15,stdin),__S==__T)?EOF:*__S++) #endif inline int getnum() { register char c=0; while(!(c>='0' && c<='9')) c=getchar(); register int a=0; while(c>='0' && c<='9') { a*=10;a+=c-'0'; c=getchar(); } return a; } int N; int ghead[105050],gnext[205050],gnode[205050],gcnt; inline void ginsertLine(register int s,register int t) { gnode[++gcnt]=t,gnext[gcnt]=ghead[s],ghead[s]=gcnt; gnode[++gcnt]=s,gnext[gcnt]=ghead[t],ghead[t]=gcnt; } /*int _log[105050],lf[105050][20],depth[105050]; void DFS(register int o,register int fa) { for(register int j=ghead[o];j;j=gnext[j]) if(gnode[j] != fa) { depth[gnode[j]]=depth[o]+1; lf[gnode[j]][0]=o; DFS(gnode[j],o); } } inline void initLCA() { for(register int i=1;i<=N;i++) _log[i]=_log[i>>1]+1; for(register int k=1;(1<<k)<=N;k++) for(register int i=1;i<=N;i++) lf[i][k]=lf[lf[i][k-1]][k-1]; } inline int getLCA(register int x,register int y) { if(depth[x]>depth[y]) x^=y^=x^=y; register int df=depth[y]-depth[x]; for(register int k=0;(1<<k)<=df;k++) if((1<<k)&df) y=lf[y][k]; if(x!=y) { for(register int k=_log[N];k>=0;k--) if(lf[x][k] != lf[y][k]) x=lf[x][k],y=lf[y][k]; x=lf[x][0]; } return x; }*/ int depth[105050],father[105050],lsize[105050],lson[105050],ltop[105050]; void DFS(register int o) { lsize[o]=1; for(register int j=ghead[o];j;j=gnext[j]) if(gnode[j] != father[o]) { depth[gnode[j]]=depth[o]+1; father[gnode[j]]=o; DFS(gnode[j]); lsize[o]+=lsize[gnode[j]]; if(lsize[gnode[j]] > lsize[lson[o]]) lson[o]=gnode[j]; } } void DFS1(register int o) { if(o==lson[father[o]]) ltop[o]=ltop[father[o]]; else ltop[o]=o; for(register int j=ghead[o];j;j=gnext[j]) if(gnode[j] != father[o]) DFS1(gnode[j]); } inline int getLCA(register int x,register int y) { while(ltop[x] != ltop[y]) if(depth[ltop[x]] > depth[ltop[y]]) x=father[ltop[x]]; else y=father[ltop[y]]; return (depth[x]<depth[y] ? x : y); } struct _edge { int s,t; }edges[105050]; int qhead[305050],qnext[2050505],qidx[2050505],qcnt; int Qvl,Qvr,Qpos; inline void ModifyTreeAddQuery(register int O,register int L,register int R) { if(L>=Qvl && R<=Qvr) { qidx[++qcnt]=Qpos,qnext[qcnt]=qhead[O],qhead[O]=qcnt; return; } register int mid=(L+R)>>1; if(Qvl<=mid) ModifyTreeAddQuery(O<<1,L,mid); if(Qvr>mid) ModifyTreeAddQuery(O<<1|1,mid+1,R); } struct _link { int x,y,len; _link operator += (const _link&o) { register int ax=x,ay=y,alen=len; #define SetAns(_olen,_ox,_oy) \ if((_olen)>alen)alen=_olen,ax=_ox,ay=_oy; #define getDIS(_x,_y) \ (depth[_x]+depth[_y]-(depth[getLCA(_x,_y)]<<1)) SetAns(o.len,o.x,o.y); SetAns(getDIS(x,o.x),x,o.x); SetAns(getDIS(x,o.y),x,o.y); SetAns(getDIS(y,o.x),y,o.x); SetAns(getDIS(y,o.y),y,o.y); x=ax,y=ay,len=alen; return *this; } }ulink[105050],hslink[105050]; int uf[105050],usize[105050]; inline int UnionFind(register int x) { while(x!=uf[x]) x=uf[x]; return x; } int hsuf[105050][2],hstop; inline int UnionMerge(register int x,register int y) { x=UnionFind(x),y=UnionFind(y); if(x==y) return ulink[x].len; if(usize[x]<usize[y]) x^=y^=x^=y; uf[y]=x,usize[x]+=usize[y]; hsuf[++hstop][0]=x,hsuf[hstop][1]=y; hslink[hstop]=ulink[x]; return (ulink[x]+=ulink[y]).len; } inline void UnionUndo() { register int x=hsuf[hstop][0],y=hsuf[hstop][1]; uf[y]=y,usize[x]-=usize[y]; ulink[x]=hslink[hstop--]; } int ans[105050]; void Divide(register int O,register int l,register int r,register int nans) { register int ohstop=hstop; for(register int j=qhead[O];j;j=qnext[j]) { register int tans=UnionMerge(edges[qidx[j]].s,edges[qidx[j]].t); nans=_max(nans,tans); } if(l==r) ans[l]=nans; else { register int mid=(l+r)>>1; Divide(O<<1,l,mid,nans),Divide(O<<1|1,mid+1,r,nans); } while(hstop>ohstop) UnionUndo(); } int main() { register int N=getnum(),M=getnum(); ::N=N; for(register int i=1;i<=N-1;i++) { register int u=getnum(),v=getnum(); ginsertLine(u,v); edges[i]=(_edge){u,v}; Qvl=getnum(),Qvr=getnum(),Qpos=i; ModifyTreeAddQuery(1,1,N); } //DFS(1,0),initLCA(); DFS(1),DFS1(1); for(register int i=1;i<=N;i++) uf[i]=i,usize[i]=1,ulink[i]=(_link){i,i,0}; Divide(1,1,N,0); for(register int i=1;i<=M;i++) printf("%d\n",ans[getnum()]); return 0; } |