设计草图

idea, solution from he_____he, data from csy2005

算法一

我会暴力！

枚举所有的区间，暴力枚举每个 ? 的取值，检验其是否为合法的括号序列。

时间复杂度为 $O(n \cdot 2^n)$，期望通过子任务 $3$，得到 $15$ 分。

算法二

如果 $S$ 中只含有 ?，那么任意一个长度为偶数的区间都是合法的！

通过计算，发现答案即为 $\left\lfloor \frac{n}{2} \right\rfloor \cdot \left\lceil \frac{n}{2} \right\rceil$。

期望通过子任务 $1$，得到 $5$ 分。结合算法一可以得到 $20$ 分。

算法三

注意到，一个区间合法当且仅当以下条件满足：

1. 区间长度为偶数
2. 将所有 ? 替换为 ( 后，把 ( 当成 1，) 当成 -1，所有前缀和均大于等于 0
3. 将所有 ? 替换为 ) 后，把 ) 当成 1，( 当成 -1，所有后缀和均大于等于 0

第二个条件相当于对每个 $l$，存在一个 $p_l$ 使得在 $l\leq r\leq p_l$ 成立。

第三个条件相当于对每个 $r$，存在一个 $q_r$ 使得在 $q_r\leq l\leq r$ 成立。

在预处理出 $p_i, q_i$ 后，我们可以枚举 $l$ 与 $r$ 并 $O(1)$ 进行判定。时间复杂度为 $O(n^2)$。

期望通过子任务 $3 \sim 4$，得到 $30$ 分。结合算法二可以获得 $35$ 分。

算法四

注意到上述问题是一个二维数点问题，我们可以使用排序后树状数组来解决，时间复杂度为 $O(n \log n)$。

期望通过所有子任务，可以获得 $100$ 分。

见贤思齐

idea, data, solution from ix35

算法一

暴力模拟每一轮的操作。

每一轮模拟的复杂度是 $O(n)$ 的，我们可以将询问离线后按照时间顺序来处理所有询问，这样复杂度即为 $O(nd + q)$。

期望通过子任务 $1 \sim 2$，得到 $40$ 分。

算法二

从 $i$ 到 $p_i$ 连边，将形成一棵基环内向树。我们先考虑比较简单的情形——一棵有根树该怎么做：

假设根的权值一直不变（或者看成每次 $+1$ 也行），将第 $j$ 天黄昏时第 $i$ 个工程师的技术水平是 $f(i,j)$，那么我们有：

$$\begin{cases}f(i,0)=a_i\\ f(i,j)=f(i,j-1)+[f(i,j-1)\leq f(p_i,j-1)]\end{cases}$$

可以发现，对于某个 $j$ 如果 $f(i,j)=f(p_i,j)$ 或 $f(i,j)=f(p_i,j)+1$，那么之后也会始终保持这种关系。为了更好发掘这种性质，我们对 $f$ 进行一个平移，定义：

$$g(i,j)=f(i,j+dep_i)-dep_i$$

其中 $dep_i$ 表示 $i$ 的深度，那么：

$$g(i,j)=g(p_i,j)\to g(i,j+1)=g(p_i,j+1)$$

证明是直接的。

于是我们可以用线段树维护 $g(i,*)$，它可以通过在 $g(p_i,*)$ 的基础上修改一段前缀（修改成一个常数或一个公差为 $1$ 的等差数列）得到，时间复杂度为 $O((n+q)\log V)$，其中 $V$ 是最大时间。

可以通过子任务 $3$，得到额外的 $20$ 分。结合算法一可以获得 $60$ 分。

算法三

再考虑基环树怎么做。事实上我们只需如下观察：设第 $i$ 天所有工程师的技术水平最小值为 $mn_i$，则这一天所有权值为 $mn_i$ 的人一定会增长，从而第 $i+1$ 天所有人的权值最小值就是 $mn_{i+1}=mn_i+1$。

这告诉我们，最小值一定每天都在工作使得自己的水平增长，所以我们找到一个环上 $a_i$ 最小的人，然后断掉 $i$ 与 $p_i$ 之间的边并假设 $f(i,j)=a_i+j$，然后当成树做即可。

时间复杂度为 $O((n+q)\log V)$，期望通过所有子任务，得到 $100$ 分。

装配序列

idea, data, solution from Kubic

出题人原本给的题意是求前缀严格 LIS，不过后来似乎是为了方便写题目背景改成了前缀最小非严格 LDS 划分，显然两者是完全等价的。

算法一

直接拿出前 $10^6$ 项然后用你喜欢的方法计算所有前缀的 LIS 即可。

期望得分：$5$。

算法二

可以发现如果 $x\ge n^2$，那么答案为 $n$。

直接拿出前 $n^2$ 项然后用你喜欢的方法计算所有前缀的 LIS 即可。

时间复杂度 $O(n^2\log n+m)$。

期望得分：$15$。

算法三

考虑 LIS 的一种贪心求法：维护一个递增序列 $b$。假设当前考虑的数是 $x$，找到最小的 $y$ 满足 $b_y\ge x$ 并将 $b_y$ 改为 $x$。如果不存在这样的 $y$ 那么就在 $b$ 的末尾插入一个 $x$。

这个算法通常的实现是按照下标从小到大，每次考虑一个值。但本题中我们考虑按照值从小到大，每次考虑一个下标。

我们考虑维护出这个长度不超过 $n$ 的序列，每次询问的答案即为序列中 $\le x$ 的数的个数。这是因为这个序列可以看作是在维护 dp 数组的差分。

我们可以归纳地认为任何一个时刻每种数保留的都是一个前缀。设当前考虑到的值在排列中的下标为 $x$，下标为 $i$ 的数保留了 $c_i$ 个。那么进行如下过程：

• 初始 $c_x=0$。
• 依次访问 $(x,n]$ 中的每一个 $i$，如果 $c_x < c_i$，那么交换 $c_x$ 和 $c_i$。
• 依次访问 $[1,x)$ 中的每一个 $i$，如果 $c_x < c_i-1$，那么先交换 $c_x$ 和 $c_i$，然后 $c_x\leftarrow c_x-1,c_i\leftarrow c_i+1$。
• 最后 $c_x\leftarrow c_x+1$。

直接暴力维护即可做到 $O(n^2+m\log n)$。

期望得分：$40$。

算法四

设 $b=a^{-1}$。

我们相当于要将 $b$ 分为 $m$ 段，使得它们的 LIS 之和最大。

可以发现 $LIS(b_{l,r+1})+LIS(b_{l+1,r})\le LIS(b_{l,r})+LIS(b_{l+1,r+1})$，即转移矩阵满足四边形不等式。因此答案关于 $m$ 是下凸的。

因此我们可以使用 wqs 二分，设当前二分的斜率为 $w$。

问题转化为：选出 $b$ 的一个子序列 $p$，最大化 $|p|-w\times\sum\limits_{i=1}^{|p|-1}[p_i>p_{i+1}]$。使用树状数组优化 dp 即可做到 $O(n\log n)$。

因此总时间复杂度为 $O(n\log^2 n)$。

当然，直接使用亚单位蒙日矩阵快速幂科技也可以做到相同的复杂度。

期望得分：$20$。

算法五

通过打表等方式可以发现在 $n=2\times 10^5$ 且数据随机的情况下 $c$ 中非零位置个数大概有 $k=900$ 个左右。猜测 $k$ 可能是 $O(\sqrt n)$ 级别，暂时还没能给出其证明。

实时维护这些非零位置即可做到 $O(n(k+\log n)+m\log n)$。

期望得分：$55$。

算法六

可以发现 $\sum\limits_{i=1}^n c_i\le n$。

设一个阈值 $B$，$\sum\limits_{i=1}^n [c_i>B]\le\dfrac{n}{B}$。

在上面的过程中，每次访问到的 $c_i$ 是严格单调递增的，

考虑上面的过程中第二步的维护方法。

我们对于 $\le B$ 中的每一种数用一个 set 维护它们的出现位置，对于 $>B$ 的数直接维护它们的出现位置。

先对于每一种数找到它们在 $(x,n]$ 中的第一次出现的位置。显然如果某种数在 $(x,n]$ 中的第一次出现没有被访问到，那么这种数一定没有被访问到。这样我们在 $O(B\log n+\dfrac{n}{B})$ 的时间复杂度内筛选出了 $O(B+\dfrac{n}{B})$ 个有用的位置，然后在 $O(B+\dfrac{n}{B})$ 的时间复杂度内模拟上面的操作，最后在 $O(B\log n+\dfrac{n}{B})$ 的时间复杂度内更新位置信息。

因此总时间复杂度为 $O(nB\log n+\dfrac{n^2}{B}+m\log n)$，取 $B=\sqrt{\dfrac{n}{\log n}}$ 时可以得到最优的 $O(n\sqrt{n\log n}+m\log n)$。

期望得分：$100$。

算法六 $+ \varepsilon$

by 127

我们可以进一步分析算法六的复杂度！

我们刚才直接将一次 set 操作的时间复杂度估计为 $O(\log n)$。考虑使用更加精确的分析方法。取 $B=\sqrt n$，设 $d_i$ 表示 $c_j=i$ 的个数。

那么我们有 $\sum\limits_{i=1}^B i\times d_i\le n$，而一次操作的时间复杂度可以估计为 $\sum\limits_{i=1}^B\log(d_i+1)$。

考虑 $\prod\limits_{i=1}^B(d_i+1)$，可以化为 $\dfrac{\prod\limits_{i=1}^B(i\times d_i+i)}{B!}$。

而我们知道：

$$ \sum\limits_{i=1}^B(i\times d_i+i)\le n+\dfrac{B(B+1)}{2}\le 2n $$

根据均值不等式可以得到：

$$ \prod\limits_{i=1}^B(i\times d_i+i)\le\left(\dfrac{2n}{B}\right)^B=(2B)^B $$

因此时间复杂度可以估计为：

$$ \sum\limits_{i=1}^B\log\left(\dfrac{2B}{i}\right)\le\log(2B)+\int_{1}^B\log\left(\dfrac{2B}{x}\right)dx=O(B) $$

因此总时间复杂度为 $O(n\sqrt n+m\log n)$。

期望得分：$100$。

bonus: interval query with $\tilde{O}(n^{1.5})$ time

tips: seaweeds method

by 127