凝聚力可以用分治吗
我不知道怎么对中间的那部分进行分治，左右两边可以做。
03-29 21:09 华北水利水电大学 C++ 发布于河南
关注
全部评论
alij
成都信息工程大学
可以证明对于选择的一个[l,r]，两个端点处一个是极值，不然总是可以减小区间长度。 有了这个之后，用线段树维护就好，令L[i]表示左边第一个大于a[i]的位置，R[i]表示右边第一个大于a[i]的位置，这个可以用单调栈求出，之后我们枚举最大值，即M=a[i]，对于j在区间[L[i]+1,i]，r=i,l=j，这时我们需要代入上式有a[i]-i+(j-a[j])，所以我们需要维护i-a[i]的最大值；对于j在区间[i+1,R[i]-1]，r=j,l=i，这时原式=a[i]+i+(-a[j]-j)，所以我们还需要维护-i-a[i]的最大值，所以使用两棵线段树进行维护即可。
相关推荐
查看3道真题和解析