差分

算法 > acwing 算法差分

发布时间 : 2022-03-31 13:22

字数:2.1k 阅读 :

差分是一种和前缀和相对的策略，可以当做是求和的逆运算。

模板

一维差分

给区间[l, r]中的每个数加上c：

B[l] += c, B[r + 1] -= c

Acwing 797.差分

输入一个长度为 n 的整数序列。

接下来输入 m 个操作，每个操作包含三个整数 l,r,c表示将序列中 [l,r] 之间的每个数加上 c。

请你输出进行完所有操作后的序列。

输入格式

第一行包含两个整数 nn 和 mm。

第二行包含 nn 个整数，表示整数序列。

接下来 mm 行，每行包含三个整数 l，r，cl，r，c，表示一个操作。

输出格式

共一行，包含 nn 个整数，表示最终序列。

数据范围

1≤n,m≤100000
1≤l≤r≤n
−1000≤c≤1000
−1000≤整数序列中元素的值≤1000

输入样例：

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

输出样例：

3 4 5 3 4 2

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], b[N];

void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i ++ ) insert(i, i, a[i]);

    while (m -- )
    {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }

    for (int i = 1; i <= n; i ++ ) b[i] += b[i - 1];

    for (int i = 1; i <= n; i ++ ) printf("%d ", b[i]);

    return 0;
}

二维差分

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：

S[x1, y1] += c;
S[x2 + 1, y1] -= c;
S[x1, y2 + 1] -= c;
S[x2 + 1, y2 + 1] += c;

差分矩阵

输入一个 n 行 m 列的整数矩阵，再输入 q个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1)和 (x2,y2)表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上 c。

请你将进行完所有操作后的矩阵输出。

输入格式

第一行包含整数 n,m,q

接下来 n 行，每行包含 m 个整数，表示整数矩阵。

接下来 q 行，每行包含 5 个整数 x1,y1,x2,y2,c表示一个操作。

输出格式

共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。

数据范围

1≤n,m≤1000
1≤q≤100000
1≤x1≤x2≤n
1≤y1≤y2≤m
−1000≤c≤1000
−1000≤矩阵内元素的值≤1000

输入样例：

输出样例：

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

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], b[N][N];

void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;//a[i][j]所有右下角的 +c
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &a[i][j]);

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

    while (q -- )
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }

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

    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ ) printf("%d ", b[i][j]);
        puts("");
    }

    return 0;
}

题目

100 增减序列

题目大意

给定一个长度为 n 的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

分析

构建差分数组b[i] = a[i] - a[i - 1]
最终目的是使a数组全部一样，即b[2] 至 b[n] = 0，b[1] = a[1]为任意值，这个值就是a数组最后全部相等的值，该值的取值个数就是最终数列可能有多少种。即问：操作几次，能使 b[2] ~ b[n] 全为0，b[1]最终有几种取值。
对a数组的区间[l ,r] 操作一次，比如+1，相当于 b[l] += 1, b[r + 1] -= 1; 即改变两个b的值。PS:可以对b[n + 1]操作，此时对a数组无影响。
设b[2] ~ b[n]的正数之和为p，负数的绝对值之和为q，则要把b[2] ~ b[n] 都变为0，至少要进行操作 $max(p, q)$次，其中最多可以对b[1]进行$|p - q|$次操作，最少进行0次,即b[1]的可能取值最多为 $1 + |p - q|$种。

源代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

LL n, c, a[N];
LL p, q;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        cin >> a[i];
    }
    for(int i = 2; i <= n; i ++){
        int c = a[i] - a[i - 1];
        if(c > 0)p += c;
        else q -= c;
    }
    
    cout << max(p, q) << endl << abs(p - q) + 1;
    return 0;
}

103. 最高的牛

题目大意

有 N 头牛站成一行，被编队为 1、2、3…N，每头牛的身高都为整数。

当且仅当两头牛中间的牛身高都比它们矮时，两头牛方可看到对方。

现在，我们只知道其中最高的牛是第 P 头，它的身高是 H ，剩余牛的身高未知。

但是，我们还知道这群牛之中存在着 M 对关系，每对关系都指明了某两头牛 A 和 B 可以相互看见。

求每头牛的身高的最大可能值是多少。

分析

读入的数据之间不可能有交叉，只可能是嵌套的关系。比如a,b ; c d ；那么只可能是[a,b]包含[c,d]，或是[c,d]包含[a,b]，两个区间不能交叉
当读入区间[a,b]之后，把[a + 1, b - 1]的牛的身高全都-1，即height[a + 1] – , height[b] ++;

源代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;
const int N = 10010;

int height[N];

int main()
{
    int n, p, h, m;
    cin >> n >> p >> h >> m;
    height[1] = h;
    set<pair<int,int>> existed;
    for(int i = 0, a, b; i < m; i ++){
        cin >> a >> b;
        if(a > b)swap(a, b);
        if(!existed.count({a, b})){
            existed.insert({a, b});
            //把a,b中间，即[a + 1,b - 1]里的牛的身高减一
            height[a + 1] --, height[b] ++;
        }
    }
    for (int i = 1; i <= n; i ++ ){
        height[i] += height[i - 1];
        cout << height[i] << endl;
    }
    return 0;
}

1715. 桶列表

题目大意：

每头牛在某个区间内需要一定数量的桶

问最少需要多少桶能满足所有牛的需要

思路：

差分、求和、求最小值

代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int b[N];

int main()
{
    cin >> n;

    while (n -- )
    {
        int l, r, c;
        cin >> l >> r >> c;
        b[l] += c, b[r] -= c;
    }

    int res = 0, sum = 0;
    for (int i = 1; i <= 1000; i ++ )
    {
        sum += b[i];
        res = max(res, sum);
    }

    cout << res << endl;
    return 0;
}

1987. 粉刷栅栏

题目大意：

一头牛绑着个粉刷，在栏杆走，给了每次从当前位置走的距离和方向，问走完以后有多长的距离是刷过两次以上的

思路：

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

int main()
{
    // b 表示差分数组
    map<int,int> b;
    int n;
    cin >> n;
    int x = 0, y;
    char s[2];
    while(n --){
        //读入移动的距离以及方向
        scanf("%d%s",&y,s);
        if(*s == 'R'){
            //假如当前是1，往右走3，则1-4之间是走过的，4之后是未走过的，b[1]++,b[4]--
            b[x] ++;
            b[x + y] --;
            x += y;
        }
        else{
            b[x - y] ++;
            b[x] --;
            x -= y;
        }
    }
    
    int last, res = 0, sum = 0;
    for(auto [x, v] : b){
        if(sum >= 2)res += x - last;
        sum += v;
        //记录上次停下的位置
        last = x;
    }
    cout << res << endl;
    return 0;
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1149440709@qq.com