势能线段树浅析：link

这里我们介绍一下经典例题以及做法。

模板做法：

由于势能线段树的性质，某些区间的值在减小一定次数之后会到达一个定值（或某区间修改次数存在限制），所以我们在递归调用线段树只需要判断左区间和右区间是否还需要修改权值。最后我们只需要在根节点进行修改,然后把需要维护的答案上传即可。

参考代码（修改部分）：

void Update(int k,int x ,int y ,int v){
    int l = tree[k].Left , r = tree[k].Right;
    if(l == r){
        tree[k].sum = ...(题目要求);
        return ;
    }
    int mid = l + r >> 1;
    if(x <= mid && 左区间有能修改的结点) Update(k << 1 , x , y , v);
    if(y > mid && 右区间有能修改的结点) Update(k << 1 | 1 , x , y , v);
    tree[k].sum = tree[k << 1].sum + tree[k << 1 | 1].sum;
}

这个模板其实非常万能，很多势能线段树的差别就在于这两句：

    if(x <= mid && 左区间有能修改的结点) Update(k << 1 , x , y , v);
    if(y > mid && 右区间有能修改的结点) Update(k << 1 | 1 , x , y , v);

具体情况请看下文分析。

经典例题：

\(No.1 \)

P4145 上帝造题的七分钟 2 / 花神游历各国

这题的题意即是 区间开方 区间求和 。

区间求和很简单，普通线段树在 \(O(\log n)\) 的时间内就能完成一次操作。

对于区间开方，我们需要探究一下开方的性质。由于 \(a_i\) 最大不会超过 \(10^{12}\) , 所以每一个点最多操作六次就能变成 1 。而变成 1 之后再开方就还是 1 了，无需再修改 。

所以我们在这里对能修改的结点定义为：权值大于 1 的结点。即：

    if(x <= mid && tree[k << 1].maxi > 1) Update(k << 1 , x , y);
    if(y > mid && tree[k << 1 | 1].maxi > 1) Update(k << 1 | 1 , x , y);

总复杂度：\(O(km\log n)\) 。这里的 \(k \leqslant 6\) 。

势能线段树完整 Code ：link

树状数组完整 Code ：link

\(No.2\)

CF438D The Child and Sequence

这题的题意是 单点修改 区间取模 区间求和。

单点修改和区间求和这里不再赘述，我们特别讲一下区间取模。

对于一个点权 \(a_i\) 和模数 \(mod\) ， 它们的大小关系有两种情况。

若 \(mod > a_i\) ， 则 \(a_i\) 这点无需修改 ， \(a_i\) % \(mod\) 依然等于 \(a_i\)。

若 \(mod < a_i\) ， 则 \(a_i\) 这点需要修改。但是我们发现它的修改次数有巧妙的性质：

令 \(nxt = a_i\) % \(mod\) ， 若想让 \(nxt\) 最大，则 \(mod = \lfloor \frac{a_i}{2} \rfloor + 1\) 。此时最大的 \(nxt\) 为 \(\lfloor \frac{a_i - 1}{2} \rfloor\) 。由此可见，每次取模，结点权值至少减少一半，所以一个结点最多修改 \(\log n\) 次。这个思想有点类似于启发式合并。

所以我们在这里对能修改的结点定义为：权值大于等于 \(mod\) 的结点。即：

    if(x <= mid && tree[k << 1].maxi >= v) Update(k << 1 , x , y , v);
    if(y > mid && tree[k << 1 | 1].maxi >= v) Update(k << 1 | 1 , x , y , v);

时间复杂度为：\(O(n \log^2n)\) 。

势能线段树完整Code：link

\(No.3\)

CF920F SUM and REPLACE

题意是 区间改 \(a_i\) 为 \(\tau(i)\) ， 区间求和 。

这题只需要先线性筛 \(\tau(i)\) 即可。线性筛详见 link 。

然后根据势能线段树可得：

	if(x <= mid && tree[k << 1].maxi > 2) Update(k << 1 , x , y);
	if(y > mid && tree[k << 1 | 1].maxi > 2) Update(k << 1 | 1 , x , y);

势能线段树完整Code：link