F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 3592 >> 这题标算复杂度是多少?
save_code @ 2018-08-16 04:45:05
[ Quote ] [ Edit ] [ Delete ] 1#
我想到了一个 N*SQRT(N)的分块算法
save_code @ 2018-08-16 04:45:49
[ Quote ] [ Edit ] [ Delete ] 2#
可以通过 离线预处理 排序的手段 扔掉LOG
save_code @ 2018-08-16 04:55:37
[ Quote ] [ Edit ] [ Delete ] 3#
发个题解练习下我的语文水平:

把所有的点 先按照 x排序,然后 sqrt(n) 一组分块,每个 分块按照y排序,树状数组 记录 sum以及 max...

然后就是查询 , 添加 一条线段, 将 线段所在 x区间[lx,rx] 上方的所有点标记取反 每个查询 [lx,rx] 所在的sqrt(n)个分块,对于整个分块 二分查询 这条线段上方的点,然后 将上方的点的标记取反,每个分块 得到一个取反区间, 对于分块内只有部分查询
直接暴力出离散点 (也可以当成一个区间)
对于每个分块 处理处所有的取反区间 然后合并(最多S个)
最后查询所有取反区间内的 值就行了
save_code @ 2018-08-16 04:55:53
[ Quote ] [ Edit ] [ Delete ] 4#
不知道有木有 log(n)的算法
sumix173 @ 2018-10-04 01:54:42
[ Quote ] [ Edit ] [ Delete ] 5#
类似 HNOI2016 矿区可以有线段树做法.
save_code @ 2018-10-04 19:10:31
[ Quote ] [ Edit ] [ Delete ] 6#
一个LOG可以搞定?
save_code @ 2018-10-04 19:10:32
[ Quote ] [ Edit ] [ Delete ] 7#
一个LOG可以搞定?
sumix173 @ 2018-10-09 14:08:11
[ Quote ] [ Edit ] [ Delete ] 8#
yes, one log.
Assign each vertex to one of its adjacent regions, then a segment tree can be used to maintain those info of vertices with the DFS sequence of the graph. For each query, some vertices at the boundary may not be included, but which can be fixed easily as the boundary is totally given by the query. The time complexity of this part is linear to the input scale.

The prob of hnoi2016 MINE was motivated by this idea, but the standard solution of this problem is to construct a BST of the planet graph from the perspective of geometry (I really can't recall the details), please refer to the training team's paper of Honghua Dong that year.
[Top] [Previous Page] [Next Page]

HOME Back