UOJ 393 【NOI2018】归程——可持久化并查集

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define mkp make_pair
#define pb push_back
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
const int N=2e5+,M=4e5+,INF=2e9+;
int n,m,hd[N],xnt,to[M<<],nxt[M<<],w[M<<],dis[N];
int fa[N],ht[N],mn[N],dep[N]; bool vis[N];
struct Ed{
int x,y,h;
Ed(int x=,int y=,int h=):x(x),y(y),h(h) {}
bool operator< (const Ed &b)const
{return h>b.h;}
}ed[M];
struct Node{
int h,v;
Node(int h=,int v=):h(h),v(v) {}
bool operator< (const Node &b)const
{return h>b.h;}
};
priority_queue<pair<int,int> > q;
vector<Node> Mn[N];
vector<Node>::iterator it;
void add(int x,int y,int z){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;w[xnt]=z;}
void dj()
{
memset(vis,,sizeof vis);
for(int i=;i<=n;i++)dis[i]=INF;
q.push(mkp(,));
while(q.size())
{
int k=q.top().second; q.pop();
if(vis[k])continue; vis[k]=;
for(int i=hd[k],v;i;i=nxt[i])
if(dis[v=to[i]]>dis[k]+w[i])
{
dis[v]=dis[k]+w[i];
q.push(mkp(-dis[v],v));
}
}
}
int fnd(int u,int p)
{
while(fa[u]!=u&&ht[u]>p)u=fa[u];
return u;
}
int fnd2(int u,int p)
{
it=--lower_bound(Mn[u].begin(),Mn[u].end(),Node(p,));
return (*it).v;
}
int main()
{
int T=rdn();
while(T--)
{
n=rdn();m=rdn();
xnt=; memset(hd,,sizeof hd);
for(int i=,u,v,l,h;i<=m;i++)
{
u=rdn();v=rdn();l=rdn();h=rdn();
add(u,v,l);add(v,u,l);
ed[i]=Ed(u,v,h);
}
dj(); sort(ed+,ed+m+);
for(int i=;i<=n;i++)
{
Mn[i].clear();
Mn[i].pb(Node(INF,mn[i]=dis[i]));
fa[i]=i; dep[i]=;
}
for(int i=;i<=m;i++)
{
int u=fnd(ed[i].x,), v=fnd(ed[i].y,);
if(u==v)continue;
if(dep[u]>dep[v])swap(u,v);
if(dep[u]==dep[v])dep[v]++;
fa[u]=v; ht[u]=ed[i].h;
if(mn[u]<mn[v])
Mn[v].pb(Node(ed[i].h,mn[v]=mn[u]));
}
int Q=rdn(),K=rdn(),S=rdn()+,ans=;
for(int i=,u,p;i<=Q;i++)
{
u=(rdn()+(K?ans:)-)%n+;
p=(rdn()+(K?ans:))%S;
u=fnd(u,p); ans=fnd2(u,p);
printf("%d\n",ans);
}
}
return ;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define mkp make_pair
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
int Mn(int a,int b){return a<b?a:b;}
const int N=2e5+,M=4e5+,K=*M,INF=;
int n,m,hd[N],xnt,to[M<<],nxt[M<<],w[M<<],dis[N];
int tp[M],rt[M],ht[M]; bool vis[N];
int tot,ls[K],rs[K],vl[K],dep[K],mn[K];
struct Ed{
int x,y,h;
Ed(int x=,int y=,int h=):x(x),y(y),h(h) {}
bool operator< (const Ed &b)const
{return h>b.h;}
}ed[M];
priority_queue<pair<int,int> > q;
void add(int x,int y,int z)
{to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;w[xnt]=z;}
void dj()
{
memset(vis,,sizeof vis);
for(int i=;i<=n;i++)dis[i]=INF;
q.push(mkp(,));
while(q.size())
{
int k=q.top().second; q.pop();
if(vis[k])continue; vis[k]=;
for(int i=hd[k],v;i;i=nxt[i])
if(dis[v=to[i]]>dis[k]+w[i])
dis[v]=dis[k]+w[i], q.push(mkp(-dis[v],v));
}
}
void build(int l,int r,int& cr)
{
cr=++tot;
if(l==r){vl[cr]=l;dep[cr]=;mn[cr]=dis[l];return;}
int mid=l+r>>;
build(l,mid,ls[cr]); build(mid+,r,rs[cr]);
}
void ins(int l,int r,int& cr,int pr,int p)
{
cr=++tot;ls[cr]=ls[pr];rs[cr]=rs[pr];
if(l==r)
{
vl[cr]=vl[pr];dep[cr]=dep[pr];
mn[cr]=mn[pr];return;
}
int mid=l+r>>;
if(p<=mid)ins(l,mid,ls[cr],ls[pr],p);
else ins(mid+,r,rs[cr],rs[pr],p);
}
int qry(int l,int r,int cr,int p)
{
if(l==r)return cr; int mid=l+r>>;
if(p<=mid)return qry(l,mid,ls[cr],p);
else return qry(mid+,r,rs[cr],p);
}
int fnd(int nw,int a)
{
int fa=qry(,n,nw,a);
if(vl[fa]==a)return fa;
return fnd(nw,vl[fa]);
}
int fnd2(int p)
{
int l=,r=m,ret=;//l=0
while(l<=r)
{
int mid=l+r>>;
if(ht[mid]>p)ret=mid,l=mid+;
else r=mid-;
}
return ret;
}
int main()
{
int T=rdn();
while(T--)
{
n=rdn();m=rdn();
xnt=; memset(hd,,sizeof hd);
for(int i=,u,v,l,a;i<=m;i++)
{
u=rdn();v=rdn();l=rdn();a=rdn();
add(u,v,l); add(v,u,l);
ed[i]=Ed(u,v,a); tp[i]=a;
}
dj(); int Q=rdn(),K=rdn(),S=rdn();
tot=;//////
sort(ed+,ed+m+); build(,n,rt[]);
/*
for(int i=1,u,v;i<=m;i++)
{
rt[i]=rt[i-1];
u=fnd(rt[i],ed[i].x); v=fnd(rt[i],ed[i].y);
if(vl[u]==vl[v])continue;
if(dep[u]>dep[v])swap(u,v);
ins(1,n,rt[i],rt[i],vl[u]);u=tot;
ins(1,n,rt[i],rt[i],vl[v]);v=tot;
vl[u]=vl[v]; mn[v]=Mn(mn[v],mn[u]);
if(dep[u]==dep[v])dep[v]++;
}
*/
int lm=m; m=;
for(int i=,u,v;i<=lm;m++)
{
rt[m]=rt[m-]; ht[m]=ed[i].h;
while(i<=lm&&ed[i].h==ht[m])
{
u=fnd(rt[m],ed[i].x); v=fnd(rt[m],ed[i].y);
i++; if(vl[u]==vl[v])continue;
if(dep[u]>dep[v])swap(u,v);
ins(,n,rt[m],rt[m],vl[u]);u=tot;
ins(,n,rt[m],rt[m],vl[v]);v=tot;
vl[u]=vl[v]; mn[v]=Mn(mn[v],mn[u]);
if(dep[u]==dep[v])dep[v]++;
}
}
int ans=; S++; m--; ht[]=INF;//
for(int i=,v,p;i<=Q;i++)
{
v=(rdn()+(K?ans:)-)%n+;
p=(rdn()+(K?ans:))%S; p=fnd2(p);
//p=lower_bound(ed+1,ed+m+1,Ed(0,0,p))-ed-1;
v=fnd(rt[p],v); ans=mn[v];
printf("%d\n",ans);
}
}
return ;
}