高阶差分
学习高阶差分之前,你需要先学习差分

高阶差分简介

记 $\Delta f(x)=f(x+1)−f(x)$。称 $\Delta f(x)$ 为 $f(x)$ 的一阶差分。

同理:记 $\Delta^n f(x)=\Delta^{n−1}f(x+1)−\Delta^{n−1}f(x)$ 。称 $\Delta^nf(x)$ 为 $f(x)$ 的 $n$ 阶差分。

高阶差分公式推导

以二阶差分为例:洛谷:P4231 三步必杀

$N$个柱子排成一排,一开始每个柱子损伤度为$0$。

接下来勇仪会进行$M$次攻击,每次攻击可以用$4$个参数$l$,$r$,$s$,$e$来描述:

表示这次攻击作用范围为第$l$个到第$r$个之间所有的柱子(包含$l$,$r$),对第一个柱子的伤害为$s$,对最后一个柱子的伤害为$e$。

攻击产生的伤害值是一个等差数列。若$l=1$,$r=5$,$s=2$,$e=10$,则对第$1 \sim 5$个柱子分别产生$2,4,6,8,10$的伤害。

需要的是所有攻击完成之后每个柱子的损伤度。

设$a$表示原数组,$b$表示一阶差分,$c$表示二阶差分。公差$d=\frac{e-s}{r-l}$

根据题意,当我们进行了一次修改,可得:

$$a_i=a_i+s+d(i-l)$$

$$a_{i-1}=a_{i-1}+s+d(i-1-l)$$

根据差分定义,得到:

$$\begin{aligned}b_i&=a_i-a_{i-1}\\&=b_i+d\end{aligned}$$

$$\begin{aligned}b_{i-1}=b_{i-1}+d\end{aligned}$$

此时,如果我们把$b_i$看做初始数组,那么我们就可以按照普通的差分做法再做一遍。这就是二阶差分。

再次根据差分定义,得到:
$$\begin{aligned}c_i&=b_i-b_{i-1}\\&=c_l\end{aligned}$$

但是我们要注意端点情况:

$$\begin{aligned}b_l&=a_l+s-a_{l-1}\\&=b_l+s\end{aligned}$$

$$\begin{aligned}b_{r+1}&=a_{r+1}-a_r-e\\&=b_{r+1}-e\end{aligned}$$

$$\begin{aligned}c_l&=b_l+s-b_{l-1}\\&=c_l+s\end{aligned}$$

$$\begin{aligned}c_{l+1}&=b_{l+1}+d-b_l-s\\&=c_{l+1}+d-s\end{aligned}$$

$$\begin{aligned}c_{r+1}&=b_{r+1}-e-b_r-d\\&=c_{r+1}-e-d\end{aligned}$$

$$\begin{aligned}c_{r+2}&=b_{r+2}-b_{r+1}+e\\&=c_{r+2}+e\end{aligned}$$

所以我们每次只需要处理$c_i$数组的五种情况,修改四个点的值即可,统计时求两遍前缀和即可。

代码

这是上面题目的代码,实现起来很简单,$a_i,b1_i,b2_i$分别对应上面的$a_i,b_i,c_i$。

Fast 命名空间中包括快读、快输、各种宏定义,不会影响代码阅读,您可以在左侧栏文章《代码模板》中查看具体内容。

#include<bits/stdc++.h>
using namespace std;
namespace Fast{...}
using namespace Fast;
ll a[M],b1[M],b2[M],n,m,l,r,s,e,ans,maxn;
int main(){
    read(n,m);
    while(m--){
        read(l,r,s,e);
        int d=(e-s)/(r-l);
        b2[l]=b2[l]+s;
        b2[l+1]=b2[l+1]+d-s;
        b2[r+1]=b2[r+1]-e-d;
        b2[r+2]=b2[r+2]+e;
    }
    for(int i=1;i<=n;i++){
        b1[i]=b1[i-1]+b2[i];
    }
    for(int i=1;i<=n;i++){
        a[i]=a[i-1]+b1[i];
        ans^=a[i];
        maxn=Max(maxn,a[i]);
    }
    print(ans,maxn);
    return 0;
}
文章标题:高阶差分
文章链接:https://www.laoguantx.top/%e9%ab%98%e9%98%b6%e5%b7%ae%e5%88%86.html
文章内容仅供参考,其中可能会有部分内容参考、引用其他网站,转发请务必标注作者为 “老官童鞋gogo” ,原文链接为 https://www.laoguantx.top/%e9%ab%98%e9%98%b6%e5%b7%ae%e5%88%86.html 。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇