题解 P6477 【[NOI Online 2 提高组]子序列问题sequence（暂无数据，禁止提交）】

· · 题解

考场上最后一分钟写完了正解，结果提交的一瞬间刚好结束。。。

这里就来分享一下考场上的思路吧。

题解：

首先，对于区间去重后的元素个数，有一种套路化的递推方法：

如何求出 \operatorname{pre} 数组？可以利用桶排序的技巧，离散化后递推

由于不好解释，直接放代码了

for(int i=1;i<=n;i++)
    cin>>a[i],b[i]=a[i];
sort(b+1,b+n+1);
cnt=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++){
    int pos=lower_bound(b+1,b+cnt+1,a[i])-b;
    a[i]=pos;
} //以上为离散化
for(int i=1;i<=n;i++){
    if(pree[a[i]])pre[i]=pree[a[i]]; //pree 数组指向 a[i] 上次出现的位置
    pree[a[i]]=i;
}

然后这道题 f 平方了。设 g=f^2，带到上面的递推式中，可得

g(l,i)=\begin{cases}1\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\;\;\;\; l=i\\g(l,i-1)\quad\quad\quad\quad\quad\quad\quad\quad\;\; l\leq\operatorname{pre}(i)\\g(l,i-1)+2f(l,i-1)+1\quad \text{else}\end{cases}

我们需要求

T(i)=\sum_{j=1}^{i}g(j,i)

函数的前缀和，这部分可以直接扫描 i 累加，问题变成了如何快速地从 T(i-1) 递推到 T(i)。

直接把 g 带入递推式，可得

\begin{aligned}T(i)&=\sum_{j=1}^{\operatorname{pre}(i)}g(j,i-1)+\sum_{j=\operatorname{pre}(i)+1}^{i-1}\left(g(j,i-1)+2f(j,i-1)+1\right)+1\\&=\sum_{j=1}^{i-1}g(j,i-1)+2(S_{i-1}(i-1)-S_{i-1}(\operatorname{pre}(i)))+\left(i-1-(\operatorname{pre}(i)+1)+1\right)+1\\&=T(i-1)+2(S_{i-1}(i-1)-S_{i-1}(\operatorname{pre}(i)))+i-\operatorname{pre}(i)\end{aligned}

其中 S_i(j)=f(1,i)+f(2,i)+\cdots+f(j,i)。

计算 T(i) 的瓶颈成为了计算 S_i(j)。

当 i\leftarrow i+1 时，由 S 的定义及 f 的递推式可知，这等价于在数列 S 的一部分加上了一个等差数列。

具体地说，i\leftarrow i+1 时对于 S 需要执行以下一系列操作

  1. 给 S_i(\operatorname{pre}(i)+1) 加上 1，给 S_i(\operatorname{pre}(i)+2) 加上 2，……，给 S_i(i-1) 加上 i-\operatorname{pre}(i)-1；

  2. 给 S_i(i) 赋值 S_i(i-1)+1。

所以，我们需要写一个数据结构，支持

显然树状数组，线段树都可以做到。这里我写的树状数组，常数较小。

树状数组在处理区间加等差数列时，只能对原数列差分，将区间加等差数列变为区间加。

树状数组处理区间加，常规方法是对原数列再差分一次。

也就是说，我们需要用树状数组维护

这是可以做到的当时线段树1我就这么做的：

设待处理数列为 A，其差分数列为 B_i=A_i-A_{i-1}。

则

\sum_{i=1}^{n}A_i=(n+1)\sum_{i=1}^{n}B_i-\sum_{i=1}^{n}iB_i

维护数列 B 和数列 iB 的前缀和即可。

也就是说，我们可以在 \Theta(\log n) 的时间复杂度内将 S_i 递推到 S_{i+1}，即将 T_i 递推到 T_{i+1}。

所以总时间复杂度 \Theta(n\log n)。

但是常数较大，需注意优化。

这道题难度还是比较大的（可能是我太弱了），个人意见：难度评级 蓝~紫