20181211 - NOI模拟赛

T1、T3 的思路基本都成型但是由于自己傻逼最后一个都没调出来。

LCM

考虑一个数最多被分解为一个大于 $\sqrt {\max a_i}$ 的质数和一些小于 $\sqrt {\max a_i} $ 的质数的乘积。考虑小于的部分,最多有 4320 种状态,我们可以用一种简单背包的方法统计出每一种值的个数。对于大于的部分,相当于我们给上一步统计的个数的时候给个数加上一个权值。通过一些简单的处理避免超过 $\sqrt { \max a_i }$ 的质数被重复计算。理论复杂度 $O(n \times 4320 \times (\log n + \log 4320))$ 。

Xor

不知道为什么出题人要把题意搞的这么迷。我们直接把边权异或到两个端点上,计算割的价值就是一边的点的权值的异或和。考虑贪心,把点按照权值从大到小排序,利用线性基维护会不会产生 $0$ ,不会就加上价值,否则减掉即可。

Lis

考虑把从左到右的最长上升子序列转变为从右到左的最长下降子序列,这样每次操作最多影响十棵树。树套树(树状数组套权值线段树)维护一个后缀高度大于指定值的 dp 值的最大值,每次暴力重算那十棵树即可。复杂度 $O(n \log^2 n \times 10)$ 。需要注意的是需要动态开的节点个数可能会很多,一定要开够。

一道卡常题。考虑分块。

如果查询的 $l$ 和 $r$ 不在同一个块内。

1
2
查询区间 =>                ┌-----------------------------┐
分好的块 => [.........][........][........][........][........][........]

把查询的区间分成三个部分、A(块前零散部分)、B(整块的)、C(块后零散部分)

先考虑每个部分自身与自身匹配对答案的贡献。我们可以预处理出从每个点出发,到所属块的开始 / 结尾的逆序对个数,分别用 lft[]rit[] 表示,预处理时间复杂度 $O(\sqrt n \times \sqrt n \times \log n)$。

1
2
3
┌-----1.-----┐               1. 这一部分的逆序对个数表示为 lft[i]
┌-----2.----┐ 2. 这一部分的逆序对个数表示为 rit[i]
[............i...........]

接下来我们考虑 A -> B , C -> B 的贡献,类似于蒲公英这题,处理出 cnt[i][j] 数组表示前 $i$ 个块内小于等于 $j$ 的数字个数,查询时枚举 A 和 C 中的每一个数,利用这个前缀和查询对答案的贡献。这个部分也可以不在查询的时候做,而是预处理出结果,做二维前缀和,直接查询。

接下来考虑 A -> C 的贡献,由于 A 和 C 是不重合的两个部分,可以采用类似归并排序的方法,把两个序列合并的同时计算出逆序对个数。

如果查询的 $l$ 和 $r$ 在同一个块内。

首先我们考虑,相邻的两个区间 A 和 B 。A 和 B 总共的逆序对个数,等于 A 内部的逆序对个数 + B 内部的逆序对个数 + A 对 B 贡献的逆序对个数。

好,那么我们再来考虑 $l$ 和 $r$ 在同一个块内:

1
2
3
4
┌------A+B-------┐      这一部分即之前已经处理出的 lft[r]
┌----A----┐ 这一部分即之前已经处理出的 lft[l]
┌--B---┐
[.........l......r.......]

现在我们要求 B 的逆序对个数,只需要把 A + B 的逆序对个数减掉 A 内部的逆序对个数,再减掉 A 对 B 的逆序对个数即可。

剩下你只需要时间来卡常。

最近忽然发现 BZOJ 的权限题还是很多的(可能是因为以前搜不到就不搜了现在上 DARKBZOJ ),看来还是得众筹买个权限号了(雾

这是一道傻逼数据结构题,由于数据范围小,各种奇葩算法随便过。本菜鸡就写了个普通的树状数组套莫队,各位大佬不要见笑。

  1. 单点修改 & 区间查询

    傻逼都会。

  2. 区间修改 & 单点查询

    假设 $a$ 数组为我们当前维护的数组,定义 $b_i = a_i - a_{i - 1}$ ,则 $a_i = \sum_{j = 1}^{i}b_j$ 。用单点修改 & 区间查询的树状数组维护 $b$ ,修改区间 $l$ 到 $r$ 只需使 $b_{l-1} + value$ 且 $b_r - value$ ,查询 $a_i$ 只需求 $\sum_{j = 1}^{i}b_j$ 。

  3. 区间修改 & 区间查询

    同 2 的假设下,求 $\sum_{i=l}^{r} a_i$ 即求 $\sum_{i=1}^{r} a_i - \sum_{i=1}^{l-1} a_i$ ,我们只需考虑如何求 $\sum_{i=1}^{k} a_i$ 。

    $\sum_{i=1}^{k} a_i = \sum_{i=1}^{k} \sum_{j=1}^{i} b_j = \sum_{i=1}^{k} b_i \times (i + 1 - x) = (k+1) \times \sum_{i=1}^{k} b_i + \sum_{i=1}^{k} (i \times b_i)$

    所以我们开两个树状数组,分别维护 $b_i$ 和 $i \times b_i$ 即可。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×