//參考:
http://hi.baidu.com/fandywang_jlu/blog/item/505b40f4c864bddff3d38574.html
http://blog.csdn.net/ldyhot/archive/2008/10/29/3173535.aspx
1
/**//*
2
線段樹+DP
3 出題者的簡單解題報告：把環從一個地方，切斷拉成一條直線，
4 用線段樹記錄當前區間的非空最大子列和當前區間的非空最小
5 子列。如果環上的數都是正整數，答案是：環上數的總和－根
6 結點的非空最小子列；否則，答案是：max{根結點的非空最大
7 子列, 環上數的總和－根結點的非空最小子列}，每次問答的
8 復雜度是O(logN)。
9
*/
10
11#include<iostream>
12using namespace std;
13#define MAXN 100000
14#define MAXM 100000
15#define MAX 262145
16
17struct Node
18
{
19 int left;
20 int right;
21 int sum; //該區間 數的總和
22 int max,min; //該區間 最大子列和 與 最小子列和
23 int lmax,rmax; //該區間 從左端點開始的最大子列和 與 到右端點結束的最小子列和
24 int lmin,rmin; //該區間 從左端點開始的最小子列和 與 到右端點結束的最小子列和
25};
26
27Node segtree[MAX];
28int value[MAXN+1];
29//int vi;
30
31void update (int v)
32{
33 segtree[v].sum=segtree[2*v].sum+segtree[2*v+1].sum;
34 segtree[v].max=max(max(segtree[2*v].max,segtree[2*v+1].max),segtree[2*v].rmax+segtree[2*v+1].lmax);
35 segtree[v].min=min(min(segtree[2*v].min,segtree[2*v+1].min),segtree[2*v].rmin+segtree[2*v+1].lmin);
36 segtree[v].lmax=max(segtree[2*v].lmax, segtree[2*v].sum+segtree[2*v+1].lmax);
37 segtree[v].rmax=max(segtree[2*v+1].rmax, segtree[2*v+1].sum+segtree[2*v].rmax);
38 segtree[v].lmin=min(segtree[2*v].lmin,segtree[2*v].sum+segtree[2*v+1].lmin);
39 segtree[v].rmin=min(segtree[2*v+1].rmin,segtree[2*v+1].sum+segtree[2*v].rmin);
40}
41
42void build(int v,int l,int r)
43{
44 segtree[v].left=l;
45 segtree[v].right=r;
46
47 if(l == r )
48
{
49 segtree[v].sum =
50 segtree[v].max = segtree[v].min =
51 segtree[v].lmax = segtree[v].rmax =
52 segtree[v].lmin = segtree[v].rmin =value[l];
53
54
}else
55 {
56
57 int mid=(segtree[v].left+segtree[v].right)>>1;
58 build(2*v,l,mid);
59 build(2*v+1,mid+1,r);
60 update(v);
61 }
62
63}
64
65void insert(int v,int index)
66{
67 if( segtree[v].left == segtree[v].right && segtree[v].left == index)
68 {
69 segtree[v].sum =
70 segtree[v].max = segtree[v].min =
71 segtree[v].lmax = segtree[v].rmax =
72 segtree[v].lmin = segtree[v].rmin =value[index];
73 }else
74 {
75 int mid=(segtree[v].left+segtree[v].right)>>1;
76 if(index <= mid) insert(2*v,index);
77 else insert(2*v+1,index);
78 //if(index <= segtree[2*v].right) insert(2*v,index);
79 //else if(index >= segtree[2*v+1].left) insert(2*v+1,index);
80 update(v);
81 }
82}
83
84int main()
85{
86 int n,k,i,index;
87 scanf("%d",&n);
88 for(i=1;i<=n;i++)
89 scanf("%d",&value[i]);
90
91 build(1,1,n);
92
93 scanf("%d",&k);
94 while(k--)
95 {
96 scanf("%d",&index);
97 scanf("%d",&value[index]);
98 insert(1,index);
99 if(segtree[1].sum==segtree[1].max)
100 printf("%d\n",segtree[1].sum-segtree[1].min);
101 else printf("%d\n",max(segtree[1].max,segtree[1].sum-segtree[1].min));
102 }
103 return 0;
104}
105
posted @
2009-04-18 22:41 wyiu 閱讀(258) |
評論 (0) |
編輯 收藏
摘要: //離散化+線段樹(以下轉)感謝它幫助我理解離散化假如不離散化，那線段樹的上界是10^7，假如建一個那么大的線段樹的話。。。必然MLE。于是要考慮離散化。離散化的目的就是要將線段的長度適當的縮小，但不破壞題意。比如：------ （1，6）------------ （1，12 ）像這樣這樣的兩條線段，可以把它們看作：-- （1，2）--- （ 1，3 ）這樣，縮短了線段的長...
閱讀全文
posted @
2009-04-17 19:16 wyiu 閱讀(279) |
評論 (0) |
編輯 收藏
摘要: //貢獻6個WA//先建樹，然后插入，總計，mixcolor表示該段不止一色
1#include<iostream> 2#define MAX 100000 3#define mixcolor -1 4using namespace s...
閱讀全文
posted @
2009-04-16 17:01 wyiu 閱讀(331) |
評論 (1) |
編輯 收藏
//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
posted @
2009-04-14 00:40 wyiu 閱讀(191) |
評論 (0) |
編輯 收藏
pku2528-Mayor's posters 區間涂色問題,使用離散化+線段樹
pku1151-Atlantis 求矩形并的面積,用線段樹+離散化+掃描線
pku1177-picture 求矩形并的周長,用線段樹+離散化+掃描線
pku3264-Balanced Lineup RMQ問題,求區間最大最小值的差
pku3368-Frequent values 轉化為RMQ問題求解
posted @
2009-04-14 00:31 wyiu 閱讀(2009) |
評論 (0) |
編輯 收藏好久沒寫過算法了，添一個吧，寫一個線段樹的入門知識，比較大眾化。
上次在湖大，其中的一道題數據很強，我試了好多種優化都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
1void insert(int s,int t,int step)//要插入的線段的左端點和右端點、以及當前線段樹中的某條線段
2
3{
4
5 if (s==a[step].left && t==a[step].right)
6
7 {
8
9 a[step].n++;//插入的線段匹配則此條線段的記錄+1
10
11 return;//插入結束返回
12
13 }
14
15 if (a[step].left==a[step].right) return;//當前線段樹的線段沒有兒子，插入結束返回
16
17 int mid=(a[step].left+a[step].right)/2;
18
19 if (mid>=t) insert(s,t,step*2);//如果中點在t的右邊，則應該插入到左兒子
20
21 else if (mid<s) insert(s,t,step*2+1);//如果中點在s的左邊，則應該插入到右兒子
22
23 else//否則，中點一定在s和t之間，把待插線段分成兩半分別插到左右兒子里面
24
25 {
26
27 insert(s,mid,step*2);
28
29 insert(mid+1,t,step*2+1);
30
31 }
32
33}
34
35
三條已知線段插入過程：
[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
posted @
2009-04-14 00:26 wyiu 閱讀(215) |
評論 (0) |
編輯 收藏
(a + b)mod c = (a mod c + b mod c) mod c
(a + b)%c = (a % c + b % c) % c
mod相當于除法，效率低
posted @
2009-04-04 19:52 wyiu 閱讀(140) |
評論 (0) |
編輯 收藏 1#include <limits.h>
2#include <stdio.h>
3#include <stdlib.h>
4
5/**//* Let INFINITY be an integer value not likely to be
6 confused with a real weight, even a negative one. */
7#define INFINITY ((1 << 14)-1)
8
9typedef struct {
10 int source;
11 int dest;
12 int weight;
13} Edge;
14
15void BellmanFord(Edge edges[], int edgecount, int nodecount, int source)
16{
17 int *distance = (int*) malloc (nodecount * sizeof (*distance)); //int
18 int i, j;
19
20 for (i=0; i < nodecount; ++i)
21 distance[i] = INFINITY;
22 distance[source] = 0;
23
24 for (i=0; i < nodecount; ++i)
25 {
26 int somethingchanged = 0;
27 for (j=0; j < edgecount; ++j)
28 {
29 if (distance[edges[j].source] != INFINITY)
30 {
31 int new_distance = distance[edges[j].source] + edges[j].weight;
32 if (new_distance < distance[edges[j].dest])
33 {
34 distance[edges[j].dest] = new_distance;
35 somethingchanged = 1;
36 }
37 }
38 }
39 /**//* if one iteration had no effect, further iterations will have no effect either */
40 if (!somethingchanged) break;
41 }
42
43 for (i=0; i < edgecount; ++i)
44 {
45 if (distance[edges[i].dest] > distance[edges[i].source] + edges[i].weight)
46 {
47 puts("Negative edge weight cycles detected!");
48 free(distance);
49 return;
50 }
51 }
52
53 for (i=0; i < nodecount; ++i) {
54 printf("The shortest distance between nodes %d and %d is %d\n",
55 source, i, distance[i]);
56 }
57
58 free(distance);
59 return;
60}
61
62int main(void)
63{
64 /**//* This test case should produce the distances 2, 4, 7, -2, and 0. */
65 Edge edges[10] = {{0,1, 5}, {0,2, 8}, {0,3, -4}, {1,0, -2},
66 {2,1, -3}, {2,3, 9}, {3,1, 7}, {3,4, 2},
67 {4,0, 6}, {4,2, 7}};
68 BellmanFord(edges, 10, 5, 4);
69 return 0;
70}
71
posted @
2009-04-03 22:08 wyiu 閱讀(198) |
評論 (0) |
編輯 收藏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) 來判斷是否存在負權回路。
posted @
2009-04-03 21:50 wyiu 閱讀(269) |
評論 (0) |
編輯 收藏
//直接向后加，不知道怎么證明，悲劇...
1#include<iostream>
2using namespace std;
3int main()
4{
5 int n;
6 int i;
7 __int64 t=0;
8 scanf("%d",&n);
9 while(n!=0){
10 int *h=new int[n];
11 for(i=0;i<n;i++)
12 scanf("%I64d",&h[i]);
13 for(i=0;i<n;i++)
14 {
15 h[i+1]+=h[i];
16 if(h[i]>=0)
17 t+=h[i];
18 else t+=-h[i];
19 }
20 printf("%I64d\n",t);
21 t=0;
22 scanf("%d",&n);
23 }
24 return 0;
25}
posted @
2009-04-03 20:13 wyiu 閱讀(97) |
評論 (0) |
編輯 收藏