coreBugZJ

此 blog 已棄。

EOJ 2458 Frequent values

/*
2

EOJ 2458 Frequent values
3

----問題描述：
6

You are given a sequence of n integers a1 , a2 ,

, an in non-decreasing order.
8

In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n).
9

For each query, determine the most frequent value among the integers ai ,

, aj.
10

----輸入：
13

The input consists of several test cases.
15

Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000).
16

The next line contains n integers a1 ,

, an (-100000 ≤ ai ≤ 100000, for each i ∈ {1,

, n}) separated by spaces.
17

You can assume that for each i ∈ {1,

, n-1}: ai ≤ ai+1.
18

The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n),
19

which indicate the boundary indices for the query.
20

The last test case is followed by a line containing a single 0.
22

----輸出：
25

For each query, print one line with one integer:
27

The number of occurrences of the most frequent value within the given range.
28

----樣例輸入：
31

10 3
33

-1 -1 1 1 1 1 3 10 10 10
34

2 3
35

1 10
36

5 10
37

0
38

----樣例輸出：
41

1
43

4
44

3
45

----分析：
48

方案一，
50

線段樹，樹中結點保存
51

左端，右端，最頻的實際數值；
52

左端，右端，最頻的數值的頻度；
53

左右端點。
54

方案二，
56

RMQ ST 算法。
57

*/
59

/**********************************************
63

版本二：
64

AC 1019MS
65

RMQ ST 算法。
66

*/
67

#include <iostream>
70

#include <cstdio>
71

#include <cmath>
72

#include <algorithm>
73

using namespace std;
75

const int L = 100009;
77

template<class T = int, unsigned int L = 100009, unsigned int L2 = 18>
79

class RmqSt
80

{
81

public :
82

int init( T a[], int le, int ri) {
83

int i, j, k;
84

fr[ le ] = le;
86

for ( i = le+1; i < ri; ++i ) {
87

if ( a[ i ] == a[ i - 1 ] ) {
88

fr[ i ] = fr[ i - 1 ];
89

}
90

else {
91

fr[ i ] = i;
92

}
93

}
94

la[ ri-1 ] = ri;
96

for ( i = ri-1; i > le; --i ) {
97

if ( a[ i ] == a[ i - 1 ] ) {
98

la[ i - 1 ] = la[ i ];
99

}
100

else {
101

la[ i - 1 ] = i;
102

}
103

}
104

105

for ( i = le; i < ri; ++i ) {
106

f[ i ][ 0 ] = 1;
107

}
108

k = 1;
109

while ( (1 << k) <= ri - le ) {
110

for ( i = ri - (1<<k); i >= le; --i ) {
111

j = i + (1<<(k-1));
112

f[ i ][ k ] = max(f[i][k-1], f[j][k-1]);
113

if ( a[ j ] == a[ j - 1 ] ) {
114

f[ i ][ k ] = max(f[i][k], min(la[j], i+(1<<k)) - max(fr[j], i));
115

}
116

}
117

++k;
118

}
119

return 0;
120

}
121

int query(int le, int ri) {
122

int k = (int)(floor(log(((double)(ri)) - le) / log(2.0)));
123

int j = ri - (1<<k);
124

int q = max(f[le][k], f[j][k]);
125

if ( (le < j) && (a[j] == a[j-1]) ) {
126

q = max(q, min(la[j], ri) - max(fr[j], le));
127

}
128

j = le + (1<<k);
129

if ( (j < ri) && (a[j] == a[j-1])) {
130

q = max(q, min(la[j], ri) - max(fr[j], le));
131

}
132

return q;
133

}
134

135

private :
136

T f[ L ][ L2 ];
137

int fr[ L ], la[ L ]; // fr[i] 表示 a[i] 第一次出現的位置，la 類似，表最后
138

};
139

140

RmqSt<int> prob;
141

int a[ L ];
142

int n;
143

144

int main() {
145

int i, q, le, ri;
146

while ( (1 == scanf("%d", &n)) && (0 < n) ) {
147

scanf("%d", &q);
148

for ( i = 1; i <= n; ++i ) {
149

scanf("%d", a+i);
150

}
151

prob.init(a, 1, n+1);
152

while ( q-- > 0 ) {
153

scanf("%d%d", &le, &ri);
154

printf("%d\n", prob.query(le, ri+1));
155

}
156

}
157

return 0;
158

}
159

160

161

162

/**********************************************
163

版本一：
164

AC 941 MS
165

線段樹。
166

*/
167

/*
168

#include <iostream>
169

#include <cstdio>
170

#include <algorithm>
171

172

using namespace std;
173

174

const int L = 100009;
175

176

template<class T = int, unsigned int L = 100009>
177

class SegTree
178

{
179

public :
180

int init(T a[], int le, int ri) {
181

this->a = a;
182

return this->init(1, le, ri);
183

}
184

int query(int le, int ri) {
185

this->le = le;
186

this->ri = ri;
187

Node qr;
188

return this->query(1, qr);
189

}
190

191

private :
192

struct Node
193

{
194

T lv, rv, mv; // 左端，右端，最頻值
195

int ln, rn, mn; // 左端，右端，最頻頻
196

int le, ri; // 左右端點
197

};
198

Node node[ L * 3 ];
199

200

T *a;
201

int le, ri;
202

203

int init(int idx, int le, int ri) {
204

if ( le + 1 == ri ) {
205

node[ idx ].le = le;
206

node[ idx ].ri = ri;
207

node[ idx ].lv = node[ idx ].rv = node[ idx ].mv = a[ le ];
208

node[ idx ].ln = node[ idx ].rn = node[ idx ].mn = 1;
209

return 1;
210

}
211

int lc = (idx<<1);
212

int rc = (idx<<1)|1;
213

init(lc, le, (le+ri)>>1);
214

init(rc, (le+ri)>>1, ri );
215

216

node[ idx ].le = le;
217

node[ idx ].ri = ri;
218

node[ idx ].lv = node[ lc ].lv;
219

node[ idx ].ln = node[ lc ].ln;
220

node[ idx ].rv = node[ rc ].rv;
221

node[ idx ].rn = node[ rc ].rn;
222

if ( node[ lc ].mn < node[ rc ].mn ) {
223

node[ idx ].mn = node[ rc ].mn;
224

node[ idx ].mv = node[ rc ].mv;
225

}
226

else {
227

node[ idx ].mn = node[ lc ].mn;
228

node[ idx ].mv = node[ lc ].mv;
229

}
230

231

if ( node[ lc ].rv == node[ rc ].lv ) {
232

if ( node[ lc ].lv == node[ lc ].rv ) {
233

node[ idx ].ln += node[ rc ].ln;
234

}
235

if ( node[ rc ].lv == node[ rc ].rv ) {
236

node[ idx ].rn += node[ lc ].rn;
237

}
238

if ( node[ idx ].mn < node[ lc ].rn + node[ rc ].ln ) {
239

node[ idx ].mn = node[ lc ].rn + node[ rc ].ln;
240

node[ idx ].mv = node[ lc ].rv;
241

}
242

}
243

return 1;
244

}
245

int query(int idx, Node &qr) {
246

if ( (this->le <= node[idx].le) && (node[idx].ri <= this->ri) ) {
247

qr = node[ idx ];
248

return qr.mn;
249

}
250

if ( (this->le >= node[idx].ri) || (this->ri <= node[idx].le) ) {
251

qr.le = -1;
252

qr.ri = -2;
253

qr.ln = qr.rn = qr.mn = 0;
254

qr.lv = qr.rv = qr.mv = 0;
255

return 0;
256

}
257

int lc = (idx<<1);
258

int rc = (idx<<1)|1;
259

int mid = (node[idx].le + node[idx].ri)>>1;
260

261

if ( (this->le < mid) && ( this->ri > mid) ) {
262

Node qle, qri;
263

query(lc, qle);
264

query(rc, qri);
265

266

qr.le = le;
267

qr.ri = ri;
268

qr.lv = qle.lv;
269

qr.ln = qle.ln;
270

qr.rv = qri.rv;
271

qr.rn = qri.rn;
272

if ( qle.mn < qri.mn ) {
273

qr.mn = qri.mn;
274

qr.mv = qri.mv;
275

}
276

else {
277

qr.mn = qle.mn;
278

qr.mv = qle.mv;
279

}
280

281

if ( qle.rv == qri.lv ) {
282

if ( qle.lv == qle.rv ) {
283

qr.ln += qri.ln;
284

}
285

if ( qri.lv == qri.rv ) {
286

qr.rn += qle.rn;
287

}
288

if ( qr.mn < qle.rn + qri.ln ) {
289

qr.mn = qle.rn + qri.ln;
290

qr.mv = qle.rv;
291

}
292

}
293

294

return qr.mn;
295

}
296

if ( this->ri > mid ) {
297

return query(rc, qr);
298

}
299

return query(lc, qr);
300

}
301

};
302

303

SegTree<int> prob;
304

int a[ L ];
305

int n;
306

307

int main() {
308

int i, q, le, ri;
309

while ( (1 == scanf("%d", &n)) && (0 < n) ) {
310

scanf("%d", &q);
311

for ( i = 1; i <= n; ++i ) {
312

scanf("%d", a+i);
313

}
314

prob.init(a, 1, n+1);
315

while ( q-- > 0 ) {
316

scanf("%d%d", &le, &ri);
317

printf("%d\n", prob.query(le, ri+1));
318

}
319

}
320

return 0;
321

}
322

*/
323

posted on 2012-04-22 22:48 coreBugZJ 閱讀(671) 評論(0) 編輯收藏引用所屬分類: ACM 、Algorithm 、DataStructure 、課內作業

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


相關文章: 微軟2014實習生及秋令營技術類職位在線測試 TopCoder SRM 593 DIV2 第三題生成全排列的非回溯方法（TopCoder SRM 591 DIV 2） A* 算法求解八數碼問題，POJ 1077 Eight POJ 1067 取石子游戲 POJ 2068 Nim POJ 2975 Nim POJ 3696 The Luckiest number POJ 3604 Professor Ben EOJ 1117 剩余定理

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

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

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術

開源

科學

數學

圖形圖像

文化

問題（練習＆有趣）

資源

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜

EOJ 2458 Frequent values