区间问题

线性差分：植树节

题目描述

植树节快要到了，学校要组织志愿者去给树苗浇水。

有一排树苗，编号依次是 0, 1, 2, ... 。

现有 ​n 个志愿者去给树苗浇水，第 ​i 个志愿者选定了一个区间 ​[a_i, b_i]，表示第 ​i 个志愿者将区间 ​[a_i, b_i] 内的每一棵树都浇一次水。

例如某个志愿者选择的浇水区间为 ​[4, 9]，表示他将给编号为 4, 5, 6, 7, 8, 9 的树各浇水一次。

当所有的志愿者完成各自所选区间的浇水后，可能有些树苗被不同的志愿者浇水多次，也可能有的树苗一次也没被浇过水。

请你求出浇水最多的树苗被浇了多少次。

输入描述

• 第 1 行，一个整数 ​n，表示志愿者的人数。
• 第 2 行到第 ​n + 1 行，每行两个整数 ​a_i, b_i (​i = 0, 1, 2, ... , n-1)，表示志愿者 ​i 选择的浇水区间。

输出描述

输出 1 行，1 个整数，表示浇水最多的树苗被浇水的次数。

输入样例 1

4
0 2
2 4
1 4
6 7

输出样例 1

3

样例说明

第 4 名志愿者给编号 6, 7 的树苗浇水；编号 0 到 7 的树被浇水的次数依次为：1, 2, 3, 2, 2, 0, 1, 1。 所以，被浇水次数最多的是编号为 2 的树，被浇水 3 次。

输入样例 2

4
1000000 1000000
1000000 1000000
0 1000000
1 1000000

输出样例 2

4

数据范围

• 对于所有的数据：​n \leq 10^5，​0 \leq a_i \leq b_i \leq 10^6。

解题思路（差分）

差分思想就是区间修改时只修改 ​l 和 ​r+1 两个元素。其公式可以表示为 b[i]=a[i]-a[i-1] ，所以不难理解为什么时 ​r+1 了，因为 i 代表的是 i 和 i-1 之间的差值。

这个题让求被浇水最多的树。那就转换成了求哪个差分数组最大。

代码

#include<bits/stdc++.h>
#define ll long long
#define mem(x,y) memset(x,y,sizeof(x))
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e6+5;
int n,a[N],b[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        a[l]++;    //a[l]-a[l-1]=1
        a[r+1]--;  //a[r+1]-a[r]=-1, 因为区间内+1
    }
    for(int i=0;i<=1e6;i++){
        b[i]=b[i-1]+a[i];    //求差分前缀和，判断最大值
    }
    int ans=0;
    for(int i=1;i<=1e6;i++){
        ans=max(b[i],ans);
    }
    cout<<ans;
    return 0;
}

二维差分：地毯

题目描述

在 ​n\times n 的格子上有 ​m 个地毯。

给出这些地毯的信息，问每个点被多少个地毯覆盖。

输入格式

第一行，两个正整数 ​n,m。意义如题所述。

接下来 ​m 行，每行两个坐标 ​(x_1,y_1) 和 ​(x_2,y_2)，代表一块地毯，左上角是 ​(x_1,y_1)，右下角是 ​(x_2,y_2)。

输出格式

输出 ​n 行，每行 ​n 个正整数。

第 ​i 行第 ​j 列的正整数表示 ​(i,j) 这个格子被多少个地毯覆盖。

样例 #1

样例输入 #1

5 3
2 2 3 3
3 3 5 5
1 2 1 4

样例输出 #1

0 1 1 1 0
0 1 1 0 0
0 1 2 1 1
0 0 1 1 1
0 0 1 1 1

提示

样例解释

覆盖第一个地毯后：

覆盖第一、二个地毯后：

覆盖所有地毯后：

数据范围

对于 ​20\% 的数据，有 ​n\le 50，​m\le 100。

对于 ​100\% 的数据，有 ​n,m\le 1000。

解题思路（二维差分）

这是一个二维的图，所以其实和线性差分差不多。直接附上代码吧。

#include<bits/stdc++.h>
#define ll long long
#define mem(x,y) memset(x,y,sizeof(x))
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1005;
int n,m,a[N][N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int X1,X2,Y1,Y2;
        cin>>X1>>Y1>>X2>>Y2;
        a[X1][Y1]++;
        a[X2+1][Y1]--;
        a[X1][Y2+1]--;
        a[X2+1][Y2+1]++;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}