YbtOJ 664「可持久化数据结构」进制路径

(Updated: )
oi
, ,

题目链接：YbtOJ #664

小 A 有一张 $n$ 个点 $m$ 条边的无向图。图中标号为 $i$ 的边可以用一个三元组 $(u_i,v_i,x_i)$ 表示，其中 $u_i,v_i$ 为它的两个端点，长度为 $2^{x_i}$。

现在他指定了图中的两个点 $s,t$，求 $s$ 到 $t$ 的最短路长度，并任意给出一条最短路径。

$1\le n\le10^5$，$0\le m\le10^5$，$0\le x_i\le10^5$。

Solution

这里的最短路和普通的最短路是一样的，唯一区别就是边权很大。则我们需要支持的操作就应该是大二进制数的加法和比大小。

我们对于每个点，开一个线段树，每一位维护二进制下这一位的值，表示其距离。

然后由于边权是 $2$ 的幂，所以也就相当于在二进制下某一位上加上 $1$。

如果要给第 $x$ 位加 $1$，就是要找到大于等于 $x$ 的最低的为 $0$ 的位（设其为 $t$），然后把 $x\sim t-1$ 这些位上改为 $0$，把第 $t$ 位改为 $1$。

而要求出大于等于第 $x$ 位的最低为 $0$ 的位，可以考虑二分。假设当前二分到 $mid$，那么若 $x\sim mid$ 间的 $1$ 的个数小于等于 $t-x$，就说明 $x\sim mid$ 之间存在至少一个 $0$，返回 true，否则返回 false。

接下来考虑如何比较两个大二进制数的大小。

可以从两棵线段树的根节点出发，由于比较的是最高位，所以若两个节点右儿子不同，就去比较右儿子；若两个节点右儿子相同，才去比较左儿子。而要快速判断两个右儿子是否一样，只要哈希一下就可以了。

具体实现中对于每个点开一棵线段树显然不现实，可以用主席树来优化。

Code

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
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    #define FS 100000
    #define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
    #define pc(c) (FC==FE&&(clear(),0),*FC++=c)
    int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
    I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
    Tp I void read(Ty& x) {x=0;RI f=1;W(!isdigit(oc=tc())) f=oc^'-'?1:-1;W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));x*=f;}
    Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
    Tp I void write(Ty x) {x<0&&(pc('-'),x=-x);W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);}
    Tp I void writeln(Ty x) {x<0&&(pc('-'),x=-x);W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
Cn int N=1e5+100,p=1e9+7;
int n,m,vis[N],Pr[N],fir[N],nxt[N<<1],son[N<<1],w[N<<1],tot,rt[N],b[N];
class ChairmanTree{
    private:
        int cnt;struct node{int l,r,v,s;}T[N*200];
        #define mid (l+r>>1)
        #define LT l,mid
        #define RT mid+1,r
        #define PT CI l=0,CI r=N-1
        I void PU(CI x){T[x].s=T[T[x].l].s+T[T[x].r].s,T[x].v=(T[T[x].r].v+T[T[x].l].v)%p;}
    public:
        I int S(CI p){return T[p].s;} 
        I int Q(CI p){return T[p].v;};
        I bool O(CI x,CI y,PT){if(l==r) return T[x].v>T[y].v;return T[T[x].r].v==T[T[y].r].v?O(T[x].l,T[y].l,LT):O(T[x].r,T[y].r,RT);}
        I int QS(CI x,CI L,CI R,PT){if(L<=l&&r<=R) return T[x].s;RI X=0;return L<=mid&&(X+=QS(T[x].l,L,R,LT)),R>mid&&(X+=QS(T[x].r,L,R,RT)),X;}
        I int F(CI x,CI v){RI l=v,r=N,X=v;W(l<=r) QS(x,v,mid)<=mid-v?X=mid,r=mid-1:l=mid+1;return X;}
        I void U0(int& x,CI L,CI R,PT){if(T[++cnt]=T[x],x=cnt,L<=l&&r<=R) return void(x=0);L<=mid&&(U0(T[x].l,L,R,LT),0),R>mid&&(U0(T[x].r,L,R,RT),0),PU(x);}
        I void U1(int& x,CI p,PT){if(T[++cnt]=T[x],x=cnt,l==r) return T[x].s=1,(void)(T[x].v=b[l]);p<=mid?U1(T[x].l,p,LT):U1(T[x].r,p,RT),PU(x);}
        I int A(CI x,CI v){RI t=F(x,v),w=x;v^t&&(U0(w,v,t-1),0);U1(w,t);return w;}
}T;
I void Add(CI x,CI y,CI z){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y,w[tot]=z;}
#define to son[i]
struct node{int x,rt;}u;
I bool operator < (Cn node& A,Cn node& B){return T.O(A.rt,B.rt);}
priority_queue<node> q;
int s,t;I void Prt(CI x,CI d){x==s?writeln(d),write(x),pc(' '):(Prt(Pr[x],d+1),write(x),pc(' '));}
int main(){
    freopen("base.in","r",stdin),freopen("base.out","w",stdout);
    RI i,x,y,z;for(read(n,m,s,t),i=1;i<=m;i++) read(x,y,z),Add(x,y,z),Add(y,x,z);for(b[0]=i=1;i<N;++i) b[i]=(1ll*b[i-1]<<1)%p;
    q.push((node){s,rt[s]});W(!q.empty()) if(u=q.top(),q.pop(),!vis[u.x])
        for(vis[u.x]=1,u.x==t&&(writeln(T.Q(rt[t])),Prt(t,1),pc('\n'),clear(),exit(0),0),i=fir[u.x];i;i=nxt[i])
            x=T.A(u.rt,w[i]),(!rt[to]T.O(rt[to],x))&&(q.push((node){to,rt[to]=x}),Pr[to]=u.x);
    return writeln(-1),clear(),0;
}