bzoj 3073 Journeys —— 线段树优化连边

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3073

建两棵线段树，一棵从下往上连边，一棵从上往下连边，叶子节点之间也有连边；

区间向区间连边时，可以新建一个节点，logn 条边就能变成 2logn 条边；

注意区间向区间连边也要连反边，别忘了连反边时 ++cnt !

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define mid ((l+r)>>1)

using namespace std;

int const xxn=5e5+,xn=4e6+,xm=3e7+;

int n,m,hd[xn],ct,to[xm],nxt[xm],w[xm],dis[xn];

int rt[],cnt,ls[xxn<<],rs[xxn<<],st[xxn],ed[xxn];

bool vis[xn];

struct N{

  int d,id;

  bool operator < (const N &y) const

  {return d==y.d?id<y.id:d>y.d;}

};

priority_queue<N>q;

int rd()

{

  int ret=,f=; char ch=getchar();

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

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

  return f?ret:-ret;

}

int gt[];

void wr(int x)

{

  if(!x){puts(""); return;}

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

  int t=;

  while(x)gt[++t]=x%,x/=;

  for(int i=t;i;i--)putchar(gt[i]+'');

  puts("");

}

void add(int x,int y,int z){to[++ct]=y; nxt[ct]=hd[x]; w[ct]=z; hd[x]=ct;}

void build(int x,int l,int r,bool tp)

{

  if(l==r)

    {

      if(!tp)st[l]=x; else ed[l]=x;

      return;

    }

  ls[x]=++cnt; rs[x]=++cnt;

  build(ls[x],l,mid,tp); build(rs[x],mid+,r,tp);

  if(!tp)add(ls[x],x,),add(rs[x],x,);

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

}

void link(int x,int l,int r,int L,int R,int c,bool tp)

{

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

    {

      if(!tp)add(x,c,); else add(c,x,);

      return;

    }

  if(mid>=L)link(ls[x],l,mid,L,R,c,tp);

  if(mid<R)link(rs[x],mid+,r,L,R,c,tp);

}

void dij(int s)

{

  memset(dis,0x3f,sizeof dis);

  dis[s]=; q.push((N){,s});

  while(q.size())

    {

      int x=q.top().id; q.pop();

      if(vis[x])continue; vis[x]=;

      for(int i=hd[x],u;i;i=nxt[i])

    if(dis[u=to[i]]>dis[x]+w[i])

      dis[u]=dis[x]+w[i],q.push((N){dis[u],u});

    }

}

int main()

{

  n=rd(); m=rd(); int p=rd();

  rt[]=++cnt; build(rt[],,n,);

  rt[]=++cnt; build(rt[],,n,);

  for(int i=;i<=n;i++)add(ed[i],st[i],);

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

    {

      a=rd(); b=rd(); c=rd(); d=rd(); int t=++cnt;

      link(rt[],,n,a,b,t,); link(rt[],,n,c,d,t,);

      t=++cnt;//!!!

      link(rt[],,n,c,d,t,); link(rt[],,n,a,b,t,);

    }

  dij(ed[p]);

  for(int i=;i<=n;i++)wr(dis[ed[i]]);

  return ;

}