毒瘤出题人，卡时间卡空间！

嗯，如果这一题不是在树上的话貌似可以直接权值线段树维护？不过到了树上的话难道可以权值线段树+树链剖分，表示不明白。于是尝试了一发线段树合并，但是我们的线段树是权值线段树。

$3$ 月份的最后一篇题解了呢……明天就属于 $4$ 月了，离省选不远了…$QwQ$…

发现窝真的很制杖，我们先来聊聊刚开始窝的想法。

我画了画图，然后发现，对于最后答案的分母(不是最简)，是这个序列中这些数的值(废话)，然后发现了每个点的出现次数，然后线段树维护求和。发现效率很低于是试图将出现次数般到二维平面上，然后曼哈顿距离转切比雪夫距离然后二维树状数组维护然后 $WA$ 了然后弃疗。

去 $Mina!$ 上了解了一波虚树，$\%\%\% XZY$ 学长太强辣！

这次总算明白了些虚树，然后 $XZY$ 大佬的例题就是消耗战。

于是看了过来。

一个可爱的 $CDQ$ ，我们将原始序列看成一个一个加入，然后后面的操作就是一个一个删除，这么一个一个操作我们都记下来，然后每个操作记一个 $id$ 表示它将为第几个时间点做出贡献。

当然对于原始序列的一个一个插入的操作这里的贡献是 $1$ ，删除操作的贡献自然是 $-1$ 。

刚开始发现 $SA$ 很可做，不过当时没有看范围，心想美滋滋了这个就是 $SA$ 的板子，然后一看范围心就凉了。

不过可以用 $SAM$ ，我们知道，对于两个串，它们的最长公共子串就是它们在前缀树上的 $Lca$ 。这是显然的，不明白的同学可以康康 $Qiuly$ 酱之前写的 $SAM$ ，可以观察观察图片。

初看题面，看到 $K$ 大我们可以想到主席树，但是连边却又符合 $LCT$ ，但是毕竟 $LCT$ 是不能支持 $K$ 大的，因为 $Splay$ 辅助树不是二叉查找树。

不过主席树我们可以大力启发式合并，合并的时候重建节点的倍增数组并且重新建立节点的权值线段树。这样子每个节点要被修改的期望次数为 $logn​$ 次，那么时间复杂度就是 $O(nlog^2n)​$ (貌似是的)，这足以让我们过这道题了。

后缀数组，我们可以先将所有的卡片连成一个串，每一个卡片数列之间用一个极大数分开保证不出锅。然后的话，对于相同的定义有些鬼，使得我们不能直接做 $SA$ ，这个时候我们将所有的卡片数列的值都转换为当前位置减去上个位置的值即可。

今天的题目貌似暴力分好拿写欸，然而……窝只有 $70$ ？不过排名比昨天上升了什么鬼。

$QwQ$ 题目的确很难懂，所以窝听了讲解后也没听懂多少，不过还是改出了第一题(第一题是人就改的出好吧o(≧口≦)o)。

今天全是原题，然而窝几乎都没做过，于是挂了……

丢人的是考场上组合数的式子 $C[i][j]$=$C[i$-$1][j]$+$C[i$-$1][j$-$1]$ 写成了 $C[i][j]$=$C[i][j$-$1]$+$C[i$-$1][j$-$1]$ ，然后第一题光荣爆 $0​$ ……TAT。

吸取教训！