質問編集履歴
3
追記
test
CHANGED
File without changes
|
test
CHANGED
@@ -265,3 +265,67 @@
|
|
265
265
|
}
|
266
266
|
|
267
267
|
```
|
268
|
+
|
269
|
+
|
270
|
+
|
271
|
+
## 追記
|
272
|
+
|
273
|
+
`query_inside()`内の
|
274
|
+
|
275
|
+
```C++
|
276
|
+
|
277
|
+
else if (l <= L && R <= r && _t_size / 2 <= now)
|
278
|
+
|
279
|
+
```
|
280
|
+
|
281
|
+
の条件`_t_size / 2 <= now`がTLEの要因になっているということですが、
|
282
|
+
|
283
|
+
この条件を削除すると、下記の例のように更新が上手く反映されない場合があると思うのですが、この場合どうすればよいのでしょうか。
|
284
|
+
|
285
|
+
|
286
|
+
|
287
|
+
```
|
288
|
+
|
289
|
+
[ 配列(_tree)/遅延評価用配列(_lazy_tree) ]
|
290
|
+
|
291
|
+
/*--------------------------------------------*/
|
292
|
+
|
293
|
+
例:
|
294
|
+
|
295
|
+
[ 2/- ]
|
296
|
+
|
297
|
+
[ 3/- ] [ 2/- ]
|
298
|
+
|
299
|
+
[ 4/- ] [ 3/- ] [ 2/- ] [ 5/- ]
|
300
|
+
|
301
|
+
[4/-] [5/-] [3/-] [6/-] [2/-] [3/-] [8/-] [5/-]
|
302
|
+
|
303
|
+
↓
|
304
|
+
|
305
|
+
区間[4,5)を1に更新
|
306
|
+
|
307
|
+
[ 2/- ]
|
308
|
+
|
309
|
+
[ 3/- ] [ 2/- ]
|
310
|
+
|
311
|
+
[ 4/- ] [ 3/- ] [ 2/- ] [ 5/- ]
|
312
|
+
|
313
|
+
[4/-] [5/-] [3/-] [6/-] <2/1> [3/-] [8/-] [5/-]
|
314
|
+
|
315
|
+
↓
|
316
|
+
|
317
|
+
区間[4,8)の最小値を求める
|
318
|
+
|
319
|
+
< 2/- >
|
320
|
+
|
321
|
+
< 3/- > < 2/- >←これ以上query関数は下に進まない
|
322
|
+
|
323
|
+
[ 4/- ] [ 3/- ] [ 2/- ] [ 5/- ]
|
324
|
+
|
325
|
+
[4/-] [5/-] [3/-] [6/-] [2/1] [3/-] [8/-] [5/-]
|
326
|
+
|
327
|
+
↓
|
328
|
+
|
329
|
+
(正しい結果は1だが)2が返される
|
330
|
+
|
331
|
+
```
|
2
初心者アイコン設定変更
test
CHANGED
File without changes
|
test
CHANGED
File without changes
|
1
タイトルを一部変更
test
CHANGED
@@ -1 +1 @@
|
|
1
|
-
AOJの RMQ and RUQ の問題でTLEが出てしまう
|
1
|
+
AOJの RMQ and RUQ の問題でTLEが出てしまう(競プロ)
|
test
CHANGED
File without changes
|