AC. 梦想

frank_c1

[BZOJ 2874] 训练士兵

发布于2017年03月29日 | 暂无评论 | 319阅读 | 主席树,线段树

题意简述

有一个n \times m的矩阵A,初始值均为0

要求先进行k次修改操作,再回答q个询问。

修改操作选定一个子矩阵加上一个数。询问操作要求回答一个子矩形的和。

答案保证不超过2 ^ {64}。询问强制在线。

1 \le n, m \le 10 ^ 8, 1 \le t \le 40000, 1 \le q \le 100000

算法讨论

模拟赛的题。早上考虑了一下,突然发现是一道挺小清新的数据结构题,于是记录一波。

首先考虑对修改差分,差分之后拆成四个单点修改。考虑如何统计答案。设B_{p,q}(p,q)的差分标记值。则此时矩阵的实际值就是

A_{i,j} = \sum_{p=1} ^ {i} \sum_{q=1} ^ {j} {B_{p,q}}

而我们要求一个子矩形的和,首先可以转化为查询4个包含点(1,1)的子矩形的和。

考虑包含点(1,1)的子矩形的和怎么求。即

C_{n,m} = \sum_{i=1} ^ {n} \sum_{j=1} ^ {m} \sum_{p=1} ^ {i} \sum_{q=1} ^ {j} {B_{p,q}}

考虑每个非零的B_{p,q}对答案的贡献,它对所有i \ge pj \ge q(i,j)产生贡献。

于是有

C_{n,m} = \sum_{i=1} ^ {n} \sum_{j=1} ^ {m} {B_{i,j} (n-i+1)(m-j+1)} =  \sum_{i=1} ^ {n} \sum_{j=1} ^ {m} {B_{i,j} ((n+1)(m+1) - (n+1) j - (m+1) i + ij)}

分成四类标记分别统计即可。(其实上次某道题目已经推过一遍了TAT 再推一遍纯属刷下存在感……

这个时候如果n,m小的话就可以二维树状数组维护了。

而这里n,m很大,但是注意到询问都在修改后面。这个条件十分有用,几乎可以说是完全离线了。

不妨考虑统计标记的过程。其实就是一个二维数点。二维线段树的话显然没有把握好离线这个条件。我们可以考虑把点离散化并排序,建主席树。线段树键值是y坐标,时间轴就是x轴。每次询问在主席树上查一下就可以了。这样的话修改和询问的复杂度都比较优了。

时间复杂度O((k+q) \log k),空间复杂度O(k \log k)