Luogu【算法2-1】前缀和、差分与离散化

Problem A

思路分析

简单的前缀和板子，不多说。

AC代码

#includeusing namespace std;
using ll =unsigned long long;
ll n, m;
ll a[200000];
ll pre[200000], sum[200000];
int main() {cin >> n;
	for (ll i = 1; i <= n; i++) {cin >> a[i];
		pre[i] = a[i] + pre[i - 1];
	}
	cin >> m;
	for (ll i = 1; i <= m; i++) {ll l = 0, r = 0;
		cin >> l >> r;
		sum[i] = pre[r] - pre[l - 1];
	}
	for (ll i = 1; i <= m; i++) {cout << sum[i] << endl;
	}
	return 0;
}

Problem B

其实是二维前缀和的板子，这里给出几份代码，看看不同的思路（大多都是细节上处理的方法不同）。

AC代码

CODE1

#include#include
using namespace std;
using ll = long long;
int n, ans = -99999999;
int squ[130][130];
int sum[130][130];
int lin[130][130];
int main() {cin >> n;
	for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cin >> squ[i][j];
			//lin[i][j]表示的是第i行前j个（其实也就是第j列）数字的和
			lin[i][j] = lin[i][j - 1] + squ[i][j];
			//sum[i][j]表示的是以第1行第1个数字为左上角，以第i行第j个数字为右下角的矩形的面积。
			sum[i][j] = sum[i - 1][j] + lin[i][j];
		}
	}
	//分别枚举左上角的坐标(x1,y1)和右下角(x2,y2)的坐标。
	for (int x1 = 1; x1 <= n; x1++) {for (int y1 = 1; y1 <= n; y1++) {for (int x2 = 1; x2 <= n; x2++) {for (int y2 = 1; y2 <= n; y2++) {if (x2 < x1||y2continue;
					}
					ans = max(ans, sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] +sum[x1-1][y1-1]);
				}
			}
		}
	}
	cout << ans;
	return 0;
}

可能有人对 s u m [ x 2 ] [ y 2 ] − s u m [ x 2 ] [ y 1 − 1 ] − s u m [ x 1 − 1 ] [ y 2 ] + s u m [ x 1 − 1 ] [ y 1 − 1 ] sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] +sum[x1-1][y1-1] sum[x2][y2]−sum[x2][y1−1]−sum[x1−1][y2]+sum[x1−1][y1−1]为什么是以 ( x 1 , y 1 ) (x_1,y_1) (x1​,y1​)为左上角，以 ( x 2 , y 2 ) (x_2,y_2) (x2​,y2​)为右下角的矩形的面积有点疑惑。画个图解释一下：

这下应该能看懂了吧qwq。

CODE2

#includeusing namespace std;
using ll=long long;
int a[125][125],mat[125][125];
int query(int i,int j,int k,int m){ //还是跟上面的操作一样
    return mat[k][m]-mat[k][j-1]-mat[i-1][m]+mat[i-1][j-1];
}
int main(){ int n;cin>>n;
    for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j];
            //预处理出以(i,j)为右下角的矩形的面积，画画图就懂了
            mat[i][j]=mat[i-1][j]+mat[i][j-1]-mat[i-1][j-1]+a[i][j];
        }
    }
    int ans=-1e9;
    //枚举左上角(i,j)，右下角(k,m)
    for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ //注意k>=i,m>=j
            for(int k=i;k<=n;k++){ for(int m=j;m<=n;m++){ ans=max(ans,query(i,j,k,m));
                }
            }
        }
    }
    cout< 
CODE3
 
实际上是在枚举时优化了一下，降低时间复杂度。
 
#includeusing namespace std;
using ll=long long;
int a[125][125],mat[125][125];
int query(int i,int j,int k,int m){ return mat[k][m]-mat[k][j-1]-mat[i-1][m]+mat[i-1][j-1];
}
int main(){ int n;cin>>n;
    for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j];
            mat[i][j]=mat[i-1][j]+mat[i][j-1]-mat[i-1][j-1]+a[i][j];
        }
    }
    int ans=-1e9,sum;
    //这里改成了枚举矩形的上下边i与j
    for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ sum=0;
            //k枚举的是第几列，从左往右扫描每一列的面积，并加到sum中
            for(int k=1;k<=n;k++){ sum+=query(i,k,j,k);
                //如果sum>ans，说明在以i行为上界，j行为下界的，并且右界限为k的构成的连续矩形面积（即sum）更大，更新ans
                if(sum>ans)ans=sum;
                //如果sum<0，那么只能另开一段，置sum为0
                if(sum<0)sum=0;
            }
        }
    }
    cout< 
或者可以理解成是矩阵压缩，可以看看题解的第一篇，本质其实是一样的。
P1719 最大加权矩形
 
Problem C
 
思路分析
 
差分的板子题，但是我经常忘记怎么操作了，贴上证明。
这里贴的是GoldenFishX大佬的博客，可以看看（大佬如果觉得侵权，联系我删除即可qwq）。
 
AC代码
 
#includeusing namespace std;
using ll = long long;
ll p, n, a[5000500], d[5000500];
ll x, y, z, ans=9999999999;
int main() {cin >> n >> p;
	for (ll i = 1; i <= n; i++) {cin >> a[i];
		//求出差分数组
		d[i] = a[i] - a[i - 1];
	}
	for (ll i = 1; i <= p; i++) {cin >> x >> y >> z;
		//上面讲得很清楚了
		d[x] += z;
		d[y + 1] -= z;
	}
	for (ll i = 1; i <= n; i++) { //差分的性质：a[i]=d[i]+d[i-1]+d[i-2]+······+d[1]
		a[i] = a[i - 1] + d[i];
		ans = min(ans, a[i]);
	}
	cout << ans;
	return 0;
}
 
Problem D
 
这题其实可以暴力模拟水过去，但实际上正解是二维差分。（补学一下qwq）。
设数组 
     
      
       
       
         a 
        
       
      
        a 
       
      
    a的差分数组为 
     
      
       
       
         b 
        
       
      
        b 
       
      
    b，则：
 b 
         
        
          [ 
         
        
          [ 
         
        
          i 
         
        
          ] 
         
        
          [ 
         
        
          j 
         
        
          ] 
         
        
          = 
         
        
          a 
         
        
          [ 
         
        
          i 
         
        
          ] 
         
        
          [ 
         
        
          j 
         
        
          ] 
         
        
          − 
         
        
          a 
         
        
          [ 
         
        
          i 
         
        
          − 
         
        
          1 
         
        
          ] 
         
        
          [ 
         
        
          j 
         
        
          ] 
         
        
          − 
         
        
          a 
         
        
          [ 
         
        
          i 
         
        
          ] 
         
        
          [ 
         
        
          j 
         
        
          − 
         
        
          1 
         
        
          ] 
         
        
          + 
         
        
          a 
         
        
          [ 
         
        
          i 
         
        
          − 
         
        
          1 
         
        
          ] 
         
        
          [ 
         
        
          j 
         
        
          − 
         
        
          1 
         
        
          ] 
         
        
       
         b[[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1] 
        
       
     b[[i][j]=a[i][j]−a[i−1][j]−a[i][j−1]+a[i−1][j−1].
（偷懒了，直接贴书上的内容qwq）
 
 
 
可以看到(a)，(b)图中，右下角的矩形中的各点都+1了，可以试着结合一维差分的证明理解一下wsm。©，(d)图其实就是相同的操作罢了。
 
AC代码
 
#includeusing namespace std;
using ll=long long;
const int MAXN=1e3+10;
int mat[MAXN][MAXN];
int main(){ int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++){ int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        //上面提到的操作
        mat[x1][y1]++;
        mat[x2+1][y1]--;
        mat[x1][y2+1]--;
        mat[x2+1][y2+1]++;
    }
    for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ //求前缀和，处理出每个点的值
            mat[i][j]+=mat[i-1][j]+mat[i][j-1]-mat[i-1][j-1];
            cout< 
Problem E
 
实际上这是一道离散化的题目，但是我当初做的时候还不会离散化qwq，看了题解区大佬的绝妙思路：
大佬的题解
可以发现，覆盖的范围是一样的，那么我们可以这样操作：
1、将起点和终点排个序。
2、将他们按照从小到大的顺序一一匹配，计算长度。
3、如果有重复的覆盖范围，减去即可。（也就是当前的终点坐标比下一个的起点坐标大时）
 
AC代码
 
#include#include
using namespace std;
using ll = long long;
int n;
ll a[20200], b[20200], l;
int main() {cin >> n; 
	for (int i = 1; i <= n; i++) {cin >> a[i] >> b[i];
	}
	sort(a + 1, a + 1 + n);
	sort(b + 1, b + 1 + n);
	for (int i = 1; i <= n; i++) {l += b[i] - a[i];
		//注意iif (b[i] > a[i + 1]) {l -= b[i] - a[i + 1];
			}
		}
	}
	cout << l;
	return 0;
}
 
Problem F
 
二维前缀和的练习题，不解释了qwq。
 
AC代码
 
#includeusing namespace std;
using ll = long long;
ll n, m, c;
ll map[1010][1010], sum[1010][1010], maxn = -999999999, nx,ny;
int main() {cin >> n >> m >> c;
	for (ll i = 1; i <= n; i++) {for (ll j = 1; j <= m; j++) {cin >> map[i][j];
			//求前缀和
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + map[i][j];
		}
	}
	for (int i = c; i <= n; i++) {for (int j = c; j <= m; j++) { //枚举以(i,j)为右下角、边长为c的正方形的面积，注意更新坐标
			if (sum[i][j] - sum[i - c][j] - sum[i][j - c] + sum[i - c][j - c] > maxn) {maxn = sum[i][j] - sum[i - c][j] - sum[i][j - c] + sum[i - c][j - c];
				nx = i - c + 1;
				ny = j - c + 1;
			}
		}
	}
	cout << nx << " " << ny;
	return 0;
}