作者stimim (qqaa)
看板Prob_Solve
标题Re: [问题] ZeroJudge-c216
时间Tue Apr 2 23:17:02 2019
※ 引述《GYLin (Lynx)》之铭言：
: 大致策略:
: 1. 把途中所有累积加值都模100000, 原因很明显
: 2. 当需要计算Sum[L,R]时, 其值为"不考虑爆掉的原本加总"扣掉100000*(区间内爆掉人数)
: 爆掉人数为: 区间内的Ai个数, 其值加上目前累积加值会超过100000的人们
: 要计算爆掉人数, 只要维护一个 Map[i][j] 就可以,
: Map[i][j] 就是 阵列 1~i, 加上高度 j 会爆掉的人数,
: 若开普通阵列可能需要 100000*100000 的大小,
: 但实际上出现的询问只会有 10^6 种,
: 所以先把询问全部存起来後, 再针对会出现的询问求出爆掉人数,
: 再回去把存起来的询问解决即可.
另一种可以 online 的作法(不用预处理询问)
在每次的询问，
假设不会爆掉，我们只要知道原始的 aL + ... + aR 再加上 K * (R - L + 1) 就是
答案。这个部份只要先算出原始 a_i 的前缀和就可以做到。
而每爆掉一个，答案就需要减掉 10^5，
因此我们想知道 aL ~ aR 中高度不超过 10^5 - K 的有几个。
假设我们有一个 binary search tree, 里面的点是 {i | ai <= 10^5 - K}
那我们可以在 O(lg n) 的时间知道 |{i | ai <= 10^5 - K} ∩{L...R}|
问题是我们要做出 10^5 个 BST，这样好像会 OOM 或 TLE
再想一下会发现：
BST[0] = empty tree
BST[i] = BST[i - 1] + {j | aj == i}
也就是从 BST[0] 到 BST[10^5] ，只会有 n 个 insert
如果我们做 copy on write 的话，我们可以让每次的 insert 都只多用 O(lg n) 的空间，
时间也还是 O(lg n)
於是，我们有：
time complexity of pre-processing: O(n lg n)
space complexity: O(n lg n)
Time complexity of each query: O(lg n) + O(1) (BST query + prefix sum)
Overall time complexity: O(m lg n + n lg n)
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 104.132.150.77
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1554218224.A.1C7.html
1F：推 oToToT: 不可能只要静态前缀和吧，他不是是要算修改後的和减掉修改 04/02 23:28
2F：→ oToToT: 後会爆掉的人数乘以十万 04/02 23:28
3F：→ stimim: 有静态前缀和K就可以算出不考虑爆的答案，BST算有几个爆掉 04/02 23:32
4F：→ stimim: 基本上和 GYLin 的想法是一样的，不过预处理的时候不需要 04/02 23:33
5F：→ stimim: 知道询问会有什麽东西 04/02 23:33
改了一下文章，希望会清楚一点
※ 编辑: stimim (104.132.150.77), 04/02/2019 23:41:19
6F：推 GYLin: 持久化线段树? 一开始也想用这个 不过太久没刻(资结苦手 04/02 23:59
7F：推 oToToT: 喔喔www我一直看成题目是区间加K,查区间和 04/03 00:35
8F：→ stimim: 我是用 persist BST, 要用 persist segment tree 也可以 04/03 11:15
9F：推 fatcat8127: 感谢大大提供的想法。我实作离线线段树或是主席树的 04/05 01:59
10F：→ fatcat8127: 在线查询，记忆体耗量都超过10MB，但是有看到记忆体 04/05 01:59
11F：→ fatcat8127: 落在3mb的，想问说做法也是一样的吗? 04/05 01:59
12F：推 GYLin: 可以用BIT 应该会省一点 04/05 13:31
13F：推 fatcat8127: BIT要怎麽处理区间查询？虽然他可以累计1~H之间的个数 04/05 14:47
14F：推 oToToT: 题目不是可以转成区间<=X的数有几个，那再考虑把询问离线 04/06 00:57
15F：→ oToToT: 并且拆成[1,R]<=X的有几个-[1,L]<=X的有几个，接下来再对 04/06 00:58
16F：→ oToToT: 这种询问从小到大排序，就可以用BIT计算了 04/06 00:59
17F：推 fatcat8127: 感谢oT大大的说明，我以为BIT可以实现在线查询，如果 04/06 11:23
18F：→ fatcat8127: 是离线，记忆体都耗在储存查询...还是不知道2.5mb做 04/06 11:23
19F：→ fatcat8127: 法@@ 04/06 11:23