智商恢复训练(前缀和与差分)

阳光穿透心脏的1/2处 2021-09-17 23:26 309阅读 0赞

**1**.一维前缀和，略  
**2**.二维前缀和  
可以通过画一个矩阵得出代数意义  
 f \[ i \] \[ j \] = f \[ i − 1 \] \[ j \] + f \[ i \] \[ j − 1 \] − f \[ i − 1 \] \[ j − 1 \] + a \[ i \] \[ j \] f\[i\]\[j\]=f\[i−1\]\[j\]+f\[i\]\[j−1\]−f\[i−1\]\[j−1\]+a\[i\]\[j\] f\[i\]\[j\]=f\[i−1\]\[j\]\+f\[i\]\[j−1\]−f\[i−1\]\[j−1\]\+a\[i\]\[j\]  
求二维前缀和的方法

#define rep(i,a,n) for (int i=a;i<n;i++)
    	rep(i,0,n)
    	rep(i,0,m)
    	f[i][j] += f[i-1][j] + f[i][j-1] - f[i-1][j-1];

求某一个矩形的方法  
 f \[ i \] \[ j \] − f \[ i − r \] \[ j \] − f \[ i \] \[ j − r \] + f \[ i − r \] \[ j − r \] f\[i\]\[j\] - f\[i-r\]\[j\] - f\[i\]\[j-r\] +f\[i-r\]\[j-r\] f\[i\]\[j\]−f\[i−r\]\[j\]−f\[i\]\[j−r\]\+f\[i−r\]\[j−r\]（加上被算2次的部分面积）

例题  
**bzoj 1218 \[HNOI2003\]激光炸弹**  
裸的二维前缀和

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    
    int n,r;
    int x,y,w;
    int f[5010][5010];
    int main(int argc, char const *argv[])
    { 
    	scanf("%d%d",&n,&r);
    	int N,M;
    	N = r,M = r;
    	rep(i,0,n)
    	{ 
    		scanf("%d%d%d",&x,&y,&w);
    		x++,y++;
    		f[x][y] = w;
    		N = max(N,x);
    		M = max(M,y);
    	}
    	rep(i,1,N+1)
    	rep(j,1,M+1)
    	{ 
    		f[i][j] += f[i-1][j] + f[i][j-1] - f[i-1][j-1];
    	}
    	int ans = 0;
    	rep(i,r,N+1)
    	rep(j,r,M+1)
    		ans = max(ans,f[i][j] - f[i-r][j] - f[i][j-r] + f[i-r][j-r]);
    	printf("%d\n",ans);	
    	return 0;
    }

**1**.差分是前缀和的逆运算，原数组可以通过前缀和求出  
**2**.序列A的区间 \[ L , R \] \[ L , R \] \[L,R\]\[L,R\] \[L,R\]\[L,R\]加 d d d，也就是把 A l , A l + 1 . . . . A r A\_l,A\_\{l+1\}....A\_r Al,Al\+1....Ar都加上d，其实就是它的差分序列 B B B中， B l + d , B r + 1 − d B\_\{l\}+d,B\_\{r+1\}−d Bl\+d,Br\+1−d，其他的位置不变。

**例题**  
**BZOJ 3043 IncDec Sequence**  
贪心加差分

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    typedef long long ll;
    
    const int maxn = 1e5+100;
    
    int n;
    ll a[maxn];
    ll b[maxn];
    int main(int argc, char const *argv[])
    { 
    	scanf("%d",&n);
    	rep(i,1,n+1)
    	{ 
    		scanf("%lld",&a[i]);
    		b[i] = a[i]-a[i-1];
    	}
    	ll pos,neg;
    	pos = 0,neg = 0;
    	rep(i,2,n+1)
    	{ 
    		if(b[i] > 0)
    			pos += b[i];
    		else
    			neg -= b[i];
    	}
    	ll ans1,ans2;
    	ans1 = max(pos,neg);
    	ans2 = abs(pos-neg)+1;
    	printf("%lld\n%lld\n",ans1,ans2);
    	return 0;
    
    }