作者flere (人間失格)
站內Prob_Solve
標題[問題] 可能和segment tree相關的問題
時間Tue Jan 10 13:29:19 2012
(當初以為很簡單沒看到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
1F：→ firejox:你是怎麼做segment tree的?? 01/10 18:31
很一般的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)
2F：推 DJWS:好像是平均分成sqrt(N)段，每段長度sqrt(N)，然後遞迴下去 01/16 14:20
3F：推 DJWS:樓上當我沒說 應該是切成小段分別處理 不用遞迴 01/16 14:23
4F：→ flere:> <可以稍微解釋一下嗎??有點不知如何下手> < 01/17 01:14
5F：推 DJWS:每1024格當作一個單位 更新時只需更新一個單位 01/17 11:28
6F：→ DJWS:查詢時也以單位為主 不滿一單位的元素就用暴搜 01/17 11:30
7F：→ DJWS:查詢的速度快慢 取決於一個單位有多少格 取很多格的話 01/17 11:31
8F：→ DJWS:單位雖少但是暴搜就很久 取太少格的話 暴搜雖快但是單位多 01/17 11:31
9F：→ DJWS:一般來說取 sqrt(N) 格當作一單位會是最快的 01/17 11:32
先感謝一下> <
那假設有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)
10F：推 suhorng:比如你把每個元素都先紀錄他在那格中是第幾大的 01/17 16:55
11F：→ suhorng:注意到你改變某個原素食 要更新的紀錄只有該格中的元素 01/17 16:55
12F：→ suhorng:注意你這樣存的話 查詢的時候只要分被"完整覆蓋"的區塊 01/17 16:57
13F：→ suhorng:以及沒有"完整覆蓋"的區塊分開算 01/17 16:57
14F：→ suhorng:沒有被完整覆蓋的區塊最多只有兩個 直接用迴圈算 01/17 16:57
15F：→ suhorng:被完整覆蓋的就查你之前做好的紀錄 01/17 16:57
16F：→ flere:感謝> <我試試看> < 01/17 17:58
17F：→ bleed1979:演算法一樣，不過我是用sort搭配binary search。 01/17 23:48
18F：→ flere:恩....我也是想用sort+BS....可是我大概要打很久> < 01/17 23:55
19F：推 DJWS:可以用STL呀~ #include<algorithm>之後有sort和lower_bound 01/18 14:05
20F：→ DJWS:如果是C語言的話可以用qsort和bsearch 可以免敲很多程式碼~ 01/18 14:06
※ 編輯: flere 來自: 140.114.200.13 (01/18 16:27)
21F：→ flere:我手動敲完了> <只是目前還沒過OAQ 01/18 16:28
怪了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)
22F：推 DJWS:這樣應該就夠快了呀！ 該不會是endl之類的問題吧...? 01/18 18:06
我也覺得應該夠了說> <
※ 編輯: flere 來自: 140.114.200.13 (01/18 18:24)
※ 編輯: flere 來自: 140.114.200.13 (01/18 18:24)