一道挺妙的题,代码难度并不是很大。貌似洛谷春令营讲过这道题然而并没有人去写?(除了 LJC00118 和我 QAQ ...)

我们把区间离线,依次加入序列的每个数并更新以这个数作为右段点的查询的答案。

考虑新加入的数,它能够更新的区间一定满足以下性质。

  • 能够更新的区间不可能超过新加入的数的值上一次出现的位置(如果是第一次加入则为 0 )——再往前排序去重后并不会改变

  • 这个数最多会和值在其 \pm 11 的范围内的数产生贡献——长度超过 10 的极长连续段不需要统计答案。

我们可以把值域在其 \pm 11 范围内的数提取出来,并按照从后往前的顺序重新插入。每次考虑新加入的数对答案产生的贡献(注意是新「加入」而不是新「插入」)。可以发现这是个区间修改状物,可以直接线段树维护,也可以差分到树状数组上。

- 阅读剩余部分 -

一道还是挺有意思的题,讲下某神仙课件里的 Matrix Tree 定理做法。

首先最小生成树有个很显然的性质,就是对于任意两颗同一个图的最小生成树,他们的边权序列排序后应当相同。可以考虑克鲁斯卡尔算法的过程用归纳法证明。

也就是说如果两棵最小生成树不同,一定是克鲁斯卡尔算法加边时,对 同一边权相同数量 条边的选择不同。

容易发现,每次以任意顺序加完所有相同边权的边后,图的连通性相同,而新加的边,一定是将原图的一些不连通的联通块连接起来。考虑暴力做法 2^{10} 枚举,即可有一种朴素的 AC 算法。

然而此题可以跑到 O(n + m k^2) ,可以发现选边的过程类似于生成树计数,我们可以直接用 Matrix Tree 定理求出对于每个连边后联通的联通块的方案树,根据乘法原理相乘即可。

需要注意:

  1. 题目给出的数不是质数(我就因为这个调了很久
  2. 需要把加边前已经联通的联通块缩点

- 阅读剩余部分 -

容易发现答案与旗杆的顺序无关,我们可以把旗杆按照从矮到高的顺序排序,这样的话我们只需要维护两个操作:

  1. 插入一些 0
  2. 给一个前缀整体 +1

考虑每次 +1 操作,除了这个前缀中的最大值,每个数的相对位置不会改变。考虑放到线段树上,对于最大值二分出其区间,对其特殊处理后移即可。

- 阅读剩余部分 -

现在每天一场模拟赛,考完还有一堆题目要订正。然而晚上回家后上不了学校 OJ ,要知道自己订正的对不对还得第二天跑来学校测 ......

前置条件

  • 一台位于学校的电脑,能保持长时间开机。
  • 一台位于公网的服务器,不需要太高的配置,推荐学生机。

这篇教程将会教你

  • 如何利用 SSH 建立反向连接
  • 如何利用 nginx 实现端口转发并配置
  • 如何利用 nginx 实现屏蔽特定页面的效果
  • 一些操作来保证安全性

- 阅读剩余部分 -