关于spfa
问题可以转化成，我们在所有海拔
>
p
>p
>p的边组成的图中，
v
v
v所在的连通块中，距离
1
1
1最近的一个点的距离
后半部分可以用spfa dijkstra解决
前面的这个东西，我们可以对于每一条边的海拔排序，从大到小建立可持久化并查集，维护一下并查集的min，相当于是可持久化带权并查集
复杂度
O
(
n
log
2
n
)
O(n\log^2n)
O(nlog2n)，实际得分在
90
90
90分左右
考虑优化，我们发现，每次合并两个可持久化带权并查集找父亲的时候，可以不用每次暴力找爸爸，而是用一个普通的并查集维护，这样每次查询只用
O
(
α
(
n
)
)
O(\alpha(n))
O(α(n))，比
O
(
log
2
n
)
O(\log^2n)
O(log2n)快了不少，实际大概可以快一半左右
然后就可以愉快的AC了
可持久化带权并查集的写法：
将
f
a
i
fa_i
fai可持久化，每次暴力向上跳，这样单次查询时
O
(
n
log
n
)
O(n\log n)
O(nlogn)的
考虑优化，利用按秩合并，每次把深度小的接到深度大的上面，这样深度最大是
log
\log
log的，单次查询可以做到
O
(
log
2
n
)
O(\log^2 n)
O(log2n)，深度数组同样可持久化一下
实际此题需要3个可持久化数组：
f
a
,
s
i
z
,
m
i
n
fa,siz,min
fa,siz,min，建议封装写法
#include <bits/stdc++.h>
using namespace std;
# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)
typedef long long ll;
const int N=2e5+5;
template<typename T> void read(T &x){
x=0;int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
x*=f;
}
int t,n,m,q,K,s;
int head[N],cnt;
int a[N];
int dis[N];
bool vis[N];
int bcj[N];
int bcj_find(int x){
if(bcj[x]==x)return x;
return bcj_find(bcj[x]);
}
struct Edge{
int to,next,w;
}e[N*8];
void add(int x,int y,int c){
e[++cnt]=(Edge){y,head[x],c},head[x]=cnt;
}
struct edge{
int u,v,w;
bool operator < (const edge &cmp)const{
return w>cmp.w;
}
}E[N*2];
struct node{
int d,p;
bool operator < (const node &cmp)const{
return d>cmp.d;
}
};
priority_queue<node> que;
void dij(){
Rep(i,1,n)dis[i]=2e9;
memset(vis,0,sizeof(vis));
que.push((node){0,1});
dis[1]=0;
while(!que.empty()){
int u=que.top().p;que.pop();
if(vis[u])continue;
vis[u]=true;
RepG(i,u){
int v=e[i].to;
if(dis[v]>dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
if(!vis[v])que.push((node){dis[v],v});
}
}
}
}
struct chair_tree{
int root[N*2],tot;
struct node{
int lc,rc;
int val;
}seg[N*60];
void clear(){
Rep(i,0,m)root[i]=0;
Rep(i,1,tot)seg[i].lc=seg[i].rc=seg[i].val=0;
tot=0;
}
int build(int l,int r){
int u=++tot;
if(l==r){
seg[u].val=a[l];
return u;
}
int mid=l+r>>1;
seg[u].lc=build(l,mid);
seg[u].rc=build(mid+1,r);
return u;
}
int update(int o,int l,int r,int x,int k){
int u=++tot;
seg[u]=seg[o];
if(l==r){
seg[u].val=k;
return u;
}
int mid=l+r>>1;
if(x<=mid)seg[u].lc=update(seg[u].lc,l,mid,x,k);
else seg[u].rc=update(seg[u].rc,mid+1,r,x,k);
return u;
}
int query(int u,int l,int r,int x){
if(l==r)return seg[u].val;
int mid=l+r>>1;
if(x<=mid)return query(seg[u].lc,l,mid,x);
else return query(seg[u].rc,mid+1,r,x);
}
}fa,dep,low;
int find(int x,int i){
int f=x;
while(1){
int faz=fa.query(fa.root[i],1,n,f);
if(faz==f)break;
f=faz;
}
return f;
}
void merge(int x,int y,int i){
int fax=bcj_find(x),fay=bcj_find(y);
if(fax==fay)return;
int dpx=dep.query(dep.root[i],1,n,fax),dpy=dep.query(dep.root[i],1,n,fay);
int lx=low.query(low.root[i],1,n,fax),ly=low.query(low.root[i],1,n,fay);
if(dpx<=dpy){
fa.root[i]=fa.update(fa.root[i],1,n,fax,fay);
dep.root[i]=dep.update(dep.root[i],1,n,fay,max(dpx+1,dpy));
low.root[i]=low.update(low.root[i],1,n,fay,min(lx,ly));
bcj[fax]=fay;
}
else{
fa.root[i]=fa.update(fa.root[i],1,n,fay,fax);
dep.root[i]=dep.update(dep.root[i],1,n,fax,max(dpy+1,dpx));
low.root[i]=low.update(low.root[i],1,n,fax,min(lx,ly));
bcj[fay]=fax;
}
}
int main()
{
read(t);
while(t--){
memset(head,-1,sizeof(head)),cnt=0;
read(n),read(m);
Rep(i,1,n)a[i]=i;
Rep(i,1,n)bcj[i]=i;
fa.root[0]=fa.build(1,n);
Rep(i,1,n)a[i]=1;
dep.root[0]=dep.build(1,n);
Rep(i,1,m){
int x,y,l,a;
read(x),read(y),read(l),read(a);
add(x,y,l),add(y,x,l);
E[i]=(edge){x,y,a};
}
dij();
Rep(i,1,n)a[i]=dis[i];
low.root[0]=low.build(1,n);
sort(E+1,E+m+1);
read(q),read(K),read(s);
Rep(i,1,m){
fa.root[i]=fa.root[i-1];
dep.root[i]=dep.root[i-1];
low.root[i]=low.root[i-1];
merge(E[i].u,E[i].v,i);
}
int lastans=0;
while(q--){
int v,p;
read(v),read(p);
v=(v+K*lastans-1)%n+1;
p=(p+K*lastans)%(s+1);
int l=1,r=m,pos=0;
while(l<=r){
int mid=l+r>>1;
if(E[mid].w>p)pos=mid,l=mid+1;
else r=mid-1;
}
lastans=low.query(low.root[pos],1,n,find(v,pos));
printf("%d\n",lastans);
}
fa.clear(),dep.clear(),low.clear();
}
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
