gzwzm06

C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理 ::

1 隨筆 :: 52 文章 :: 17 評論 :: 0 Trackbacks

<

2010年5月

>

日

一

二

三

四

五

六

25

26

27

28

29

30

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

常用鏈接

留言簿(3)

隨筆檔案

2009年5月 (1)

文章分類

文章檔案

搜索

最新評論

1.?re: Pku 2774--Long Long Message（后綴樹）
求教大牛，那個Lt屬性是記錄什么的
--dereky
2.?re: POJ 2481(樹狀數組)
@gzwzm06
哦，實在是不好意思，確實是那個地方，現在過了，謝謝了啊。
--Klion
3.?re: POJ 2481(樹狀數組)
你再檢查下，cc[j].m_e == cc[j].m_e這個條件肯定是真的，沒有意義吧
--gzwzm06
4.?re: POJ 2481(樹狀數組)
@gzwzm06
兩個相同一起比較也就是兩個區間是一樣的，起點和終點是相同的，和您的第80行比較的應該是一樣的吧？
--Klion
5.?re: POJ 2481(樹狀數組)
評論內容較長,點擊標題查看
--gzwzm06

Pku 2828(線段樹)

利用線段樹倒推

1

#include <cstdio>
2

3

const int MAXN = 200100 ;
4

5

struct NODE
6

{
7

int start , end ;
8

int sum ;
9

NODE *leftc ;
10

NODE *rightc ;
11

12

void Build( const int& s, const int& e ) ;
13

void Insert( int pos ) ;
14

} ;
15

16

NODE *root , SegTree[MAXN * 2] ;
17

int g_Pos , mark , array[MAXN][2] , seq[MAXN] ;
18

19

void NODE::Build( const int& s, const int& e )
20

{
21

int mid = ( s + e ) >> 1 ;
22

start = s , end = e ;
23

sum = mid - s + 1 ; //記錄此點左邊有多少個人
24

25

if ( s == e )
26

{
27

leftc = rightc = NULL ;
28

return ;
29

}
30

31

leftc = &SegTree[g_Pos++] ;
32

rightc = &SegTree[g_Pos++] ;
33

34

leftc->Build( s , mid ) ;
35

rightc->Build( mid + 1 , e ) ;
36

}
37

38

void NODE::Insert( int pos )
39

{
40

if ( start == end )
41

{
42

mark = start ; //記錄最終位置
43

return ;
44

}
45

if ( sum < pos ) //左邊人數比指定位置小，則插到右孩子節點
46

{
47

pos -= sum ;
48

rightc->Insert( pos ) ;
49

}
50

else if ( sum >= pos ) //否則插到左孩子節點
51

{
52

sum-- ; //那么左邊的人數空位減1
53

leftc->Insert( pos ) ;
54

}
55

}
56

57

void Init()
58

{
59

root = &SegTree[0] ;
60

g_Pos = 1 ;
61

}
62

63

int main()
64

{
65

// freopen("in.txt", "r", stdin) ;
66

67

int n , i ;
68

69

while ( scanf("%d", &n) != EOF )
70

{
71

Init() ;
72

73

for ( i = 0 ; i < n ; ++i )
74

{
75

scanf("%d %d", &array[i][0], &array[i][1]) ;
76

}
77

78

root->Build( 1, n ) ;
79

80

for ( i = n - 1 ; i >= 0 ; --i )
81

{
82

root->Insert( array[i][0] + 1 ) ;
83

84

seq[mark] = array[i][1] ;
85

}
86

87

for ( i = 1 ; i < n ; ++i )
88

printf("%d ", seq[i]) ;
89

printf("%d\n", seq[i]) ;
90

}
91

return 0 ;
92

}

posted on 2008-11-18 10:12 巫閱讀(491) 評論(0) 編輯收藏引用所屬分類: 數據結構

只有注冊用戶登錄后才能發表評論。


相關文章: 7th GDCPC Problem H(DFS序 + 線段樹) POJ 3368 (RMQ) POJ 3368 Frequent values (線段樹) POJ 2060--Taxi Cab Scheme(最小路徑覆蓋) Atomic Nucleus Investigation (線段樹 n = 100000) POJ 2481(樹狀數組) POJ 2481 Cows(線段樹) POJ 3667 Hotel(模擬) Pku 2828(線段樹) Pku 2777(線段樹)

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品