作者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)