bzoj 3073 [Pa2011]Journeys ——线段树优化连边

题目：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+,M=3e7+,K=5e5+;

int n,m,p,tot,hd[N],xnt,to[M],nxt[M],w[M],ls[K<<],rs[K<<],dis[N];

int rt,d0[K],d1[K];

bool vis[N];

priority_queue<pair<int,int> > q;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return fx?ret:-ret;

}

void wrt(int x)

{

  if(x<)putchar('-'),x=-x;

  if(x<){putchar(x+'');return;}

  wrt(x/); putchar(x%+'');

}

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],);

      return;

    }

  int mid=l+r>>;

  ls[cr]=++tot; build(l,mid,ls[cr],fx);

  rs[cr]=++tot; build(mid+,r,rs[cr],fx);

  if(fx)add(cr,ls[cr],),add(cr,rs[cr],);

  else add(ls[cr],cr,),add(rs[cr],cr,);

}

void mdfy(int l,int r,int cr,int L,int R,bool fx)

{

  if(l>=L&&r<=R)

    {

      if(!fx)add(cr,tot,);

      else add(tot,cr,);

      return;

    }

  int mid=l+r>>;

  if(L<=mid)mdfy(l,mid,ls[cr],L,R,fx);

  if(mid<R)mdfy(mid+,r,rs[cr],L,R,fx);

}

int main()

{

  n=rdn(); m=rdn(); p=rdn();

  tot=; build(,n,,);

  rt=++tot; build(,n,rt,);

  for(int i=,a,b,c,d;i<=m;i++)

    {

      a=rdn(); b=rdn(); c=rdn(); d=rdn();

      tot++; mdfy(,n,,a,b,); mdfy(,n,rt,c,d,);

      tot++; mdfy(,n,,c,d,); mdfy(,n,rt,a,b,);

    }

  memset(dis,0x3f,sizeof dis);

  dis[d1[p]]=; q.push(make_pair(,d1[p]));

  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(make_pair(-dis[v],v));

    }

    }

  for(int i=;i<=n;i++,puts(""))wrt(dis[d1[i]]);

  return ;

}