【算法/训练】：前缀和&&差分

🚀 前言：

前面我们已经通过  【算法/学习】前缀和&&差分-CSDN博客  学习了前缀和&&差分的效相关知识，现在我们开始进行相关题目的练习吧

1. 校门外的树

思路：给[0, n]的数组都标记为1，然后输出m行范围，[l, r]都标记为0。

AC代码如下：

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main()
{
    int n, m;
    cin>>n>>m;
    for(int i = 0; i <= n; i++) a[i] = 1;
    int l, r;
    for(int i = 1; i <= m; i++)
    {
        cin>>l>>r;
        for(int j = l; j <= r; j++) a[j] = 0;
    }
    int cnt = 0;
    for(int i = 0; i <= n; i++) {
        if(a[i] == 1) cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}

2. 值周

思路：

该题与上题意思相同，但是数据范围更大，因此我们不能使用上面的方法，我们可以使用前缀和，使让数组a内的数据先初始化为0，然后对[ l, r ]进行操作，a[l]--, a[r + 1]++，然后操作M次后，再 a[i] += a[i - 1];这样可以使得每个区域内的数都小于0.

AC代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e7 + 10;

int a[N];

int main()
{
    int n, m;
    cin >> n >> m;
    int l, r;
    for (int i = 0; i < m; i++){
        cin >> l >> r;
        a[l]--, a[r + 1]++;  //前缀和，l-r标记为-1，r + 1又标记为1
    }
    for (int i = 1; i <= n; i++)
    {
        a[i] += a[i - 1];
    }
    int ans = 0;
    for (int i = 0; i <= n; i++)
    {
        if (a[i] >= 0) ans++;
    }
    cout << ans << endl;
    return 0;
}

3. 字母收集

思路：

     对输入的字符矩阵我们按照要求将其转换为数字分数，由于只能往下和往右走，因此走到（i，j）的位置要就是从（i - 1， j）往下走，或者是从(i，j  - 1)的位置往右走，由于我们要使得路程遍历积分最多，则应该从积分多的位置过来，

    故（i，j）位置的积分应该为a[ i ][ j ] = max(a[ i - 1 ][ j ], a[ i ][ j - 1 ]) + a[ i ][ j ];

    但是上面仅对于（i >= 1 && j >= 1）成立，对于第一行和第一列我们应该特殊处理，利用前缀和的知识可以求得，走到第一列的第i个位置最多能拿的积分以及走到第一行的第j个位置最多能拿的积分，然后我们就可以按照a[ i ][ j ] = max(a[ i - 1 ][ j ], a[ i ][ j - 1 ]) + a[ i ][ j ]的方法遍历每个节点即可

#include <iostream>
using namespace std;

const int N = 1005;
int a[N][N];

int main() {
	int n, m;
	cin >> n >> m;
	char ch;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			cin >> ch;
			if (ch == 'l') a[i][j] = 4;
			else if (ch == 'o') a[i][j] = 3;
			else if (ch == 'v') a[i][j] = 2;
			else if (ch == 'e') a[i][j] = 1;
			else a[i][j] = 0;
		}
	}

for (int i = 1; i < n; i++) a[i][0] = a[i - 1][0] + a[i][0]; 
for (int j = 1; j < m; j++) a[0][j] = a[0][j - 1] + a[0][j]; 

	for (int i = 1; i < n; i++){
		for (int j = 1; j < m; j++){
			a[i][j] = max(a[i - 1][j], a[i][j - 1]) + a[i][j];
		}
	}

	cout << a[n - 1][m - 1] << endl;
	return 0;
}

4. [CQOI2009]中位数图

思路：

🔥1.由于是求中位数是b的连续子序列，那么我们只要找到一串连续的数，里面包含数b，且大于b的数的数目与小于b的数的数目相等，才是我们要找的序列。
🔥2.由于数据范围给的比较大，我们可以简化一下，把比b大的数直接赋值为1，小的就赋值为-1.
同时，我们再用一个sum来求和，sum往一边统计的时候，当sum==0的时候说明大于b的数的数目与小于b的数的数目相等，也就是我们找到了一个序列。
🔥3.那么两边都有的情况怎么考虑呢？我们可以往一边记录，用一个num数组来记录sum的加减情况。
我们可以来看一下题目的样例：
{5，7，2，4，3，1，6}->{1，1，-1，4，-1，-1，1}
🔥往左遍历：
      1.sum+=-1-->sum==-1,可以这样，num[n+sum]+=1,也就是左边有一个比b小的情况加1.
       2.sum+=1->sum==0,num[n+sum]+=1，左边刚好找到一个成功的序列，ans++.
      3.sum+=1-->sum==1,num[n+sum]+=1,左边有一个比b大的情况加一。
🔥现在往右遍历：
      先初始化sum=0.
      然后sum+=-1->sum==-1,右边找到了一个比b小的数，而num[n+1]表示左边有一个比b小的情况的数目，也就是num[n-sum],我们可以用ans+=num[n-sum]。
后面同理，最后ans==4.（ans初始值为1，因为自己本身也是一个序列）

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

const int N = 1e6 + 10;
ll a[N], s[N];

int main()
{
	int n, b;
	cin >> n >> b;
	int pos, x;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		if (a[i] > b)a[i] = 1;
		else if (a[i] < b) a[i] = -1;
		else pos = i;//标记中位数的位置
	}

	ll sum = 0, ans = 1; //自己也算一个
	for (int i = pos - 1; i >= 1; i--) {
		sum += a[i];
		s[n + sum]++; //记录左边和为sum的数量
		if (!sum) ans++; //sum为零就说明小于b的数的数量于大于b的数量相同
	}
	sum = 0; //再往右遍历，同时与左边比较
	for (int i = pos + 1; i <= n; i++) {
		sum += a[i];
		ans += s[n - sum]; //加上左边与其互补的数量
		if (!sum) ans++;
	}
	cout << ans << endl;
}