萌新求助线段树优化建图板子

只有 20 qwq

#include<iostream>
#include<deque>
#include<cstring>
using namespace std;
const int N=500100,M=100100,LG=10,inf=0x3f3f3f3f;
int edge;
int head[N<<2],to[(N<<2)+8*LG*LG*M],nex[(N<<2)+8*LG*LG*M],wei[(N<<2)+8*LG*LG*M];
inline void insert(int u,int v,int w){
    to[++edge]=v;
    nex[edge]=head[u];
    head[u]=edge;
    wei[edge]=w;
}
int ver;
int L[N<<1],R[N<<1],ls[N<<1],rs[N<<1],rt;
int loc[N];
inline int New(int L_,int R_,int ls_,int rs_){
    L[++ver]=L_;R[ver]=R_;ls[ver]=ls_,rs[ver]=rs_;
    return ver;
}
int build(int l,int r){
    if(l==r)return loc[l]=New(l,r,0,0);
    int mid=(l+r)>>1;
    return New(l,r,build(l,mid),build(mid+1,r));
}
void get_range(int nd,int l,int r,int blk[],int&tot){
    if(l<=L[nd]&&R[nd]<=r){blk[++tot]=nd;return;}
    if(l<=R[ls[nd]])get_range(ls[nd],l,r,blk,tot);
    if(r>=L[rs[nd]])get_range(rs[nd],l,r,blk,tot);
}
int x[N],y[N];
int n,m,P;
void init(){
    cin>>n>>m>>P;
    rt=build(1,n);
    for(int i=1;i<=ver;i++){
        if(ls[i])insert(ls[i],i,0),insert(i+ver,ls[i]+ver,0);
        if(rs[i])insert(rs[i],i,0),insert(i+ver,rs[i]+ver,0);
    }
    for(int i=1;i<=n;i++)insert(loc[i]+ver,loc[i],0);
    for(int i=1;i<=m;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        int cnt1=0,cnt2=0;
        get_range(rt,a,b,x,cnt1);
        get_range(rt,c,d,y,cnt2);
        for(int j=1;j<=cnt1;j++){
            for(int k=1;k<=cnt2;k++)insert(x[j],y[k]+ver,1),insert(y[k],x[j]+ver,1);
        }
    }
}
int dis[N<<2];
deque<int>q;
void bfs(int s){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    q.push_back(s);
    while(!q.empty()){
        int nd=q.front();
        q.pop_front();
        for(int i=head[nd];i;i=nex[i]){
            if(dis[to[i]]<inf)continue;
            dis[to[i]]=dis[nd]+wei[i];
            if(wei[i])q.push_back(to[i]);
            else q.push_front(to[i]);
        }
    }
}
int main(){
    // freopen("read.in","r",stdin);
    init();
    bfs(loc[P]+ver);
    for(int i=1;i<=n;i++)cout<<dis[loc[i]+ver]<<endl;
    return 0;
}