首页 > 编程学习 > 闲话 22.9.23

闲话 22.9.23

发布时间:2022/9/23 21:02:27

闲话

预告一下
继FFT FWT FMT后又出现了FDT(F的T)
\(\text{Z}\color{red}{\text{hou}}\) 喜欢在有着秋日气氛的校园里面散步
\(\huge Cdsidi\)喜欢吃七分饱而且巨所以\(_水\)管子炸了
不知道说什么东西

不知道我在说什么?你很快就会知道的

昨天jjdw的歌词是LostOne的号哭
想唱但是脑子里只有mafu的不知道是什么的歌 似乎是《空腹》
今天jjdw的(没有)歌词是Merry Bad End
是mafu的歌但是没歌词所以一句都想不出来

但是《空腹》很会唱(
虽然唱不上去就是了

今天是饭的图!

旅 - 其四

image

比较大所以这个是小一点(一半)的

点我!

因为被AT题干掉了
于是在找构造题练手
在洛咕上搜构造标签
于是给了我一道题
P4689 [Ynoi2016] 这是我自己的发明
啊对对对

几天来随便切了几道题

因为jjdw写了所以我写一下
其实没什么难的题 要么一眼出性质要么两眼出结果
所以意识流一下 看不懂见谅

没有代码。

[YER 2021] TEST_68

给定一棵 \(n\) 个节点的树,第 \(i\) 个点有一个权值 \(a_i\)

对每个点 \(x\),其的答案为其所在子树外的所有点中,选两个可以相同的点 \(i,j\)\(a_i\) 异或 \(a_j\) 的最大值,如果选不出两个点,则认为 \(x\) 的答案是 \(0\)

\(1\le n\le 5 \times 10^5\)\(0\le a_i \le 10^{18}\)

第一眼Trie。考虑怎么维护求值。

这题唯一的性质就是“子树外”三个字。从这上面下手。
叶子节点显然除了自己都能选。然后外推性质发现最终似乎有很多点的答案都是相同的。
设树上任意两点的 xor 最大值出现在 \(a[p] \oplus a[q]\)。根据性质似乎有 \(p\)\(q\) 到根的路径上外的所有点答案都是 \(a[p] \oplus a[q]\) 。这样问题就被解决大半了。这部分答案可以直接上Trie板子。

然后考虑怎么求出 \(p\)\(q\) 到根的路径上点的答案。两边的路径除了LCA外是不相关的,可以求两次。因此在特判LCA的情况下可以拆成两条链求解。
对于一条根到目标节点的链,我们从根开始往下扫,扫到一个节点先把不含目标节点的子树中的值加入Trie,这棵Trie里的 xor 最大值就是这个点的答案。然后把这个点加入 Trie,接着扫。

总时间复杂度是三次插入+查询每个节点。因此是 \(O(n \log {值域})\) 的。

简单题

\(T\) 组询问。一开始给定一个常数 \(K\)。每次询问单独给定 \(n\)。请你求出:

\[\sum_{i=1}^{n}\sum_{j=1}^{n} (i+j)^K \gcd(i,j) \mu^2(\gcd(i,j)) \pmod {2^{32}} \]

\(T = 10^4\), n\le 10^7,\(1 \leq K < 2^{31}\)

化式子题。也不太难,是不同于幽灵乐团的做法。

\[\begin{aligned} & \sum_{i=1}^{n}\sum_{j=1}^{n} (i+j)^K \gcd(i,j) \mu^2(\gcd(i,j)) \\ = & \ \sum_{x = 1}\sum_{i=1}^{n}\sum_{j=1}^{n} (i+j)^K x \mu^2(x) [\gcd(i,j) = x] \\ = & \ \sum_{x = 1}x \mu^2(x) \sum_{d=1}\mu(d) (xd)^K \sum_{i=1}^{n/xd}\sum_{j=1}^{n/xd} (i+j)^K \\ = & \ \sum_{T = 1} \sum_{d|T} \mu^2(d) \mu(\frac Td) d T^K \sum_{i=1}^{n/T}\sum_{j=1}^{n/T} (i+j)^K \end{aligned} \]

\(S(n) = \sum_{i=1}^{n}\sum_{j=1}^{n} (i+j)^K\)\(G(n) = \sum_{i=1}^{n} i^K\)\(f(T) = \sum_{d|T} \mu^2(d) d \mu(\frac Td)\)
则原式变为

\[\sum_{T = 1} S(\frac nT) f(T) T^k \]

这个一眼整除分块。然后考虑预处理 \(f\) 的前缀和以及快速处理 \(S\) 的单点。

\[S(n) = \sum_{i=1}^{n}\sum_{j=1}^{n} (i+j)^K = \sum_{i=n+1}^{2n} \sum_{j=1}^{i} j^K - \sum_{i=1}^{n} \sum_{j=1}^{i} j^K = G(2n) - 2G(n) \]

证明考虑竖着求和变横着求和。然后自然数幂是完全积性的 \(id_K\),可以直接筛,这样我们就解决完两个东西了,剩一个 \(f\)

简单推一下 \(f\) 的筛法。\(f\) 在质数处的取值显然 \(p - 1\),接下来是筛的部分。

\[\begin{aligned} p\nmid n \rightarrow f(pn) & = \sum_{d|n} \mu^2(d) d \mu(\frac {pn} d) + \mu^2(pd) pd \mu(\frac {n} d) \\ &= \sum_{d|n} -\mu^2(d) d \mu(\frac {n} d) + \mu^2(d) pd \mu(\frac {n} d) \\ & = (p-1)f(n) \end{aligned}\]

\[\begin{aligned} p\mid n\ \land\ p^2 \nmid n \rightarrow f(pn) & = \sum_{d|\frac np} \mu^2(d) d \mu(\frac {pn} d) + \mu^2(pd) pd \mu(\frac {n} {d}) + \mu^2(p^2d) p^2d \mu(\frac {n} {pd}) \\ & = \sum_{d|\frac np} \mu^2(pd) pd \mu(\frac {n} {d}) \\ & = -p \sum_{d|\frac np} \mu^2(d) d \mu(\frac {\frac np} {d}) \\ & = -p\times f(\frac n p) \end{aligned}\]

\[\begin{aligned} p^2\mid n\ \land\ p^3 \nmid n \rightarrow f(pn) & = \sum_{d|\frac np} \mu^2(d) d \mu(\frac {pn} d) + \mu^2(pd) pd \mu(\frac {n} {d}) + \mu^2(p^2d) p^2d \mu(\frac {n} {pd}) + \mu^2(p^3d) p^3d \mu(\frac {n} {p^2d}) \\ & = ({容易发现这玩意哪一项都没值}) \times 0 \end{aligned}\]

筛就完了。然后没了。

[NOIP2015] 充满了希望

给一个长为 \(n\) 的序列,有 \(m\) 个操作,操作编号从 \(1\)\(m\),每个操作为:

1 x y:将序列位置为 \(x,y\) 的两个元素交换。

2 l r x:将序列区间 \([l,r]\) 内所有元素修改为 \(x\)

3 x:查询序列 \(x\) 位置的值。

现在有 \(q\) 次查询,每次查询给出一个操作的区间 \([l,r]\)

先将序列中的元素全部置为 \(0\),之后依次进行从 \(l\)\(r\) 的所有操作,求出所有这些操作中所有 \(3\) 操作的答案的和。

查询之间独立。

\(1\le n,m,q\le 10^6\)\(1\le x\le 10^9\)

一眼被吓到。第二眼发现这玩意是求和。然后就好搞了。

容易发现所有查询查出来的要么是2操作改的值,要么是0。
考虑先预处理出每次操作的值。

我们整来一棵线段树,叶子维护元素最新一次修改对应的修改操作编号,然后顺序扫每个操作。如果是1就把树上x和y叶子节点的编号swap,2就区间覆盖这个操作,3就把当前x的编号记录下来。

对于查询,我们离线下来做扫描线,过程中用BIT维护当前操作集合
经典地,在r位置记录一个l,然后顺序扫每个操作。对于3操作,把BIT里记录的编号位置加一个编号对应操作的x值,其他操作不管。操作完扫当前位置的查询,查一下BIT里l-r区间内的和就是最终答案。

看上去很离谱但是比较套路。

异或粽子

给定一个长度为 \(n\) 的数组 \(a_i\) ,你每次可以选择一个区间 \([l,r]\) ,其价值为 \(val[l,r]=\bigoplus_{i=l}^r a_i\)。求价值最大的 \(k\) 个不同区间的价值和。

\(1\le n\le 5\times 10^5,1\le k\le \min\{\frac {n(n-1)} 2 ,2\times 10^5 \},0\le a_i\le 2^{32}-1\)

比较套路?这题应该也比较经典了。
上来求一个 xor 前缀和 \(s_i = \bigoplus_{i=1}^r a_i\),然后问题转化成从 \(s_{0\dots n}\) 里选出 \(k\) 对来 xor 的最大值。

不想去重,因此乘2直接扫,最后答案除以2就行了。把所有值插入一个 Trie,然后就能快速找到和数 \(a\) xor 的第 \(k\) 大值了。

产生当前最大值的方式也很套路。我们把与每个 \(s_i\) xor 得到的第一大值插入一个大根堆,然后每次取堆顶累加入答案,若当前取出了与 \(s_i\) xor 的第 \(k\) 大值,那将与 \(s_i\) xor 的第 \(k+1\) 大值插入堆即可。
若我们需要前 \(k\) 大值,那迭代 \(k\) 轮后就是答案。

这题的 \(k\) 可以拓展到 \(O(n^2)\) 的级别。现在查询的方式是确定 xor 的对象来搞的,我们也可以直接在 Trie 上二分,先查出第 \(k\) 大,再求出前 \(k\) 大。具体看这篇。

好少好少好少jjdw牛的

Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号