//參考:
http://hi.baidu.com/fandywang_jlu/blog/item/505b40f4c864bddff3d38574.html
http://blog.csdn.net/ldyhot/archive/2008/10/29/3173535.aspx

     摘要: //離散化+線段樹(以下轉)感謝它幫助我理解離散化假如不離散化，那線段樹的上界是10^7，假如建一個那么大的線段樹的話。。。必然MLE。于是要考慮離散化。離散化的目的就是要將線段的長度適當的縮小，但不破壞題意。比如：------   （1，6）------------ （1，12 ）像這樣這樣的兩條線段，可以把它們看作：-- （1，2）--- （ 1，3 ）這樣，縮短了線段的長...  閱讀全文      摘要: //貢獻6個WA//先建樹，然后插入，總計，mixcolor表示該段不止一色   1#include<iostream>  2#define MAX 100000  3#define mixcolor -1  4using namespace s...  閱讀全文 //Sparse Table(ST)，動態規劃，<O(N logN), O(1)>

 1void rmq_init()
 2{
 3    int i,j;
 4    for(j=1;j<=n;j++) mx[j][0]=d[j];
 5    int m=floor(log((double)n)/log(2.0));
 6    for(i=1;i<=m;i++)
 7        for(j=0;j+(1<<(i-1))<=n;j++)
 8            mx[j][i]=max(mx[j][i-1],mx[j+(1<<(i-1))][i-1]);
 9}
10
11int rmq(int l,int r)
12{
13    int m=floor(log((double)(r-l+1))/log(2.0));
14    int a=max(mx[l][m],mx[r-(1<<m)+1][m]);
15    return a;  
16}
17
18

RMQ介紹：http://baike.baidu.com/view/1536346.htm
摘自某人文章:http://blog.sina.com.cn/s/blog_4d88e9860100cthl.html
pku2352-Stars 區間統計,使用線段樹,也可用樹狀數組
pku2528-Mayor's posters 區間涂色問題,使用離散化+線段樹
pku1151-Atlantis 求矩形并的面積,用線段樹+離散化+掃描線
pku1177-picture 求矩形并的周長,用線段樹+離散化+掃描線
pku3264-Balanced Lineup RMQ問題,求區間最大最小值的差
pku3368-Frequent values 轉化為RMQ問題求解

好久沒寫過算法了，添一個吧，寫一個線段樹的入門知識，比較大眾化。

上次在湖大，其中的一道題數據很強，我試了好多種優化都TLE，相信只能用線段樹才能過。回來之后暗暗又學了一次線段樹，想想好像是第三次學了，像網絡流一樣每學一次都有新的體會。

把問題簡化一下：

在自然數，且所有的數不大于30000的范圍內討論一個問題：現在已知n條線段，把端點依次輸入告訴你，然后有m個詢問，每個詢問輸入一個點，要求這個點在多少條線段上出現過；

最基本的解法當然就是讀一個點，就把所有線段比一下，看看在不在線段中；

每次詢問都要把n條線段查一次，那么m次詢問，就要運算m*n次，復雜度就是O(m*n)

這道題m和n都是30000，那么計算量達到了10^9；而計算機1秒的計算量大約是10^8的數量級，所以這種方法無論怎么優化都是超時

-----

因為n條線段是固定的，所以某種程度上說每次都把n條線段查一遍有大量的重復和浪費；

線段樹就是可以解決這類問題的數據結構

舉例說明：已知線段[2,5] [4,6] [0,7]；求點2,4,7分別出現了多少次

在[0,7]區間上建立一棵滿二叉樹：（為了和已知線段區別，用【】表示線段樹中的線段）

                                               【0,7】

                                      /                                  \

                     【0,3】                                           【4,7】

                  /               \                                    /                \

       【0,1】             【2,3】                 【4,5】               【6,7】

         /      \                 /      \                       /      \                      /      \

【0,0】 【1,1】【2,2】 【3,3】   【4,4】 【5,5】 【6,6】 【7,7】

每個節點用結構體：

struct line

{

      int left,right;//左端點、右端點

      int n;//記錄這條線段出現了多少次，默認為0

}a[16];

和堆類似，滿二叉樹的性質決定a[i]的左兒子是a[2*i]、右兒子是a[2*i+1];

然后對于已知的線段依次進行插入操作：

從樹根開始調用遞歸函數insert

三條已知線段插入過程：

[2,5]

--[2,5]與【0,7】比較，分成兩部分：[2,3]插到左兒子【0,3】，[4,5]插到右兒子【4,7】

--[2,3]與【0,3】比較，插到右兒子【2,3】；[4,5]和【4,7】比較，插到左兒子【4,5】

--[2,3]與【2,3】匹配，【2,3】記錄+1；[4,5]與【4,5】匹配，【4,5】記錄+1

[4,6]

--[4,6]與【0,7】比較，插到右兒子【4,7】

--[4,6]與【4,7】比較，分成兩部分，[4,5]插到左兒子【4,5】；[6,6]插到右兒子【6,7】

--[4,5]與【4,5】匹配，【4,5】記錄+1；[6,6]與【6,7】比較，插到左兒子【6,6】

--[6,6]與【6,6】匹配，【6,6】記錄+1

[0,7]

--[0,7]與【0,7】匹配，【0,7】記錄+1

插入過程結束，線段樹上的記錄如下（紅色數字為每條線段的記錄n）：

                                               【0,7】

                                                    1

                                  /                                      \

                     【0,3】                                           【4,7】

                         0                                                     0

                 /                 \                                     /                 \

       【0,1】                 【2,3】                【4,5】                【6,7】

            0                           1                           2                          0

          /    \                      /      \                     /     \                    /      \

【0,0】 【1,1】 【2,2】 【3,3】 【4,4】 【5,5】 【6,6】 【7,7】

     0            0             0            0             0            0                 1           0

詢問操作和插入操作類似，也是遞歸過程，略

2——依次把【0,7】 【0,3】 【2,3】 【2,2】的記錄n加起來，結果為2

4——依次把【0,7】 【4,7】 【4,5】 【4,4】的記錄n加起來，結果為3

7——依次把【0,7】 【4,7】 【6,7】 【7,7】的記錄n加起來，結果為1

不管是插入操作還是查詢操作，每次操作的執行次數僅為樹的深度——logN

建樹有n次插入操作，n*logN，一次查詢要logN，m次就是m*logN；總共復雜度O(n+m)*logN，這道題N不超過30000，logN約等于14，所以計算量在10^5～10^6之間，比普通方法快了1000倍；

這道題是線段樹最基本的操作，只用到了插入和查找；刪除操作和插入類似，擴展功能的還有測度、連續段數等等，在N數據范圍很大的時候，依然可以用離散化的方法建樹。

湖大的那道題目繞了個小彎子，alpc12有詳細的題目和解題報告，有興趣的話可以看看http://www.shnenglu.com/sicheng/archive/2008/01/09/40791.html

線段樹的經典題目就是poj1177的picturehttp://acm.pku.edu.cn/JudgeOnline/problem?id=1177

(a + b)mod c = (a mod c + b mod c) mod c
(a + b)%c = (a % c + b % c) % c
mod相當于除法，效率低

Bellman-Ford 算法及其優化

Bellman-Ford算法與另一個非常著名的Dijkstra算法一樣，用于求解單源點最短路徑問題。Bellman-ford算法除了可求解邊權均非負的問題外，還可以解決存在負權邊的問題（意義是什么，好好思考），而Dijkstra算法只能處理邊權非負的問題，因此 Bellman-Ford算法的適用面要廣泛一些。但是，原始的Bellman-Ford算法時間復雜度為 O（VE）,比Dijkstra算法的時間復雜度高，所以常常被眾多的大學算法教科書所忽略，就連經典的《算法導論》也只介紹了基本的Bellman-Ford算法，在國內常見的基本信息學奧賽教材中也均未提及，因此該算法的知名度與被掌握度都不如Dijkstra算法。事實上，有多種形式的Bellman-Ford算法的優化實現。這些優化實現在時間效率上得到相當提升，例如近一兩年被熱捧的SPFA（Shortest-Path Faster Algoithm 更快的最短路徑算法）算法的時間效率甚至由于Dijkstra算法，因此成為信息學奧賽選手經常討論的話題。然而，限于資料匱乏，有關Bellman-Ford算法的諸多問題常常困擾奧賽選手。如：該算法值得掌握么？怎樣用編程語言具體實現？有哪些優化？與SPFA算法有關系么？本文試圖對Bellman-Ford算法做一個比較全面的介紹。給出幾種實現程序，從理論和實測兩方面分析他們的時間復雜度，供大家在備戰省選和后續的noi時參考。

Bellman-Ford算法思想

Bellman-Ford算法能在更普遍的情況下（存在負權邊）解決單源點最短路徑問題。對于給定的帶權（有向或無向）圖 G=（V,E），其源點為s，加權函數 w是 邊集 E 的映射。對圖G運行Bellman-Ford算法的結果是一個布爾值，表明圖中是否存在著一個從源點s可達的負權回路。若不存在這樣的回路，算法將給出從源點s到 圖G的任意頂點v的最短路徑d[v]。

Bellman-Ford算法流程分為三個階段：

（1）    初始化：將除源點外的所有頂點的最短距離估計值 d[v] ←+∞, d[s] ←0;

（2）    迭代求解：反復對邊集E中的每條邊進行松弛操作，使得頂點集V中的每個頂點v的最短距離估計值逐步逼近其最短距離；（運行|v|-1次）

（3）    檢驗負權回路：判斷邊集E中的每一條邊的兩個端點是否收斂。如果存在未收斂的頂點，則算法返回false，表明問題無解；否則算法返回true，并且從源點可達的頂點v的最短距離保存在 d[v]中。

算法描述如下：

Bellman-Ford(G,w,s) ：boolean   //圖G ，邊集 函數 w ，s為源點

1        for each vertex v ∈ V（G） do        //初始化 1階段

2            d[v] ←+∞

3        d[s] ←0;                             //1階段結束

4        for i=1 to |v|-1 do               //2階段開始，雙重循環。

5           for each edge（u,v） ∈E(G) do //邊集數組要用到，窮舉每條邊。

6              If d[v]> d[u]+ w(u,v) then      //松弛判斷

7                 d[v]=d[u]+w(u,v)               //松弛操作   2階段結束

8        for each edge（u,v） ∈E(G) do

9            If d[v]> d[u]+ w(u,v) then

10            Exit false

11    Exit true

下面給出描述性證明：

   首先指出，圖的任意一條最短路徑既不能包含負權回路，也不會包含正權回路，因此它最多包含|v|-1條邊。

   其次，從源點s可達的所有頂點如果 存在最短路徑，則這些最短路徑構成一個以s為根的最短路徑樹。Bellman-Ford算法的迭代松弛操作，實際上就是按頂點距離s的層次，逐層生成這棵最短路徑樹的過程。

在對每條邊進行1遍松弛的時候，生成了從s出發，層次至多為1的那些樹枝。也就是說，找到了與s至多有1條邊相聯的那些頂點的最短路徑；對每條邊進行第2遍松弛的時候，生成了第2層次的樹枝，就是說找到了經過2條邊相連的那些頂點的最短路徑……。因為最短路徑最多只包含|v|-1 條邊，所以，只需要循環|v|-1 次。

每實施一次松弛操作，最短路徑樹上就會有一層頂點達到其最短距離，此后這層頂點的最短距離值就會一直保持不變，不再受后續松弛操作的影響。（但是，每次還要判斷松弛，這里浪費了大量的時間，怎么優化？單純的優化是否可行？）

如果沒有負權回路，由于最短路徑樹的高度最多只能是|v|-1，所以最多經過|v|-1遍松弛操作后，所有從s可達的頂點必將求出最短距離。如果 d[v]仍保持 +∞，則表明從s到v不可達。

如果有負權回路，那么第 |v|-1 遍松弛操作仍然會成功，這時，負權回路上的頂點不會收斂。

 

 

 

例如對于上圖，邊上方框中的數字代表權值，頂點A,B,C之間存在負權回路。S是源點，頂點中數字表示運行Bellman-Ford算法后各點的最短距離估計值。

此時d[a]的值為1，大于d[c]+w(c,a)的值-2，由此d[a]可以松弛為-2，然后d[b]又可以松弛為-5,d[c]又可以松弛為-7.下一個周期，d[a]又可以更新為更小的值，這個過程永遠不會終止。因此，在迭代求解最短路徑階段結束后，可以通過檢驗邊集E的每條邊(u,v)是否滿足關系式 d[v]> d[u]+ w(u,v) 來判斷是否存在負權回路。

//直接向后加，不知道怎么證明，悲劇...