gzwzm06

C++博客 :: 首頁(yè) :: 新隨筆 :: 聯(lián)系 :: 聚合

:: 管理 ::

1 隨筆 :: 52 文章 :: 17 評(píng)論 :: 0 Trackbacks

<

2011年5月

>

日

一

二

三

四

五

六

24

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

常用鏈接

留言簿(3)

隨筆檔案

2009年5月 (1)

文章分類(lèi)

文章檔案

搜索

最新評(píng)論

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

POJ 3368 Frequent values (線(xiàn)段樹(shù))

1

#include <cstdio>
2

3

const int SIZE = 100101;
4

void BuildSTree(const int& id, const int& s, const int& e)
22

{
23

stree[id].m_start = s;
24

stree[id].m_end = e;
25

stree[id].m_srcS = 100000;
26

stree[id].m_srcE = 0;
27

stree[id].m_num = 0;
28

stree[id].m_equal = false;
29

30

if ( s == e )
31

{
32

stree[id].m_equal = true;
33

return ;
34

}
35

36

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

38

stree[id].m_left = gIndex++;
39

BuildSTree( stree[id].m_left, s, mid );
40

41

stree[id].m_right = gIndex++;
42

BuildSTree( stree[id].m_right, mid + 1, e );
43

}
44

45

void Insert(const int& id, const int&p, const int& num)
46

{
47

if ( stree[id].m_num < num )
48

stree[id].m_num = num;
49

50

if ( stree[id].m_srcS > srcS )
51

stree[id].m_srcS = srcS;
52

if ( stree[id].m_srcE < srcE )
53

stree[id].m_srcE = srcE;
54

55

if ( stree[id].m_start == p && stree[id].m_end == p )
56

{
57

stree[id].m_srcS = srcS;
58

stree[id].m_srcE = srcE;
59

return;
60

}
61

62

int mid = (stree[id].m_start + stree[id].m_end) >> 1;
63

64

if ( mid >= p )
65

{
66

Insert( stree[id].m_left, p, num );
67

}
68

else
69

{
70

Insert( stree[id].m_right, p, num );
71

}
72

}
73

74

void Query(const int& id, const int& s, const int& e)
75

{
76

if ( stree[id].m_srcS == s && stree[id].m_srcE == e )
77

{
78

if ( rs_n < stree[id].m_num )
79

rs_n = stree[id].m_num;
80

return;
81

}
82

if ( stree[id].m_equal && stree[id].m_srcS <= s && stree[id].m_srcE >= e )
83

{
84

if ( rs_n < e - s + 1 )
85

int l = stree[id].m_left, r = stree[id].m_right;
90

91

if ( stree[l].m_srcE >= e )
92

{
93

Query( l, s, e );
94

}
95

else if ( s > stree[r].m_srcS )
96

Query( l, s, stree[l].m_srcE );
101

Query( r, stree[r].m_srcS, e );
102

}
103

}
104

105

int arr[SIZE], N, Q;
106

108

112

while ( scanf("%d", &N) && N != 0 )
113

118

for ( i = 1; i <= N; ++i )
119

{
120

scanf("%d", &arr[i]);
121

}
122

123

srcS = 1;
124

p = 1;
125

for ( i = 2; i <= N; ++i )
126

{
127

if ( arr[i] != arr[i - 1] )
128

BuildSTree( 0, 1, p );
140

141

for ( i = 1; i <= p; ++i )
142

{
143

srcS = rs[i][0];
144

srcE = rs[i][1];
145

Insert( 0, i, srcE - srcS + 1 );
146

}
147

148

for ( i = 0; i < Q; ++i )
149

{
150

151

scanf("%d %d", &srcS, &srcE);
152

rs_n = 0;
153

154

if ( srcS == srcE )
155

{
156

printf("1\n");
157

}
158

else if ( srcS == srcE - 1 )
159

{
160

if ( arr[srcS] == arr[srcE] )
161

Query( 0, srcS, srcE );
167

printf("%d\n", rs_n);
168

171

174

http://acm.pku.edu.cn/JudgeOnline/problem?id=3368
代碼惡心了。。。

posted on 2009-05-08 07:59 巫閱讀(162) 評(píng)論(0) 編輯收藏引用所屬分類(lèi): 數(shù)據(jù)結(jié)構(gòu)

只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。


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

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

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