gzwzm06

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

:: 管理 ::

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

<

2025年11月

>

日

一

二

三

四

五

六

26

27

28

29

30

31

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

1

2

3

4

5

6

常用鏈接

留言簿(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

POJ 2528(離散化 + 線段樹)

1

#include <cstdio>
2

#include <memory.h>
3

#include <algorithm>
4

using namespace std ;
5

6

const int MAXN = 41001 ;
7

const int SIZE = 10001 ;
8

9

struct NODE
10

{
11

int m_flag ;
12

int m_start, m_end ;
13

NODE *leftc , *rightc ;
14

15

void BuildTree(const int& s, const int& e) ;
16

void Insert(const int& s, const int& e, const int& k) ;
17

void FindInTree() ;
18

} ;
19

20

struct WALL
21

{
22

int m_pos ;
23

int m_value ;
24

25

bool const operator < ( WALL& b )const
26

{
27

if ( m_value < b.m_value )
28

return true ;
29

return false ;
30

}
31

}wall[SIZE * 2] ;
32

33

NODE *root ;
34

NODE Stree[MAXN] ;
35

int g_Pos ;
36

int ans , arrSize ;
37

int gFlag[SIZE] ;
38

39

void NODE::BuildTree(const int& s, const int& e)
40

{
41

m_flag = 0 ;
42

m_start = s, m_end = e ;
43

if ( e == s )
44

{
45

leftc = rightc = NULL ;
46

return ;
47

}
48

49

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

51

leftc = &Stree[g_Pos++] ;
52

rightc = &Stree[g_Pos++] ;
53

54

leftc->BuildTree(s, mid) ;
55

rightc->BuildTree(mid + 1, e) ;
56

57

}
58

59

void NODE::Insert(const int& s, const int& e, const int& k)
60

{
61

if ( m_start == m_end )
62

{
63

m_flag = k ;
64

return ;
65

}
66

if ( m_start == s && m_end == e )
67

{
68

m_flag = k ;
69

return ;
70

}
71

if ( m_flag > 0 ){
72

rightc->m_flag = m_flag ;
73

leftc->m_flag = m_flag ;
74

m_flag = -1 ;
75

}
76

else if ( m_flag == 0 )
77

m_flag = k ;
78

79

int mid = ( m_start + m_end ) >> 1 ;
80

81

if ( mid >= e )
82

{
83

leftc->Insert( s, e, k ) ;
84

}
85

else if ( mid < s ) //就這里，寫多了一個等號，導致WA十幾次
86

{
87

rightc->Insert( s, e, k ) ;
88

}
89

else {
90

leftc->Insert( s, mid, k ) ;
91

rightc->Insert( mid + 1, e, k ) ;
92

}
93

}
94

95

void NODE::FindInTree()
96

{
97

if ( m_flag >= 0 )
98

{
99

if ( gFlag[m_flag] == 0 )
100

{
101

gFlag[m_flag] = 1 ;
102

ans++ ;
103

}
104

return ; //不需要訪問到葉節點
105

}
106

107

if ( m_flag == -1 )
108

{
109

leftc->FindInTree() ;
110

rightc->FindInTree() ;
111

}
112

113

}
114

115

void Init()
116

{
117

ans = 0 ;
118

g_Pos = 1 ;
119

root = &Stree[0] ;
120

121

root->leftc = root->rightc = NULL ;
122

memset(gFlag, 0, sizeof(gFlag)) ;
123

}
124

int main()
125

{
126

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

128

int T , n , i , size , x , y ;
129

int pos[SIZE][2] ;
130

scanf("%d", &T) ;
131

132

while ( T-- )
133

{
134

Init() ;
135

size = 0 ;
136

137

scanf("%d", &n) ;
138

139

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

{
141

scanf("%d %d", &pos[i][0], &pos[i][1]) ;
142

wall[size].m_pos = i ;
143

wall[size++].m_value = pos[i][0] ;
144

wall[size].m_pos = -i ;
145

wall[size++].m_value = pos[i][1] ;
146

}
147

//離散化
148

sort(wall, wall + size) ;
149

150

x = 1 ;
151

if ( wall[0].m_pos < 0 )
152

pos[-wall[0].m_pos][1] = 1 ;
153

else
154

pos[wall[0].m_pos][0] = 1 ;
155

156

for ( i = 1 ; i < size ; ++i )
157

{
158

if ( wall[i].m_value != wall[i - 1].m_value )
159

{
160

x++ ;
161

}
162

if ( wall[i].m_pos > 0 )
163

pos[wall[i].m_pos][0] = x ;
164

else
165

pos[-wall[i].m_pos][1] = x ;
166

167

}
168

169

arrSize = x ;
170

//線段樹
171

root->BuildTree( 1, arrSize ) ;
172

173

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

{
175

x = pos[i][0] ;
176

y = pos[i][1] ;
177

root->Insert( x, y, i ) ;
178

}
179

180

root->FindInTree() ;
181

182

printf("%d\n", ans) ;
183

}
184

return 0 ;
185

}
186

187

188

189

posted on 2008-11-16 20:58 巫閱讀(458) 評論(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 管理

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