[AH2017/HNOI2017]影魔

errr
这题还是很简单的
首先任何形如\([i,i+1]\)的点对显然贡献是\(p_1\)
我们下面只考虑长度大于\(2\)的区间,也就是中间跨过了一些数的点对
我们对于每个数用单调栈求出左边和右边第一个比它大的数的位置\(l_i,r_i\),
那么点对\((l_i,r_i)\)贡献是\(p_1\),而\(l_i\)和\((i+1,r_i-1)\)内的所有点的贡献都是\(p_2\),对于\(r_i\)同理
线段树上离线搞搞
复杂度\(O(nlog_2n)\)

发表评论

电子邮件地址不会被公开。 必填项已用*标注