昨夜闲潭梦落花

· · 个人记录

上来，先学术部分？

毒瘤 Delov 出了个数据结构题。

Chino 给出了 O(n \sqrt n) 的分块（orz）。
Delov 给出了 O(n \sqrt{n \log n}) 的分块（orz）。
我给出了 O(n \log ^ 2 n) 的可持久化树套树（?）。

（以上算法按照效率递减排序）

由于 Delov 想把这个题出到暑假集训模拟赛，所以题干在此不表。

当然，这让我想起来了很久以前在讨论版上看到的一个东西。

维护一个 BST。
每当访问一个节点的时候，设其子树的大小为 a。
则我们有 \frac{1}{a} 的概率将其子树重构。

首先考虑其平衡性。
我们将重构的概率函数设为 \frac{2}{a}。
那么，对于一个子树，我们再插入 a 个元素，有

\sum_{k=1}^a \frac{2}{a + k} > 1

因此在期望意义下，子树大小翻倍之前就会被重构。
所以此树重量平衡。

（当然，以上分析并不严谨。但是并不影响复杂度的数量级）

然后是重构代价。
显然，访问一个节点的期望代价是 O(1) 的。
因此此树的复杂度与替罪羊树是一样的。

有什么用？
期望意义下任意时刻树都是平衡的。
不基于均摊，那就可以可持久化了啊。
且，此树在插入时无需旋转或分裂，可以做树套树的外层树。
常数极大就是了。

此树的实现见远古代码。

又有人给了这样一个题。

给定一个长为 n 的序列 A。
对于给定的整数 k，我们定义这个序列的权值：
将所有下标 \mod k 相等的位置相乘，然后求和。
对于 k \in [1, n]，求出序列的权值。

目前只能给出一个比较抽象的 O(n \log ^ 2 n) 的做法。
细节较多。读者可以自行思考。
如果有巨佬可以做到更优可以私信 D 我。

什么，你问我怎么全是 OI？
你觉得我像是学会了 whk 的样子吗。
那好吧，来一点非 OI 内容。

考虑如果我们并不是绝顶聪明，如何求解以下积分：

\int \frac{1}{x^2 + a^2} dx

其中 a 为常量。

我们对下面进行因式分解。
得：

\int \frac{1}{(x + ai)(x - ai)} dx

然后裂项，得：

\frac{1}{2ai}\int \left( \frac{1}{x - ai} - \frac{1}{x + ai}\right) dx

这里就显然了。得到：

\frac{1}{2ai} (\ln (x - ai) - \ln (x + ai))

下一步，使用喜闻乐见的辅助角公式和欧拉公式把 \ln 去掉。
（x + ai = \frac{e^{\frac{ai}{x}}}{\sqrt{x^2 + a^2}}）
（这下 whk 相关了吧）

最后的结果是 -\frac{\arctan(\frac{a}{x}) }{a}

因此，我们发现，对于幂函数 f(x)，求解 \int \frac{1}{f(x)} dx 几乎均可以用上述方法解决。
（像是 \int \frac{1}{x^2} dx 之类的就不提了）
且，难度与因式分解相同。

事态的发展与预期基本相同。

whk 大抵是没什么长进的。
高一什么水平现在基本上还是那样。
可喜的是，仅三个星期就已经完全恢复了水平了。
（指仍然是垫底）

曾经询问了港大有关事宜。
得知学费比某高中还要高十倍左右。
如果有这经费支持的话，我为什么不去冲一冲 USACO。
遂弃。

平日边摆烂边学术。
同桌先后是生奥的和物奥的。
又开拓视野了。

近来也确实发现了 whk 不好的原因。
大抵是注意力无法集中吧。
很难完整的听完一节课。
或者，上午听了两节课。困了。遂睡。

然而，对于遇到的个别问题，极大的吸引了我的注意。
然后一个自习过去了。

这似乎是在自我封闭吧。
表面上看对各式各样的新事物充满了好奇与兴趣。
而实际上呢，因果关系应该倒过来。
因为感兴趣，才会对新事物充满好奇。
当然，这种习惯从小就有。

或许每个人都是这样的吧，都封闭在自己的领域上。
结交感兴趣的人，学感兴趣的知识，做感兴趣的工作。
并将这种行为称为自由。

当然，还有的人无法封闭在自己的领域内，并因此闷闷不乐。
或许这种人是偏多的。

闲来易生事。
之前打 OI 的时候，看似每天都很闲。
但，和近期相比的话，那还确实是挺忙的。
毕竟，现在我每天没什么学业上的压力。

于是想起了之前写的闲话来了。
评价是缺乏表现力。
先不考虑学术部分。其他部分确实是真实想法的表述。
然而略显生硬就是了。
像，小学生作文？

于是考虑了一下如何提升文字的表现力。
按照我的习惯，自然是不喜欢一次性把话说明白的。

而事实上，很多著作的语言都是极为质朴的。
读起来给人的感觉却完全不一样。

也便只好解释为，深度不够了。

闲来易生事。
近期才刚刚摸到一点多项式相关的基础内容。
感觉多项式也还比较有意思（?）

显然，人们总是会下意识的拒绝自己不熟悉且看上去困难的东西。
就像，公共自习物奥的人分享题目没人听一样。
（当然，我其实也不听来着。高数没学好，不懂）
这或许也导致了之前一直没有接触多项式。
这或许也导致了之前 joke 说这东西简单而我不信。
当然，现在仍然不信。

尝试继续发展重工业。

好几天，他仿佛中了魔，总是低声地嘟嚷什么，并为自己反复斟酌的各种假设感到吃惊，自己都不相信。
最后，在十二月里的一个星期、吃午饭的时候，他忽然一下子摆脱了恼人的疑虑。
孩子们至死都记得，由于长期熬夜和冥思苦想而变得精疲力竭的父亲，如何洋洋得意地向他们宣布自己的发现：

“地球是圆的，像橙子。”

（选自《百年孤独》）

精神状态下滑严重。
闲的吧，也许。
在先前的闲话里面有表述。
然而到现在又过了半年，没什么改观。
随着积累程度越来越深了吧。

先前一直坚持学术自由来着。
然后推广到了其他领域。
大致就是，对于因国家界限而造成的隔阂而不满。
崇尚整体利益。

而这个逻辑有其显然的矛盾点。
意识到这一点之后，想起来了 Fate/zero 和魔圆。

表述的是同一种问题吗？
可能只是我想多了吧。

尽管什么都想不明白，生活总归是要继续的。
最好的方法便是别人做什么就跟着做什么。

路的尽头也许尽为混沌。
是一个人走过去还是被一群人挤过去，或许一样。
虽然，已经离人群日渐遥远了。

每个人都有自己独立的想法的社会，如何平稳运行下去？
不知道。
还没见过这样的社会。

斜月沉沉藏海雾，碣石潇湘无限路。

不知乘月几人归，落月摇情满江树。