【BZOJ2727】【HNOI2012】双十字

首先把每个点向上向下向左向右能够扩展的最长距离\(u_i,d_i,l_i,r_i\)求出来。那么一个点作为十字中心的最长长度\(len_i\)为\(min(l_i,r_i)\)。

那么如果我们枚举两个十字的中心\(p,q\),会出现两种情况:

若\(len_p\ge len_q\),那么共有\(\frac{len_q(len_q-1)}{2}u_p d_q\)种双十字

若\(len_p< len_q\),那么共有\(\sum_{i=1}^{len_p}(len_q-i)u_p d_q=len_pu_p len_q d_q-\frac{(len_p)(len_p+1)}{2}u_p d_q\)种双十字

那么用树状数组分别维护一下每个点上面的\(\sum{u_p},\sum{len_p u_p},\sum{\frac{(len_p)(len_p+1)}{2}u_p}\)即可

说点什么

您将是第一位评论人!

提醒
wpDiscuz