2.8

数列

赛时想到了没有优化空间的 DP，受 CSP-S2019D2T2 影响决定打表找性质，然而并没有想到换状态

设 \(f[i]\) 为 \(i\) 为某段最大值的答案，则有

\[f[i]=\max_{j<i,\max a[i:j]=\max(a[i],a[j])}\{f[j]+(a[i]-a[j])^{2}+c\} \]

\[ans=\max_{\max a[i:n]=a[i]}\{f[i]\} \]

第二个条件比较烦，仔细思考一下，若 \(\exists j<k<i,a[k]>\max(a[i],a[j])\)，那么 \((a[i]-a[j])^{2}<(a[j]-a[k])^{2}+(a[i]-a[k])^{2}+c\)，即从 \(j\) 转移到 \(i\) 一定不如先从 \(j\) 转移到 \(k\)，再转移到 \(i\) 优，因此这个条件实际上是无用的

通过『不合法转移一定不优』规避掉判断合法性

差量

先进行全局询问得到极差，然后二分出一个最值所在的位置，记为 \(p1\)（询问前缀，判断极差是否改变可知两最值是否都在该前缀中）

排除 \(p1\)，询问二进制下第 \(i\) 位为 \(1\) 的下标（记为 \(S_i\)），再加上 \(p1\) 询问，两结果做差即可得到这些数与 \(a_{p1}\) 的差（记为 \(T_i\)）。考虑将其一一对应，对于 \(a_i\)，\(|a_{i}-a_{p1}|=\cap_{\text{the jth bit of i is 1}}T_{j}\)，最终得到了每个数与 \(a_{p1}\) 的差

通过极差可以确定出另一个最值 \(p2\)，那么 qry1(p1),qry1(p2) 即可得到 \(a[p1]\) 是最大值还是最小值，然后就能推出 \(a\)

\(n\) 很小因此可以随便实现

二进制分组减少交互次数
差值关系从最值入手（大小关系确定）