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

[flere (人間失格)]

(當初以為很簡單沒看到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
→ firejox:你是怎麼做segment tree的??
很一般的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)
推 DJWS:好像是平均分成sqrt(N)段，每段長度sqrt(N)，然後遞迴下去
推 DJWS:樓上當我沒說  應該是切成小段分別處理　不用遞迴
→ flere:> <可以稍微解釋一下嗎??有點不知如何下手> <
推 DJWS:每1024格當作一個單位  更新時只需更新一個單位
→ DJWS:查詢時也以單位為主  不滿一單位的元素就用暴搜
→ DJWS:查詢的速度快慢  取決於一個單位有多少格  取很多格的話
→ DJWS:單位雖少但是暴搜就很久  取太少格的話  暴搜雖快但是單位多
→ DJWS:一般來說取 sqrt(N) 格當作一單位會是最快的
先感謝一下> <

那假設有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)
推 suhorng:比如你把每個元素都先紀錄他在那格中是第幾大的
→ suhorng:注意到你改變某個原素食 要更新的紀錄只有該格中的元素
→ suhorng:注意你這樣存的話 查詢的時候只要分被"完整覆蓋"的區塊
→ suhorng:以及沒有"完整覆蓋"的區塊分開算
→ suhorng:沒有被完整覆蓋的區塊最多只有兩個 直接用迴圈算
→ suhorng:被完整覆蓋的就查你之前做好的紀錄
→ flere:感謝> <我試試看> <
→ bleed1979:演算法一樣，不過我是用sort搭配binary search。
→ flere:恩....我也是想用sort+BS....可是我大概要打很久> <
推 DJWS:可以用STL呀~ #include<algorithm>之後有sort和lower_bound
→ DJWS:如果是C語言的話可以用qsort和bsearch  可以免敲很多程式碼~
※ 編輯: flere           來自: 140.114.200.13       (01/18 16:27)
→ flere:我手動敲完了> <只是目前還沒過OAQ
怪了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)
推 DJWS:這樣應該就夠快了呀！　該不會是endl之類的問題吧...?
我也覺得應該夠了說> <

※ 編輯: flere           來自: 140.114.200.13       (01/18 18:24)
※ 編輯: flere           來自: 140.114.200.13       (01/18 18:24)