gzwzm06

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

:: 管理 ::

1 隨筆 :: 52 文章 :: 17 評論 :: 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)

文章分類

文章檔案

搜索

最新評論

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 3368 (RMQ)

1

#include <cstdio>
2

#include <cmath>
3

4

const int SIZE = 100101;
5

6

int arr[SIZE], N;
7

int cntFront[SIZE], cntBack[SIZE];
8

int Max[18][SIZE];
9

10

inline int GetMax(const int& a, const int& b)
11

{
12

return (a > b ? a : b);
13

}
14

15

void Init()
16

{
17

int i, cnt;
18

19

cntFront[1] = 1;
20

cnt = 1;
21

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

{
23

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

{
25

cnt = 1;
26

}
27

else {
28

cnt++;
29

}
30

cntFront[i] = cnt;
31

}
32

33

cntBack[N] = 1;
34

cnt = 1;
35

for ( i = N - 1; i > 0; --i )
36

{
37

if ( arr[i] != arr[i + 1] )
38

{
39

cnt = 1;
40

}
41

else
42

{
43

cnt++;
44

}
45

cntBack[i] = cnt;
46

}
47

}
48

49

void MakeRMQ()
50

{
51

int i, j;
52

53

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

{
55

Max[0][i] = cntFront[i];
56

}
57

58

for ( j = 1; (1 << j) <= N; ++j )
59

for ( i = 1; i + (1 << j) - 1 <= N; ++i )
60

{
61

Max[j][i] = GetMax( Max[j - 1][i], Max[j - 1][i + (1 << (j - 1))] );
62

}
63

}
64

65

inline int RMQ(const int& i, const int& j)
66

{
67

int k = (int)(log((double)(j - i + 1)) / log(2.0));
68

69

return GetMax( Max[k][i], Max[k][j - (1 << k) + 1] ) ;
70

}
71

72

int Query(int s, int e)
73

{
74

if ( s == e )
75

return 1;
76

else
77

{
78

int t, lv, rv;
79

80

lv = cntBack[s];
81

rv = cntFront[e];
82

83

if ( s + lv - 1 > e - rv + 1 )
84

{
85

return (e - s + 1);
86

}
87

88

t = GetMax( lv, rv );
89

90

s = s + lv;
91

e = e - rv;
92

93

if ( s < e )
94

{
95

t = GetMax( t, RMQ( s, e ) );
96

}
97

98

return t;
99

100

}
101

}
102

103

int main()
104

{
105

// freopen("1.txt", "r", stdin);
106

107

int i, s, e, Q;
108

109

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

{
111

scanf("%d", &Q);
112

113

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

{
115

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

}
117

118

Init();
119

MakeRMQ();
120

121

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

{
123

scanf("%d %d", &s, &e);
124

125

printf("%d\n", Query( s, e ));
126

127

}
128

129

}
130

131

return 0;
132

}

posted on 2009-05-08 08:00 巫閱讀(155) 評論(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 管理

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