题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3073
建两棵线段树，一棵孩子向父亲连边，是走出去的；一棵父亲向孩子连边，是走进来的。
注意第二棵线段树的叶子向第一棵线段树的叶子连边。
在树上节点间连边的时候，不是 log^2 地直接连，而要新建一个节点作中转点，这样边数就是 2*log 的；连向中转点和连出去的边一部是0一部是1或者全是0.5即可。
注意连无向边。两种方向当然是两个中转点。
边数 3e7 似乎还是小。但能过。更大就开不下了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=4e6+5,M=3e7+5,K=5e5+5; int n,m,p,tot,hd[N],xnt,to[M],nxt[M],w[M],ls[K<<2],rs[K<<2],dis[N]; int rt,d0[K],d1[K]; bool vis[N]; priority_queue<pair<int,int> > q; int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar(); return fx?ret:-ret; } void wrt(int x) { if(x<0)putchar('-'),x=-x; if(x<10){putchar(x+'0');return;} wrt(x/10); putchar(x%10+'0'); } void add(int x,int y,int z) { to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;w[xnt]=z; } void build(int l,int r,int cr,bool fx) { if(l==r) { if(!fx)d0[l]=cr; else d1[l]=cr,add(cr,d0[l],0); return; } int mid=l+r>>1; ls[cr]=++tot; build(l,mid,ls[cr],fx); rs[cr]=++tot; build(mid+1,r,rs[cr],fx); if(fx)add(cr,ls[cr],0),add(cr,rs[cr],0); else add(ls[cr],cr,0),add(rs[cr],cr,0); } void mdfy(int l,int r,int cr,int L,int R,bool fx) { if(l>=L&&r<=R) { if(!fx)add(cr,tot,1); else add(tot,cr,0); return; } int mid=l+r>>1; if(L<=mid)mdfy(l,mid,ls[cr],L,R,fx); if(mid<R)mdfy(mid+1,r,rs[cr],L,R,fx); } int main() { n=rdn(); m=rdn(); p=rdn(); tot=1; build(1,n,1,0); rt=++tot; build(1,n,rt,1); for(int i=1,a,b,c,d;i<=m;i++) { a=rdn(); b=rdn(); c=rdn(); d=rdn(); tot++; mdfy(1,n,1,a,b,0); mdfy(1,n,rt,c,d,1); tot++; mdfy(1,n,1,c,d,0); mdfy(1,n,rt,a,b,1); } memset(dis,0x3f,sizeof dis); dis[d1[p]]=0; q.push(make_pair(0,d1[p])); while(q.size()) { int k=q.top().second; q.pop(); if(vis[k])continue; vis[k]=1; 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(make_pair(-dis[v],v)); } } for(int i=1;i<=n;i++,puts(""))wrt(dis[d1[i]]); return 0; }