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 2777(線段樹)

1

#include <stdio.h>
2

#include <memory.h>
3

4

const long max = 200001 ;
5

6

struct NODE
7

{
8

int color ;
9

int start ;
10

int end ;
11

struct NODE *leftc ;
12

struct NODE *rightc ;
13

14

void BuildSTree( int s, int e ) ;
15

void Insert( int s, int e, int col ) ;
16

void CountColor( int s, int e ) ;
17

};
18

19

NODE STree[max] ;
20

NODE *root ;
21

22

long num = 0 ;
23

bool Color[31] ;
24

25

void NODE::BuildSTree( int s , int e )
26

{
27

start = s ;
28

end = e ;
29

color = 1 ;
30

31

if ( s == e )
32

{
33

leftc = NULL ;
34

rightc = NULL ;
35

return ;
36

}
37

38

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

40

leftc = &STree[num++] ;
41

rightc = &STree[num++] ;
42

43

leftc->BuildSTree( s , mid ) ;
44

rightc->BuildSTree( mid + 1 , e ) ;
45

}
46

47

void NODE::Insert( int s , int e , int col )
48

{
49

if ( col == color )
50

{
51

return ;
52

}
53

if ( s == start && e == end )
54

{
55

color = col ;
56

return ;
57

}
58

if ( color > 0 )
59

{
60

leftc->color = color ;
61

rightc->color = color ;
62

}
63

int mid = ( start + end ) >> 1 ;
64

65

color = -1 ;
66

67

if ( mid >= e )
68

{
69

leftc->Insert( s, e, col ) ;
70

}
71

else if ( mid < s ) {
72

rightc->Insert( s, e, col ) ;
73

}
74

else {
75

leftc->Insert( s, mid, col ) ;
76

rightc->Insert( mid + 1, e, col ) ;
77

}
78

}
79

80

void Paint( int s , int e , int col )
81

{
82

root->Insert( s, e, col ) ;
83

}
84

85

void NODE::CountColor( int s, int e )
86

{
87

if ( color > 0 )
88

{
89

Color[color] = true ;
90

return ;
91

}
92

93

int mid = ( start + end ) >> 1 ;
94

95

if ( mid >= e )
96

{
97

leftc->CountColor( s, e ) ;
98

}
99

else if ( mid < s ) {
100

rightc->CountColor( s, e ) ;
101

}
102

else {
103

leftc->CountColor( s, mid ) ;
104

rightc->CountColor( mid + 1, e ) ;
105

}
106

}
107

108

int main()
109

{
110

long L , T , O , s , e ;
111

char cmd ;
112

int col ;
113

114

scanf("%ld %ld %ld\n", &L, &T, &O) ;
115

116

root = &STree[num++] ;
117

root->BuildSTree( 1 , 100000 ) ;
118

119

for ( int i = 0 ; i < O ; i++ )
120

{
121

scanf("%c", &cmd) ;
122

123

while ( cmd != 'C' && cmd != 'P' )
124

{
125

scanf("%c", &cmd) ;
126

}
127

128

if ( cmd == 'C' )
129

{
130

scanf("%ld %ld %d", &s, &e, &col) ;
131

132

if ( s > e )
133

{
134

long t = s ; s = e ; e = t ;
135

}
136

137

Paint( s, e, col ) ;
138

}
139

else if ( cmd == 'P' )
140

{
141

scanf("%ld %ld", &s, &e) ;
142

143

if ( s > e )
144

{
145

long t = s ; s = e ; e = t ;
146

}
147

148

root->CountColor( s, e ) ;
149

150

int ans = 0 ;
151

152

for ( int j = 1 ; j < 31 ; j++ )
153

{
154

if ( Color[j] )
155

{
156

ans++ ;
157

}
158

}
159

160

memset(Color, 0, sizeof(Color)) ;
161

162

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

}
164

}
165

166

return 0 ;
167

}
168

posted on 2008-11-17 22:55 巫閱讀(262) 評論(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 管理

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