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是补的 大概知道是像线段树一样二分着问下来 但是那个性质没摸出来 不知道咋转移 还是差了点意思
- Constructor Codeforces Institute supported Roundconstructor codeforces institute supported 题解constructor codeforces institute educational codeforces round rated codeforces round 911 div codeforces round 887 div codeforces round 864 div codeforces round 863 div codeforces round 915 div codeforces round 913 div codeforces round 917 div