#24391: 45% 可以算AC了
a0976531005@gmail.com
(Terry ob)
學校
:
不指定學校
編號 : 100175
來源 : [27.247.99.71]
最後登入時間 ：
2023-08-26 22:41:36
c258. kevin 愛畫圓
| From: [59.115.204.132] |
發表日期
:
2021-02-12 01:02
#14 的 n 是 10^4
這題用 離散化+BIT 解
複雜度也要 O(nlogn)
4.5s 要跑 5*10^5 有點勉強
我用 python 是靠作弊直接撈答案才 AC 的
順便給不會解的人一些提示:
相離 = 沒有相交 = 在左邊或在中間或在右邊
判斷及計算的方法很多，可以自行歸納出可行的方式
BIT 即為 Binary Indexed Tree
不知道的話可以 google 查一下
可以拿來動態的將陣列前綴的某段 所有元素通通+x
也可以查詢某段前綴的總和，兩個操作時間都在 O(logn)
但是在建構的過程需要做離散化
因為輸入的數字範圍太大，所以要做一點轉化
類似將 4, 8, 7, 6, 3 轉成 1, 4, 3, 2, 0 這樣的動作
BIT 如何用在本題上，請自行意會
以上是我的不專業見解~~
#39920: Re: 45% 可以算AC了
cataholic.0000@gmail.com
(貓奴)
學校
:
高雄市立高雄高級工業職業學校
編號 : 192061
來源 : [163.32.89.161]
最後登入時間 ：
2024-04-02 10:25:34
c258. kevin 愛畫圓
| From: [101.136.48.51] |
發表日期
:
2024-04-12 14:46
#14 的 n 是 10^4
這題用 離散化+BIT 解
複雜度也要 O(nlogn)
4.5s 要跑 5*10^5 有點勉強
我用 python 是靠作弊直接撈答案才 AC 的
順便給不會解的人一些提示:
相離 = 沒有相交 = 在左邊或在中間或在右邊
判斷及計算的方法很多，可以自行歸納出可行的方式
BIT 即為 Binary Indexed Tree
不知道的話可以 google 查一下
可以拿來動態的將陣列前綴的某段 所有元素通通+x
也可以查詢某段前綴的總和，兩個操作時間都在 O(logn)
但是在建構的過程需要做離散化
因為輸入的數字範圍太大，所以要做一點轉化
類似將 4, 8, 7, 6, 3 轉成 1, 4, 3, 2, 0 這樣的動作
BIT 如何用在本題上，請自行意會
以上是我的不專業見解~~
大佬可以大概講解解題思路嗎？
拜託QAQ
ZeroJudge Forum