A n=50非常小 所以直接暴力枚举 枚举每次把某个数以下的全部减完 然后看一下是否上升就行
https://codeforces.com/contest/1856/submission/217275334
B题直接 贪心 前面优先放最小的 最后一个放最大的 然后如果重复了就到前面去看能不能调整一下
https://codeforces.com/contest/1856/submission/217288823
C题 首先我们考虑最后形成的是一个什么形状 手玩后发现应该从最高的值那里开始以此递减 不够的补上 直到遇到一个不用补的 并且最后一个数字补不了
形象化的来说 假设最高点为i 则改变后的为bi ， bi-1 .... bj 且abs(bi+1 - bi) == 1
比如现在有 1，3，4
我假设现在最大值为5 ，并且从第一个位置开始
所以变化后第一个数为5 第二个数发现比4要小 （如果比4大我们直接结束了 因为你要让当前位置为某个值 他后面那个数必须得比这个值-1要大 ， 3 ， 3 操作一次只能变成4，3） 然后给他补成4 ， 到第三个数发现不用补了 所以直接break 然后算一下花费就可以了
注意如果到了最后一位发现最后一位不满足 直接break 因为不可能给最后一位补
所以最后我们二分最大值 枚举从每个位置开始是最大值 看是否满足就行
https://codeforces.com/contest/1856/submission/217291691
D题
考虑如果询问q(l , r)和q(l,r-1） 假如 二者相等 证明没有出现新的逆序队 即a【r】 为最大值 而题目恰好让我们维护的是最大值
令f(l,r) 为最大值的下标 mid = (l + r) >> 1 ;
令i为f（l , mid) j 为f（mid+1，r)
如果q(l , j)==q(l,j-1)证明a[j]是l到j的最大值 而j又是mid+1到r的最大值 所以f（l，r）=f（mid+1，r）
反之 则说明前面有比mid+1到r的最大值还大的 f（l，r）= f（l，mid）
每次转移前询问两次即可
E1 对于每个节点作为lca时统计贡献 则其贡献只取决于有多少节点大于它 多少节点小于它 并且这两部分的点一定来自于不同的子树 也就是说 要么一整颗字数都大于它 要么一整颗子树都小于它
假设大于它的点有x个 小于有y个 贡献为x*y
现在问题转化为怎么分配最大
和一定差小积大
尽可能的平均分配就行 所以应该我们要计算出所有分配的情况 然后找最平均那个
算分配情况用一个典型的背包就行
复杂度n^2
https://codeforces.com/contest/1856/submission/217350235
总结 写了四个题 d是补的 大概知道是像线段树一样二分着问下来 但是那个性质没摸出来 不知道咋转移 还是差了点意思
标签：890,bi,submission,Institute,最大值,supported,mid,1856,codeforces From： https://www.cnblogs.com/Vellichor/p/17612559.html