Codeforces Round #709 补题
Codeforces Round #709
这场乱搞场，很迷。
D.Playlist
$n$个数字按顺序给定$a_1,a_2\dots a_n$，从$1$开始循环，设当前保留数字$x$，下一个相邻的未删除数字位$y$，若$gcd(a_x,a_y)=1$，则删除$y$，并从下一个数字开始操作。请按顺序输出被删掉的数字的编号。
思路
这题很迷，一开始感觉是按$gcd$分块+链表贪心。
看了别人的题解既不理解正确性又不明白复杂度分析。
我们可以发现，若一段区间$[l,r]$内连续的$gcd>1$成立，那么该区间内只有右端点$r$才会移除别人，而$[l,r)$只可能会被别人移除。
那么我们使用队列来维护$gcd=1$的点对（放入点对中第一个点），本质还是模拟。
原本相邻的点对$(x,y)$，若$gcd(a_x,a_y)=1$，那么移除$y$，并且让$x$指向剩下点中$y$的下个点（维护相邻点对 ），将$x$放入队尾。
否则若$gcd(a_x,a_y)>1$，那么点$x$永远不会移除别人，我们可以不考虑$x$点产生的效果，直接让$x$出队，这个也是终止条件。
复杂度分析
没错困扰了我一下午。
一轮跑下来只有相邻$gcd=1$的点存在于队列中，花费$T(n)$。
每一轮，$gcd>1$连续块内只会有一个元素保留下来，而若$gcd(a_x,a_y)=1$，则会删掉$y$（$y$原本处于队列中，是目前$x$的相邻点），每完全进行一轮操作，每次队列内元素数量至少减半。
相当于对数列
$$
n+\dfrac{n}{2}+\dfrac{n}{4}+\dfrac{n}{8}+\dots \dfrac{n}{2^∞}
$$
求和，$n$趋向于无穷时$=2n$。
感觉是$O(n)$的。
代码
1 | //#pragma comment(linker, "/STACK:102400000,102400000") |
E.Skyline Photo
给定两个$n$长数组$h_1,h_2\dots h_n$与$b_1,b_2,\dots b_n$，$h$保证为$n$的全排列，你要将$[1,n]$分为不为空的任意大小块，每一个块的贡献为该块内$h$最小的位置对应的$b$，求出最大贡献和。
思路
先写出$O(n^2)$的转移方程，$f(x,y)$为区间$[x,y]$的贡献。
1 | for i←1 to n |
考虑优化这个$dp$，我们可以发现对于每个点$i$，他所控制的范围向前截止到离他最近的且$h$值比它更小的位置，即$[p+1,i]$，这一步可以用单调递增的单调栈维护每个值前面最近小于他的值。
那么如果我们对于$i$选择其对应的断点$j$落在$[p+1,i]$这一段区间里，$b[i]$的权值是一定计入$dp[i]$的，而我们只是要让这个值最大化，很明显$dp[i]=\operatorname{max}\limits_{j=p+1}^{i-1}(dp[j])+b[i]$，此时转变成一个查询区间最值的问题。
而若$i$所在的分割块的左端点在$p$的左面，即$j\in [1,p]$，那么$b[i]$一定不会计入贡献，因为该块内此时有$b$值比它更小的权值了，令$dp[i]=dp[p]$即可转移（如果令$dp[i]=max(dp[1:p])$的话可能不是合法解）。
若$i$左面没有比$h[i]$更矮的，直接讨论一下即可。
思路流程：推出来一个复杂度较差的$dp$->尝试观察性质，发现每个点的控制范围并且想到单调栈->优化转移过程。
代码
1 | //#pragma comment(linker, "/STACK:102400000,102400000") |