题解 P4768 【[NOI2018]归程】

场外选手休闲做题 kruskal重构树什么的根本没听说过啊…… ~~这里是愚蠢的$O(nlog^2n)$做法，然而跑的飞起~~ __________________ 首先如果我们仔细想一下的话，由于下车之后无论是不是积水的边都能走，所以下车之后一定会走到1号点的最短路 如此说来我们可以使用dijkstra算法处理出1号点到其他所有点的最短路 那么我们乘车的目的就是选择一个到一号点最短路最小的点下车 但是车是有使用限制的，我们只能走不积水的边 那么我们可以想到一个非常暴力的方式就是每次暴力的把所有还不积水的边塞到并查集里，此时我们查一发并查集中每个点到一号点的最小值即可知道此时到达一号点的最小步行距离 当然暴力是过不去的，但是我们可以考虑如何优化这个东西 发现每次的询问时给出了一个积水量，海拔大于这个积水量的边才有效。 那么我们可以尝试把所有边按照海拔排一个序，此时我们会发现每次询问相当于规定了一个前缀是生效的。 等等，每次一个边的前缀是生效的？ 现在我们将边从大到小依次加入并查集中，我们认为这个顺序就是时间顺序 显然我们的并查集会有n个版本(因为每次合并集合总数减少1) 每次应对询问的时候我们二分一下可以确定到底哪些边是生效的 这些边都生效且另外的边都不生效时的并查集，其实时我们把边排序依次加入并查集这个过程的某一个历史版本 为了回答询问我们需要知道某一个这个并查集的某一个历史版本长什么样，然后在这个的并查集的历史版本里面查一下最小值即可了 所以说，我们要实现一个并查集资瓷快速访问历史版本 可持久化并查集！ 如果不会的的话可以左转你站模板区 另外一件事时如果我们只是实现一个可持久化并查集的话会发现复杂度时$O((E+Q)log^2N)$基本过不去 但是我们做个小优化，我们写一个真实的不可持久化的并查集，然后将这个并查集的变化用可持久化数组记录下来 此时我们的复杂度变成了$O((N+E)logN+Qlog^2N)$此时常数压力就比较小了我们就可以(加)轻(上)松(快)的(读)通过本题 对了也是最重要的一点 # 关于spfa ~~它死了~~ 被负责任的出题人干掉了，所以请使用dijkstra 上代码~ ```C // luogu-judger-enable-o2 #include<cstdio> #include<algorithm> #include<queue> using namespace std; template <class T> void read(T &x){ char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } const int N=2*1e5+10;const int E=4*1e5+10;typedef long long ll; int n;int m;int q;ll k;ll s;int T;int dis[N];int cnt; struct data { int u;int v;int dep; friend bool operator <(data a,data b){return a.dep>b.dep;} }ed[E]; namespace dijkstra//最短路预处理 { int v[2*E];int x[2*E];int ct;int al[N];int val[2*E]; inline void add(int u,int V,int va){v[++ct]=V;x[ct]=al[u];al[u]=ct;val[ct]=va;} struct nod{int dis;int u;friend bool operator <(nod a,nod b){return a.dis>b.dis;}}; priority_queue <nod> pq;bool book[N]; inline void solve() { for(int i=1;i<=n;i++)dis[i]=0x7f7f7f7f;dis[1]=0;pq.push((nod){0,1}); while(!pq.empty()) { nod nw=pq.top();pq.pop();if(book[nw.u])continue;book[nw.u]=true; for(int i=al[nw.u];i;i=x[i]) if(!book[v[i]]&&dis[v[i]]>nw.dis+val[i]) dis[v[i]]=nw.dis+val[i],pq.push((nod){dis[v[i]],v[i]}); } } inline void clear() {for(int i=1;i<=n;i++)book[i]=false;for(int i=1;i<=n;i++)al[i]=0;ct=0;} } struct per_array//可持久化数组 { int s[20*E][2];int root[E];int w[20*E];int ct;int tim; inline void setval(int p1,int p2,int l,int r,const int& pos,const int& val) { if(r-l==1){w[p1]=val;return;}int mid=(l+r)/2; if(pos<=mid)s[p1][0]=++ct,s[p1][1]=s[p2][1],setval(ct,s[p2][0],l,mid,pos,val); else s[p1][1]=++ct,s[p1][0]=s[p2][0],setval(ct,s[p2][1],mid,r,pos,val); } inline int find(int p,int l,int r,const int& pos) { if(r-l==1){return w[p];}int mid=(l+r)/2; if(pos<=mid)return find(s[p][0],l,mid,pos); else return find(s[p][1],mid,r,pos); } inline void ih(int p,int l,int r,int* st)//并查集由于一开始数组不为空所以要初始化 { if(r-l==1){w[p]=st[r];return;}int mid=(l+r)/2; s[p][0]=++ct;s[p][1]=++ct;ih(s[p][0],l,mid,st);ih(s[p][1],mid,r,st); } inline void csval(const int& pos,const int& val) {root[++tim]=++ct;setval(root[tim],root[tim-1],0,n,pos,val);} inline void cih(int* st){ih(root[0]=++ct,0,n,st);} inline int cfind(const int& t,const int& p){return find(root[t],0,n,p);} inline void skip(){++tim;root[tim]=root[tim-1];} inline void clear(){ct=0;tim=0;} }pa1,pa2; struct bcj//普通的并查集，注意的是不要加路径压缩 { int fa[N];int siz[N];int mi[N]; inline void ih() { for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=n;i++)siz[i]=1;for(int i=1;i<=n;i++)mi[i]=dis[i]; pa1.cih(fa);pa2.cih(mi); } inline int f(int x){++cnt;return (fa[x]==x)?x:f(fa[x]);} inline void u(int x,int y) { int u=f(x);int v=f(y); if(u==v){pa1.skip();pa2.skip();return;} if(siz[u]>siz[v])swap(u,v); fa[u]=v;siz[v]+=siz[u];mi[v]=min(mi[v],mi[u]); pa1.csval(u,v);pa2.csval(v,mi[v]); } }bj; inline void solve()//解决问题 { read(n);read(m); for(int i=1,u,v,w,d;i<=m;i++) { read(u);read(v);read(w);read(d); dijkstra::add(u,v,w);dijkstra::add(v,u,w);ed[i]=(data){u,v,d};} dijkstra::solve();bj.ih();sort(ed+1,ed+m+1);ed[0].dep=0x7f7f7f7f; for(int i=1;i<=m;i++){bj.u(ed[i].u,ed[i].v);} ll lastans=0;read(q);read(k);read(s); for(int i=1;i<=q;i++) { ll v0;ll p0;read(v0);read(p0); v0=(v0+k*lastans-1)%n+1;p0=(p0+k*lastans)%(s+1);int l=0;int r=m; while(l!=r){int mid=(l+r+1)/2;if(ed[mid].dep<=p0)r=mid-1;else l=mid;} int p=v0;while(1){int fa=pa1.cfind(l,p);if(p==fa)break;else p=fa;} lastans=pa2.cfind(l,p);printf("%lld\n",lastans); } } inline void clear(){dijkstra::clear();pa1.clear();pa2.clear();} int main(){scanf("%d",&T);for(int z=1;z<=T;z++)solve(),clear();return 0;} ```