【PA2011】【BZOJ3073】Journeys

Description
Seterは大きな星を建て、Nカ国と無数の双方向道路を建設するつもりだ.Nの国はすぐに建てられました.N番号ですが、彼は道が多すぎることに気づきました.彼が1本建てるのは不可能です.そこで彼は以下のように道路を建設した:(a,b)、(c,d)は、任意の2つの国x,yに対して、a<=x<=b,c<=y<=dであれば、xyの間に道路を建設することを示す.Seterは1つの道路が2回も建設されないことを保証し、1つの国と自分の間に道路があることを保証します.Seterはやっとすべての道路を建てた.彼は今P号の首都にいる.SeterはP号の国からどの国まで少なくともいくつかの道を通る必要があることを知りたい.もちろん、SeterはP号の国がどの国にも行けることを保証します.
注意:重辺Inputがある場合があります
最初の行の3つの数N,M,P.N<=500000,M<=100000. 後M行、各行4個の数A,B,C,D.1<=A<=B<=N,1<=C<=D<=N.
Output
N行、i行目はP番の国からi番目の国まで少なくともいくつかの道を通る必要があることを示しています.明らかにP行目は0であるべきだ.
Sample Input
5 3 4
1 2 4 5
5 5 4 4
1 1 3 3
Sample Output
1
1
2
0
1 HINT
Source
seter翻訳
線分樹は建図の最短路を最適化する.(あれこれは本当に線分の木を計算して図を最適化しますか..私の個人の定義はあまり厳格ではありませんかもしれませんカードのメモリ..最後に試みて辺の配列を開けて300 W過ぎますことができます

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#define MAXN 500010
#define GET (ch>='0'&&ch<='9')
#define lchild rt<<1,l,mid
#define rchild rt<<1|1,mid+1,r
#define ln rt<<1
#define rn rt<<1|1
using namespace std;
int n,m,p,top,tp,cnt;
int a,b,c,d,tl,tr;
set<int> s;
set<int>::iterator it,sta[MAXN];
inline void in(int &x)
{
    char ch=getchar();x=0;
    while (!GET)    ch=getchar();
    while (GET) x=x*10+ch-'0',ch=getchar();
}
int root[MAXN],dis[MAXN];
struct edge {   int al,ar;edge *next;   }e[MAXN*6],*prev[MAXN*2+50000];
inline void build(int rt=1,int l=1,int r=n)
{
    if (l==r)   {   root[l]=rt;return;  }
    int mid=(l+r)>>1;build(lchild);build(rchild);
}
inline void insert(int rt,int l,int r,int L,int R)
{
    int mid=(L+R)>>1;
    if (l<=L&&r>=R) {   e[++top].al=tl;e[top].ar=tr;e[top].next=prev[rt];prev[rt]=&e[top];return;   }
    if (r<=mid) insert(ln,l,r,L,mid);
    else    if (l>mid)  insert(rn,l,r,mid+1,R);
    else    insert(ln,l,mid,L,mid),insert(rn,mid+1,r,mid+1,R);
}
int main()
{
    int x,t;
    for (in(n),in(m),in(p),build();m;m--)
        in(a),in(b),in(c),in(d),
        tl=c,tr=d,insert(1,a,b,1,n),
        tl=a,tr=b,insert(1,c,d,1,n);
    queue<int>  q;q.push(p);
    for (int i=1;i<=n+1;i++)    if (i!=p)   s.insert(i);
    while (!q.empty())
    {
        x=q.front();t=dis[x];q.pop();x=root[x];
        for (;x;prev[x]=0x0,x>>=1)
            for (edge *i=prev[x];i;i=i->next)
            {
                for (cnt=0,it=s.lower_bound(i->al);*it<=i->ar;it++) dis[*it]=t+1,q.push(*it),sta[++cnt]=it;
                while (cnt) s.erase(sta[cnt--]);
            }
    }
    for (int i=1;i<=n;i++)  printf("%d
",dis[i]);
}