BZOJ 3073: [Pa2011]Journeys

Description

\(n\)个点，每次在\([a,b]\)到\([c,d]\)的点，分别连边 \(n\leqslant 5\times 10^5,m\leqslant 10^5\).

Solution

最短路+线段树.

线段树优化建图...

建两颗线段树，从一个线段树的节点出发，到另一颗线段树对应的节点即可。

同时把叶节点对应连起来.

然后每次连边新建一个中间的节点，不然直接连也可以，不过那样边数是\(O(n\log^2 n)\)的.

Code

/**************************************************************
    Problem: 3073
    User: BeiYu
    Language: C++
    Result: Accepted
    Time:17520 ms
    Memory:226032 kb
****************************************************************/
 
#include 
using namespace std;
 
#define mid ((l+r)>>1)
#define lc (o<<1)
#define rc (o<<1|1)
#define uor(i,j,k) for(int i=j;i<=(int)k;i++)
#define uep(i,j,k) for(int i=j;i<(int)k;i++)
 
const int N = 5005000;
 
inline int in(int x=0,char s=getchar()) { while(s>'9'||s<'0')s=getchar();
    while(s>='0'&&s<='9')x=x*10+s-'0',s=getchar();return x; }
 
int n,m,s,cp,B;
int id[N],d[N],b[N];
struct Edge { int v,w; };
bool operator < (const Edge &a,const Edge &b) { return a.w>b.w; }
 
vector g[N];
priority_queue q;
 
void AddEdge(int u,int v,int w) { g[u].push_back((Edge) { v,w }); }
void Build1(int o,int l,int r) {
//  cout< &res) {
    if(L<=l && r<=R) { res.push_back(o);return; }
    if(L<=mid) get_id(lc,l,mid,L,R,res);
    if(R>mid) get_id(rc,mid+1,r,L,R,res);
}
void Dijstra(int s) {
    memset(d,0x3f,sizeof(d));
    d[s]=0,q.push((Edge) { s,0 });
    for(int x;!q.empty();) {
        x=q.top().v,q.pop();
        if(b[x]) continue;b[x]=1;
        uep(i,0,g[x].size()) {
            int v=g[x][i].v,w=g[x][i].w;
            if(d[x]+w";
        uep(j,0,g[i].size()) cout< aa,bb;
        aa.clear(),bb.clear();
        get_id(1,1,n,a,b,aa),get_id(1,1,n,c,d,bb);
        x=++cp;
        uep(u,0,aa.size()) AddEdge(x,aa[u]+B,1);
        uep(v,0,bb.size()) AddEdge(bb[v],x,1);
        x=++cp;
        uep(v,0,bb.size()) AddEdge(x,bb[v]+B,1);
        uep(u,0,aa.size()) AddEdge(aa[u],x,1);
    }
//  cout< tmp;tmp.clear(),get_id(1,1,n,s,s,tmp),s=tmp[0];
//  cout<>1);
    return 0;
}