按理来说最近开始了一天一套 div2 计划，第一天做了一套 Div1，第二天做了 hustfc，第三天因为要赶 latex 期末考试，所以什么也没做。

明天写一下 hustfc 比较牛的几题。

A

暴力怎么做，是不是加加加，然后判断。

B

本质上是让长度为 \(i\) 的后缀全是 \(0\) 那么找到最短的有 \(i\) 个 \(0\) 的后缀求一下逆序对就行了。

C

注意到 \(\min(a)\) 选 \(1\) 或者 \(m\) 最好使，暴力找到 \(\max(a)\) 即可。

差分哦

D

对 \(x\in [1,n]\) 计算是不是在 \(a\) 中存在 \(x\) 的因子。再通过差分计算有多少对子的 \(\rm{gcd}\) 是 \(t\in[1,n]\) 不能输入一个 \(a_i\) 标记一下哦！

E

策略大概就是笛卡尔树上 父亲权值减去儿子权值 × 儿子控制区间长度。换一个想法，如果出现了 \(a_l\ge a_k\le a_r\) 且 \(a_k=\max\limits_{i=l}^r\{a_i\}\) 则需要进行 \(\min\{a_l,a_r\}-a_k\) 次操作。

所有操作其实和 \(k\) 没什么关系，主要是 \(\min\{a_l,a_r\}-a_k\) 的数值。看到 shift，自然想到了复制一倍接到原序列的后面。考虑一个 \((l,r,v)\) 的操作区间。

• 如果 shift 之后不会破坏 \([l,r]\) 区间的完整性，或者说 shift 的次数不超过 \(\min\{l,n-1\}\) 而且不小于 \(\max \{r-n+1,0\}\)，那么对操作代价的贡献是一定的，可以差分进行区间加。

• 否则破坏了区间的结构。假设 shift 之后剩下了 \([t,r]\) 在序列开头。这时候可能出现 \(k<t\) 而导致可能 \([t,r]\) 无法通过这轮操作把所有元素变成一样的。但是不难发现可以这个问题通过操作 \((k,r,v')\) 来实现，所以进行 \(v\) 次操作即可。

  不难发现此时操作区间长度和 shift 的次数有关，而且是一个二次函数。而对于所有产生间断的情况的贡献全都是二次函数，同一个操作对这些 shift 的二次函数的系数的贡献是一样的，可以进行差分处理。

好久没见到这样的题啦。好有意思。