[問題] 可能和segment tree相關的問題

看板Prob_Solve作者 (人間失格)時間12年前 (2012/01/10 13:29), 編輯推噓6(6推 0噓 16→)
留言22則, 5人參與, 最新討論串1/1
(當初以為很簡單沒看到problem size.....QQ 簡單敘述題意如下 : 給你一個N的array-A N<=10^5 然後給你M個指令 M<=2*10^4 每個指令有4個數字 L,R,V,P 要找出從A[L]~A[R]中比V小的數字有幾個,假設num個 然後帶一個他給定的公式tmp = u*num/(R-L+1) 取整數,u一開始題目會給 然後把A[P] 改成剛剛算出來的答案 -> A[P]=tmp 我用segment tree的方法去做 不過有些細節的地方無法克服 仍然是TLE 請問有什麼好方法嗎?? 謝謝^^ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.114.200.13
→
01/10 18:31, , 1F
你是怎麼做segment tree的??
01/10 18:31, 1F
很一般的segment tree> <不太熟 我在每個node同時儲存他底下的min,max為多少 然後去搜尋L,R區間的range 如果搜尋的一個range他的min比V還要大那就不搜尋下去 如果這個range的max比V小就整個range的數量都比V小 但是當大小平均分布時 有很大的機會仍然會到tree的底部 就有點....QQ了> < ※ 編輯: flere 來自: 140.114.200.13 (01/10 18:43)
推
01/16 14:20, , 2F
好像是平均分成sqrt(N)段，每段長度sqrt(N)，然後遞迴下去
01/16 14:20, 2F
推
01/16 14:23, , 3F
樓上當我沒說 應該是切成小段分別處理　不用遞迴
01/16 14:23, 3F
→
01/17 01:14, , 4F
> <可以稍微解釋一下嗎??有點不知如何下手> <
01/17 01:14, 4F
推
01/17 11:28, , 5F
每1024格當作一個單位 更新時只需更新一個單位
01/17 11:28, 5F
→
01/17 11:30, , 6F
查詢時也以單位為主 不滿一單位的元素就用暴搜
01/17 11:30, 6F
→
01/17 11:31, , 7F
查詢的速度快慢 取決於一個單位有多少格 取很多格的話
01/17 11:31, 7F
→
01/17 11:31, , 8F
單位雖少但是暴搜就很久 取太少格的話 暴搜雖快但是單位多
01/17 11:31, 8F
→
01/17 11:32, , 9F
一般來說取 sqrt(N) 格當作一單位會是最快的
01/17 11:32, 9F
先感謝一下> < 那假設有9個數字 2 4 6 8 1 3 5 7 0 分成3個單位好了 2 4 6 8 1 3 5 7 0 然後我要找第0格(數字2)到第6格(數字5)中,比7小的有幾個 有辦法用O(1)的時間就找到一個單位(這邊是3個元素)裡面的答案是多少嗎?? ※ 編輯: flere 來自: 140.114.200.13 (01/17 16:05)
推
01/17 16:55, , 10F
比如你把每個元素都先紀錄他在那格中是第幾大的
01/17 16:55, 10F
→
01/17 16:55, , 11F
注意到你改變某個原素食 要更新的紀錄只有該格中的元素
01/17 16:55, 11F
→
01/17 16:57, , 12F
注意你這樣存的話 查詢的時候只要分被"完整覆蓋"的區塊
01/17 16:57, 12F
→
01/17 16:57, , 13F
以及沒有"完整覆蓋"的區塊分開算
01/17 16:57, 13F
→
01/17 16:57, , 14F
沒有被完整覆蓋的區塊最多只有兩個 直接用迴圈算
01/17 16:57, 14F
→
01/17 16:57, , 15F
被完整覆蓋的就查你之前做好的紀錄
01/17 16:57, 15F
→
01/17 17:58, , 16F
感謝> <我試試看> <
01/17 17:58, 16F
→
01/17 23:48, , 17F
演算法一樣，不過我是用sort搭配binary search。
01/17 23:48, 17F
→
01/17 23:55, , 18F
恩....我也是想用sort+BS....可是我大概要打很久> <
01/17 23:55, 18F
推
01/18 14:05, , 19F
可以用STL呀~ #include<algorithm>之後有sort和lower_bound
01/18 14:05, 19F
→
01/18 14:06, , 20F
如果是C語言的話可以用qsort和bsearch 可以免敲很多程式碼~
01/18 14:06, 20F
※ 編輯: flere 來自: 140.114.200.13 (01/18 16:27)
→
01/18 16:28, , 21F
我手動敲完了> <只是目前還沒過OAQ
01/18 16:28, 21F
怪了OAQ 我把N平分成sqrt(N)份,每份sqrt(N)個 存兩份,一份是有分段sort好的,一份是原始順序 然後指令的起始跟最後判斷有沒有在同一段裡 去做一下這一段或兩段的暴力法 然後用sort好的去做binary search(被起始跟最後夾住的段落 找到到底有多少個數字符合後 在原始的那裏面修改 然後再花sqrt(N)*2的時間修改sort那一部分 最後把原始的那一array印出來 結果會TLE耶O口Q 有哪個地方可以再加速的嗎?? ※ 編輯: flere 來自: 140.114.200.13 (01/18 16:39)
推
01/18 18:06, , 22F
這樣應該就夠快了呀！　該不會是endl之類的問題吧...?
01/18 18:06, 22F
我也覺得應該夠了說> < ※ 編輯: flere 來自: 140.114.200.13 (01/18 18:24) ※ 編輯: flere 來自: 140.114.200.13 (01/18 18:24)
‣ 更多 flere 的文章
文章代碼(AID): #1F2yoq7U (Prob_Solve)