bzoj3073:[Pa2011]Journeys线段树建边优化

bzoj3073: [Pa2011]Journeys

Description

Seter建造了一个很大的星球&＃xff0c;他准备建造N个国家和无数双向道路。N个国家很快建造好了&＃xff0c;用1..N编号&＃xff0c;但是他发现道路实在太多了&＃xff0c;他要一条条建简直是不可能的&＃xff01;于是他以如下方式建造道路&＃xff1a;(a,b),(c,d)表示&＃xff0c;对于任意两个国家x,y&＃xff0c;如果a<&＃61;x<&＃61;b,c<&＃61;y<&＃61;d&＃xff0c;那么在xy之间建造一条道路。Seter保证一条道路不会修建两次&＃xff0c;也保证不会有一个国家与自己之间有道路。
Seter好不容易建好了所有道路&＃xff0c;他现在在位于P号的首都。Seter想知道P号国家到任意一个国家最少需要经过几条道路。当然&＃xff0c;Seter保证P号国家能到任意一个国家。
注意&＃xff1a;可能有重边

Input

第一行三个数N,M,P。N<&＃61;500000,M<&＃61;100000。
后M行&＃xff0c;每行4个数A&＃xff0c;B&＃xff0c;C&＃xff0c;D。1<&＃61;A<&＃61;B<&＃61;N,1<&＃61;C<&＃61;D<&＃61;N。

Output

N行&＃xff0c;第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

知识点&＃xff1a;线段树建边优化

首先有一个朴素的建边方式&＃xff08;其实一点也不朴素&＃xff0c;我不会。。。其实是我太弱了&＃xff09;就是对于a~b到c~d我们新建虚拟节点p1,p2p1,p2&＃xff0c; a~b到p1p1连边权为0的&＃xff0c;然后p1p1到p2p2连边权为1的&＃xff0c;p2p2到c~d连边权为0的&＃xff0c;然后反过来再建一遍。这样的话时间和空间的复杂度是O(mn2)O(mn2)不可以接受。
这个时候有一种神奇的操作叫做线段树建边优化。
考虑由于每次建边都是一整段区间&＃xff0c;由此联想到线段树的区间修改&＃xff0c;构造性地建线段树A和线段树B&＃xff0c;分别表示线段树的出和入。操作如下&＃xff1a;

1. A树每个节点向父亲连边&＃xff0c;B树每个节点向儿子连边。边权为零。
2. 每个B树的叶子节点向对应的A树的叶子节点连边。
3. 对于a~b连向c~d&＃xff0c;在A树上找到a~b对应的区间u1,u2……unu1,u2……un&＃xff0c;将其连向虚拟节点p1p1&＃xff0c;边权为0
4. 虚拟节点p1p1到虚拟节点p2p2连上边权为1的边
5. 在B树上找到c~d对应的区间v1,v2……vnv1,v2……vn从p2p2连到这些区间&＃xff0c;边权为0

出线段树上的叶子节点对应的就是图上的真实节点。
然后跑一遍Dij堆优化即可。正确性。。。自己yy吧。因为每一条路径都代表了一种实际上的建边方式&＃xff0c;可以自己画图。
空间复杂度&＃xff1a;线段树节点是线性O(n)O(n)的&＃xff0c;每一次连边最多连lognlogn个区间&＃xff0c;一共连m次&＃xff0c;所以总复杂度是O(mlogn&＃43;n)O(mlogn&＃43;n)时间复杂度一样样的。
但实际上是O(玄学)因为常数爆炸

代码

跑的速度和空间大小都是中等&＃xff0c;模板题。

/**************************************************************Problem: 3073User: 2014lvzelongLanguage: C&＃43;&＃43;Result: AcceptedTime:9560 msMemory:340696 kb
****************************************************************/#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N &＃61; 4400000;
const int M &＃61; 21000000;
const int inf &＃61; 0x3f3f3f3f;
int read() {char ch &＃61; getchar(); int x &＃61; 0, f &＃61; 1;while(ch <&＃39;0&＃39; || ch > &＃39;9&＃39;) {if(ch &＃61;&＃61; &＃39;-&＃39;) f &＃61; -1; ch &＃61; getchar();}while(ch >&＃61; &＃39;0&＃39; && ch <&＃61; &＃39;9&＃39;) {x &＃61; (x <<1) &＃43; (x <<3) &＃43; ch - &＃39;0&＃39;; ch &＃61; getchar();}return x * f;
}
int pre[N], to[M], nxt[M], w[M], ls[N], rs[N], pos[N], dis[N], sz, top, ra, rb, n, m, s;
bool vis[N];
void add(int u, int v, int ww &＃61; 0) {to[&＃43;&＃43;top] &＃61; v; nxt[top] &＃61; pre[u]; pre[u] &＃61; top; w[top] &＃61; ww;}
struct data {int a, b;data(int aa &＃61; 0, int bb &＃61; 0) : a(aa), b(bb) {}bool operator <(data a) const {return b > a.b;}
};void Build(int &p, int L, int R, bool flag) {if(!p) p &＃61; &＃43;&＃43;sz;if(L &＃61;&＃61; R) {if(flag) pos[L] &＃61; sz; return;}int mid &＃61; L &＃43; R >> 1;Build(ls[p], L, mid, flag); Build(rs[p], mid &＃43; 1, R, flag);if(flag) add(ls[p], p), add(rs[p], p);else add(p, ls[p]), add(p, rs[p]);
}
void Add(int pa, int pb, int L, int R) {if(L &＃61;&＃61; R) {add(pb, pa); return;}int mid &＃61; L &＃43; R >> 1;Add(ls[pa], ls[pb], L, mid); Add(rs[pa], rs[pb], mid &＃43; 1, R);
}
void Update(int p, int L, int R, int st, int ed, int c, bool flag) {if(L &＃61;&＃61; st && ed &＃61;&＃61; R) {if(flag) add(p, c, 0);else add(c, p, 0);return ;}int mid &＃61; L &＃43; R >> 1;if(st <&＃61; mid) Update(ls[p], L, mid, st, min(mid, ed), c, flag);if(ed > mid) Update(rs[p], mid &＃43; 1, R, max(st, mid &＃43; 1), ed, c, flag);
}
void Link(int a, int b, int c, int d) {Update(ra, 1, n, a, b, &＃43;&＃43;sz, 1); add(sz, sz &＃43; 1, 1); Update(rb, 1, n, c, d, &＃43;&＃43;sz, 0);
}void Dij() {for(int i &＃61; 1;i <&＃61; sz; &＃43;&＃43;i) dis[i] &＃61; inf;priority_queueq;dis[pos[s]] &＃61; 0; q.push(data(pos[s], 0));while(!q.empty()) {int u &＃61; q.top().a; q.pop();if(vis[u]) continue;vis[u] &＃61; true;for(int i &＃61; pre[u]; i; i &＃61; nxt[i]) if(!vis[to[i]] && dis[to[i]] > dis[u] &＃43; w[i]) {dis[to[i]] &＃61; dis[u] &＃43; w[i];q.push(data(to[i], dis[to[i]]));}}
}int main() {n &＃61; read(); m &＃61; read(); s &＃61; read();Build(ra, 1, n, 1); Build(rb, 1, n, 0); Add(ra, rb, 1, n);for(int i &＃61; 1;i <&＃61; m; &＃43;&＃43;i) {int a &＃61; read(), b &＃61; read(), c &＃61; read(), d &＃61; read();Link(a, b, c, d); Link(c, d, a, b);}Dij();for(int i &＃61; 1;i <&＃61; n; &＃43;&＃43;i) printf("%d\n", dis[pos[i]]);return 0;
}