Educational Codeforces Round 131 (Rated for Div. 2) F.Points 线段树

作为k：此时只需要考虑 [ k − 1 , k − d ] [k - 1, k - d] [k−1,k−d]内点的数量，设为 c n t 2 cnt_2 cnt2​，则产生的贡献为 C c n t 2 2   ( c n t 1 > 1 ) = c n t 2 ∗ ( c n t 2 − 1 ) 2 C_{cnt_2}^{2}\ (cnt_1 > 1) = \frac{cnt_2 * (cnt_2 - 1)}{2} Ccnt2​2​ (cnt1​>1)=2cnt2​∗(cnt2​−1)​

作为j：此时需要考虑情况需要进行转化，即作为 j j j加入后对各个 i i i产生的影响以及同时对各个 j j j产生的影响： ∑ i = j − d j − 1 s i g n ( i ) × c n t ( j + 1 , i + d ) s i g n ( x ) = { 1 , i f   x   e x i s t s 0 , o t h e r w i s e \sum^{j - 1}_{i = j - d} sign(i) \times cnt_{(j + 1, i + d)} \\ sign(x) = \begin{cases} 1, if\ \textbf{x}\ exists\\ 0, otherwise \end{cases} i=j−d∑j−1​sign(i)×cnt(j+1,i+d)​sign(x)={1,if x exists0,otherwise​ 其中 c n t ( l , r ) cnt_{(l, r)} cnt(l,r)​表示 [ l , r ] [l, r] [l,r]内点的数量。容易发现贡献计算式中 c n t ( j + 1 , i + d ) cnt_{(j + 1, i + d)} cnt(j+1,i+d)​是一个定左端点变右端点式子。且实际上我们在权值线段树上查询的是 q u e r y ( 1 , i + d ) − q u e r y ( 1 , j ) query(1, i + d) - query(1, j) query(1,i+d)−query(1,j)，也就是 c n t ( 1 , i + d ) − c n t ( 1 , j ) cnt_{(1, i + d)} - cnt_{(1, j)} cnt(1,i+d)​−cnt(1,j)​。那么上述求和式子可以化为： ∑ i = j − d j − 1 s i g n ( i ) × ( c n t ( 1 , i + d ) − c n t ( 1 , j ) ) = ( ∑ i = j − d j − 1 s i g n ( i ) × c n t ( 1 , i + d ) ) − c n t ( j − d , j − 1 ) × c n t ( 1 , j ) \sum^{j - 1}_{i = j - d} sign(i) \times (cnt_{(1, i + d)} - cnt_{(1, j)}) = (\sum^{j - 1}_{i = j - d} sign(i) \times cnt_{(1, i + d)}) - cnt_{(j - d, j - 1)} \times cnt_{(1, j)} i=j−d∑j−1​sign(i)×(cnt(1,i+d)​−cnt(1,j)​)=(i=j−d∑j−1​sign(i)×cnt(1,i+d)​)−cnt(j−d,j−1)​×cnt(1,j)​ 如果用树状数组维护 ( 1 , x ) (1, x) (1,x)区间，那么需要将上述式继续展开： ( ∑ i = j − d j − 1 s i g n ( i ) × c n t ( 1 , i + d ) ) − ( c n t ( 1 , j − 1 ) − c n t ( 1 , j − d − 1 ) ) × c n t ( 1 , j ) (\sum^{j - 1}_{i = j - d} sign(i) \times cnt_{(1, i + d)}) - (cnt_{(1, j - 1)} - cnt_{(1, j - d - 1)}) \times cnt_{(1, j)} (i=j−d∑j−1​sign(i)×cnt(1,i+d)​)−(cnt(1,j−1)​−cnt(1,j−d−1)​)×cnt(1,j)​ 那么式子分成了两部分： ∑ i = j − d j − 1 s i g n ( i ) × c n t ( 1 , i + d ) \sum^{j - 1}_{i = j - d} sign(i) \times cnt_{(1, i + d)} ∑i=j−dj−1​sign(i)×cnt(1,i+d)​和 − c n t ( 1 , j − d − 1 ) ) × c n t ( 1 , j ) - cnt_{(1, j - d - 1)}) \times cnt_{(1, j)} −cnt(1,j−d−1)​)×cnt(1,j)​。对于前式，我们可以单独开一棵区间和线段树维护。后面式子树状数组解决。当然也可以直接权值线段树查询。

考虑如何维护 ∑ i = j − d j − 1 s i g n ( i ) × c n t ( 1 , i + d ) \sum^{j - 1}_{i = j - d} sign(i) \times cnt_{(1, i + d)} ∑i=j−dj−1​sign(i)×cnt(1,i+d)​，不难发现单点 x x x加入会对 [ x − d , 2 e 5 ] [x - d, 2e5] [x−d,2e5]区间有效点产生 + 1 +1 +1贡献。那么每次直接更新即可，注意更新时把权值线段树的叶子节点当作 T A G TAG TAG乘到区间和线段树上去，这样可以直接处理“有效点”问题。