CF 786 B Legacy(線分樹最適化建図＋最短路)

qbxtのあるキャンプで集団でやった
題名の中と地方のOIerは基本的に2本の線分の木のを書きます
一方、私たち六安のOIer神TMの思考は一致しています.1つのセグメントツリーだけで、1次元の階層図の思想に似ています.第2層の第1層に対応するノードの番号は第1層のノード番号+NUMで、スコアの思考は正常なようです.lson=k<<1、rson=k<<1|1を満たすため、一般的なセグメントツリーと類似度が高いからです.
なぜパーティションや階層を分けるのかというと、ツリーエッジ(補助エッジ)が双方向でなければならない(先祖ノードの出入り情報を使うため)ことがわかりやすいのですが、パーティションや階層を分けなければ最短ルートを求めるのは明らかに0ではないでしょうかQwQ
したがって、階層化すると、親は1つのレイヤであり、子は別のレイヤであり、2つのレイヤの間はリーフノードで接続されます.
なお、リーフノードの処理については、YoOXiiiおよびPride 205は、原図第iノードをツリー上第i+nノード(nは原図ノード個数)に投影する
これは彼らのコードを詳しく見て(実は私も彼らの処理方法をよく研究していません)、ここは盗まないで(窃盗犯罪w)、自分で探すことを見ます
私は彼らと一緒に座らないので、考えている間に交流していないので、私はこのように書いていません.私は第1階を普通の線分の木の番号に従って建てて、このように簡単です.そして原図の結点を直接葉の結点にマッピングすればよい(pos配列を開く)(szsz 46もそう書いてあることが分かったが、もともと六安OIerの思考同期性は空間に従ってQwQを変えない)
そして・・・
コードをつけましょう

#include
#include
#include
#include
#include
#define NUM 1000000
#define maxn 100005<<5
//         
#define int long long
using namespace std;
typedef long long ll;

inline void input(ll &x){
    ll ans=0,f=1;
    char c=getchar();
    while(c>'9'||c='0'&&c<='9'){
        ans=ans*10+c-48;
        c=getchar();
    }
    x=ans*f;
}

inline void output(ll x){
    if(x<0)x=-x,putchar('-');
    if(x>9)output(x/10);
    putchar(x%10+48);
}

inline void writeln(ll x){
    output(x);
    putchar('
');
}

int n,m,s,head[maxn],c[maxn],pos[maxn],vis[maxn],dis[maxn],cnt;

//pos:           

struct edge{
    int v,w,next;
}e[maxn];

struct node{
    int dis,u;
    bool operator>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    add(k<<1,k,0);
    add(k<<1|1,k,0);
    add(k+NUM,(k<<1)+NUM,0);//      ：   ；     NUM    k NUM 
    add(k+NUM,(k<<1|1)+NUM,0);
}

inline void add(int k,int l,int r,int xl,int xr,int from,int w,int opt){
    if(xl<=l&&r<=xr){
        if(opt==2)add(from,k+NUM,w);
        else if(opt==3)add(k,from,w);
        return;
    }
    int mid=(l+r)>>1;
    if(xl<=mid)add(k<<1,l,mid,xl,xr,from,w,opt);
    if(xr>=mid+1)add(k<<1|1,mid+1,r,xl,xr,from,w,opt);
}

priority_queue q;

inline void dijkstra(){
    s=pos[s];
    q.push((node){0,s});
    dis[s]=0;
    while(!q.empty()){
        int x=q.top().u;
        q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int i=head[x];i!=-1;i=e[i].next){
            int y=e[i].v;
            if(!vis[y]&&dis[y]>dis[x]+e[i].w){
                dis[y]=dis[x]+e[i].w;
                q.push((node){dis[y],y});//    ，              
            }
        }
    }
    s<<=1;
    if(s>=1)dijkstra();
}

signed main(){
    memset(head,-1,sizeof(head));
    memset(dis,127,sizeof(dis));
    memset(vis,0,sizeof(vis));
    input(n);input(m);input(s);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int opt;
        input(opt);
        if(opt==1){
            int u,v,w;
            input(u);input(v);input(w);
            add(pos[u],pos[v],w);
        }
        else if(opt==2){
            int u,l,r,w;
            input(u);input(l);input(r);input(w);
            add(1,1,n,l,r,pos[u],w,opt);
        }
        else if(opt==3){
            int u,l,r,w;
            input(u);input(l);input(r);input(w);
            add(1,1,n,l,r,pos[u],w,opt);
        }
    }
    dijkstra();
//  for(int i=1;i<=4*n;i++)cout<

転載先:https://www.cnblogs.com/Y15BeTa/p/11318060.html