简述

后缀数组是一种后缀数据结构,记录一个字符串后缀按字典序排序的结果$SA_i$以及其与前后串$LCP$(最长公共前缀)$Height_i$

我是CQ初三CSP蒟蒻选手zzw4257

这是我新建的Hexo博客，希望多多关照

联系方式：

QQ:809050685

luogu:zzw4257

cnblogs:zzw4257

BSOJ:bizhouziwei20

_——人常说无论做什么都不要忘了初心，但如果一个人从来没有”应该”去忘了初心，又从何谈起的初心。_

看到没有人用老师的办法，于是自己写一下思路

思路第一步:排除旧方法

首先这道题和$4178$不一样，因为那道题是计数，而这道题是求最值，最值有个坏处，就是对于来自相同子树的信息没法高效剔除,比如容斥用不了，举例来说，对于这道题，如果我们继续用尺取法维护黑点个数，对于一组刚好使$cnt_l+cnt_r\leq k$的$l,r$,且$[l+1,r]$所在子树都与$l$不同时就可以选取$l~and~x\in [l+1,r]$,我们要使$dis_l+dis_x$只需使$dis_x$最大，因此每次递归建$ST$表$RMQ$即可

题目

H国的社会等级森严，除了国王之外，每个人均有且只有一个直接上级，当然国王没有上级。如果A是B的上级，B是C的上级，那么A就是C的上级。绝对不会出现这样的关系：A是B的上级，B也是A的上级。
　　最开始的时刻是0，你要做的就是用1单位的时间把一个消息告诉某一个人，让他们自行散布消息。在任意一个时间单位中，任何一个已经接到消息的人，都可以把消息告诉他的一个直接上级或者直接下属。
　　现在，你想知道：
　　1.到底需要多长时间，消息才能传遍整个H国的所有人？
　　2.要使消息在传递过程中消耗的时间最短，可供选择的人有那些？

题目描述

JOI村有一片荒地，上面竖着N个稻草人，村民们每年多次在稻草人们的周围举行祭典。
有一次，JOI村的村长听到了稻草人们的启示，计划在荒地中开垦一片田地。和启示中的一样，田地需要满足以下条件：
田地的形状是边平行于坐标轴的长方形；
左下角和右上角各有一个稻草人；
田地的内部(不包括边界)没有稻草人。
给出每个稻草人的坐标，请你求出有多少遵从启示的田地的个数
简述 求$n$个点组成的内部不含其它点的矩形有多少

【前置知识】

组合数公式($n\in N$):$C_n^m$=$\frac{n!}{(n-m)!\cdot m!}$

拓展（$n\in R$）:$C_n^m$=$\frac{\prod_{i=n-m+1}^n{}i}{m!}$

二项式定理:$(a+b)^n = \sum_{i=0}^{n} C_n^i a^{n-i} b^i (n>0)$

拓展:$(a+b)^{-n} = \sum_{i=0}^{-n} C_{-n}^i a^{n-i} b^i(n>0)$

Part I 前置技能

数论分块

性质一:对于$\large \lfloor \frac Ni \rfloor$,最多只有$2\sqrt{N}$种取值

性质二:对于使得$\large \lfloor \frac N{i’} \rfloor$=$\large \lfloor \frac Ni \rfloor$的$i’$,
$i’{max}=\large \left \lfloor \frac N{\left \lfloor \frac Ni \right \rfloor } \right \rfloor$

$e.g.$求$\sum_{i=1}^N \lfloor \frac Ni \rfloor(N<10^{12})$

性质

性质1：对树长链剖分后，树上所有长链的长度和为$n$

性质2：对于树上任意一点$x$，它的$K$级祖先$y$所在长链的长度一定$\ge K$。

性质3：从任何一个点向上跳到根所经过的轻边不会超过$\sqrt n$条