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

7th GDCPC Problem H(DFS序 + 線段樹)

1

#include <cstdio>
2

3

const int SIZE = 100001;
4

const int INF = 10000000;
5

6

int N, arr_sc[SIZE], arr_order[SIZE], arr_index[SIZE], edge[SIZE][2], father[SIZE];
7

8

struct NODE
9

{
10

int m_v;
11

struct NODE* next;
12

}tree[SIZE], mem[SIZE * 2];
13

14

int index = 0, M = 0, tId = 1;
15

int gMax, gMin;
16

17

struct ITEM
18

{
19

int fst;
20

int last;
21

}arr_pos[SIZE];
22

23

struct STREE
24

{
25

int m_start;
26

int m_end;
27

28

int m_max;
29

int m_min;
30

int m_markMin;
31

int m_markMax;
32

33

int m_leftChild;
34

int m_rightChild;
35

}stree[SIZE * 2];
36

37

void Insert(const int& x, const int& y)
38

{
39

mem[index].m_v = y;
40

mem[index].next = tree[x].next;
41

tree[x].next = &mem[index];
42

index++;
43

44

mem[index].m_v = x;
45

mem[index].next = tree[y].next;
46

tree[y].next = &mem[index];
47

index++;
48

}
49

50

void DFS( const int &root, const int& fat )
51

{
52

NODE *ptr = tree[root].next;
53

54

arr_pos[root].fst = M;
55

arr_index[root] = M;
56

arr_order[M++] = root;
57

father[root] = fat;
58

59

while ( ptr )
60

{
61

if ( ptr->m_v != fat )
62

{
63

DFS( ptr->m_v, root );
64

}
65

ptr = ptr->next;
66

}
67

68

arr_pos[root].last = M - 1;
69

}
70

71

void Build(const int& id, const int& s, const int& e)
72

{
73

stree[id].m_start = s;
74

stree[id].m_end = e;
75

stree[id].m_max = 0;
76

stree[id].m_min = INF;
77

stree[id].m_markMax = -1;
78

stree[id].m_markMin = -1;
79

if ( s == e )
80

{
81

return;
82

}
83

84

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

86

stree[id].m_leftChild = tId++;
87

Build( stree[id].m_leftChild, s, mid );
88

89

stree[id].m_rightChild = tId++;
90

Build( stree[id].m_rightChild, mid + 1, e );
91

}
92

93

void InsertTree(const int& id, const int& p, const int& v)
94

{
95

if ( stree[id].m_max < v )
96

{
97

stree[id].m_max = v;
98

stree[id].m_markMax = arr_order[p];
99

}
100

if ( stree[id].m_min > v )
101

{
102

stree[id].m_min = v;
103

stree[id].m_markMin = arr_order[p];
104

}
105

106

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

{
108

return;
109

}
110

111

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

113

if ( mid >= p )
114

InsertTree( stree[id].m_leftChild, p, v );
115

else
116

InsertTree( stree[id].m_rightChild, p, v );
117

}
118

119

void Change( const int& id, const int& p, const int& v )
120

{
121

if ( stree[id].m_markMax == arr_order[p] )
122

{
123

stree[id].m_max = 0;
124

stree[id].m_markMax = -1;
125

}
126

if ( stree[id].m_markMin == arr_order[p] )
127

{
128

stree[id].m_min = INF;
129

stree[id].m_markMin = -1;
130

}
131

132

if ( stree[id].m_leftChild == p && stree[id].m_rightChild == p )
133

{
134

stree[id].m_max = stree[id].m_min = v;
135

stree[id].m_markMax = stree[id].m_markMin = arr_order[p];
136

return;
137

}
138

139

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

141

if ( mid >= p )
142

{
143

Change( stree[id].m_leftChild, p, v );
144

}
145

else {
146

Change( stree[id].m_rightChild, p, v );
147

}
148

149

int tf = stree[id].m_leftChild, tr = stree[id].m_rightChild, tmark, ts;
150

151

ts = (stree[tf].m_max > stree[tr].m_max ? stree[tf].m_max : stree[tr].m_max);
152

tmark = (stree[tf].m_max > stree[tr].m_max ? stree[tf].m_markMax : stree[tr].m_markMax );
153

if ( stree[id].m_max < ts )
154

{
155

stree[id].m_max = ts;
156

stree[id].m_markMax = tmark;
157

}
158

159

ts = (stree[tf].m_min < stree[tr].m_min ? stree[tf].m_min : stree[tr].m_min);
160

tmark = (stree[tf].m_min < stree[tr].m_min ? stree[tf].m_markMin : stree[tr].m_markMin );
161

if ( stree[id].m_min > ts )
162

{
163

stree[id].m_min = ts;
164

stree[id].m_markMin = tmark;
165

}
166

167

}
168

169

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

{
171

if ( s == stree[id].m_start && e == stree[id].m_end )
172

{
173

if ( gMax < stree[id].m_max )
174

gMax = stree[id].m_max;
175

if ( gMin > stree[id].m_min )
176

gMin = stree[id].m_min;
177

178

return;
179

}
180

181

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

183

if ( mid >= e )
184

{
185

Query( stree[id].m_leftChild, s, e );
186

}
187

else if ( mid < s )
188

{
189

Query( stree[id].m_rightChild, s, e );
190

}
191

else {
192

Query( stree[id].m_leftChild, s, mid );
193

Query( stree[id].m_rightChild, mid + 1, e );
194

}
195

}
196

197

void Solve(const int& ep)
198

{
199

gMax = 0;
200

gMin = INF;
201

202

__int64 ans;
203

int x, y, s, e;
204

205

x = edge[ep][0], y = edge[ep][1];
206

207

if ( y == father[x] )
208

y = x;
209

210

s = arr_pos[y].fst;
211

e = arr_pos[y].last;
212

213

if ( s == e )
214

{
215

gMax = gMin = arr_sc[y];
216

}
217

else {
218

Query( 0, s, e );
219

}
220

221

ans = gMax * gMin;
222

223

gMax = 0;
224

gMin = INF;
225

226

if ( s > 0 )
227

Query( 0, 0, s - 1 );
228

229

if ( e + 1 <= M - 1 )
230

Query( 0, e + 1, M - 1 );
231

232

ans += gMax * gMin;
233

234

printf("%I64d\n", ans);
235

236

}
237

238

void Init()
239

{
240

int i;
241

242

for ( i = 0; i < SIZE; ++i )
243

tree[i].next = NULL;
244

245

index = 0;
246

tId = 1;
247

M = 0;
248

}
249

250

int main()
251

{
252

freopen("1.txt", "r", stdin);
253

254

int cs;
255

int i, x, y, Q;
256

char cmd[10];
257

258

scanf("%d", &cs);
259

260

while ( cs-- )
261

{
262

scanf("%d %d", &N, &Q);
263

264

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

{
266

scanf("%d", &arr_sc[i]);
267

}
268

269

Init();
270

Build( 0, 0, N - 1 );
271

272

for ( i = 0; i < N - 1; ++i )
273

{
274

scanf("%d %d", &x, &y);
275

276

edge[i + 1][0] = x;
277

edge[i + 1][1] = y;
278

Insert( x, y );
279

}
280

281

father[1] = -1;
282

DFS( 1, -1 );
283

284

for ( i = 0; i < M; ++i )
285

{
286

int t = arr_order[i];
287

InsertTree( 0, i, arr_sc[t] );
288

}
289

290

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

{
292

scanf("%s", cmd);
293

294

if ( cmd[0] == 'Q' )
295

{
296

scanf("%d", &x);
297

298

Solve( x );
299

}
300

else if ( cmd[0] == 'C' )
301

{
302

scanf("%d %d", &x, &y);
303

arr_sc[x] = y;
304

Change( 0, arr_index[x], y );
305

}
306

}
307

}
308

309

return 0;
310

}
311

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

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