差分

发布于 2018-12-22  304 次阅读


坑不只占了一年么

感谢Herself32推荐的模板题

差分以前缀和为基础(前缀差?),可以实现O(1)修改,O(n)查询。

例题 洛谷P2367 语文成绩

题目背景

语文考试结束了,成绩还是一如既往地有问题。

题目描述

语文老师总是写错成绩,所以当她修改成绩的时候,总是累得不行。她总是要一遍遍地给某些同学增加分数,又要注意最低分是多少。你能帮帮她吗?

//这又跟神器有什么关系呢?神说:呵呵。

//因为n和p的范围比较大 建议C++选手使用scanf读入.

//同时建议写读入优化....

//最后一个点,亲测pas读入800+ms,c/C++的scanf 1200+ms,所以这个点的时限改为2s

输入输出格式

输入格式:

第一行有两个整数n,p,代表学生数与增加分数的次数。

第二行有n个数,a1~an,代表各个学生的初始成绩。

接下来p行,每行有三个数,x,y,z,代表给第x个到第y个学生每人增加z分。

输出格式:

输出仅一行,代表更改分数后,全班的最低分。

输入输出样例

输入样例#1:
3 2
1 1 1
1 2 1
2 3 1
输出样例#1:
2

说明

对于40%的数据,有n<=1000

对于60%的数据,有n<=10000

对于80%的数据,有n<=100000

对于100%的数据,有n<=5000000,p<=n,学生初始成绩<=100,z<=100

解法

cin + 差分

什么是差分

我们有两个数组a[5] = {1,3,5,2,4};,A[5]。

我们让A存储a数组中,每相邻两个数的差。即A[i] = a[i] - a[i - 1]

于是 两个数组对应如下

数组 column1 column2 column3 column4 column5
a 1 3 5 2 4
A 1 2 2 -3 2

把a[2]到a[4]都加5,再预处理A[i] = a[i] - a[i - 1]

于是 两个数组对应如下

数组 column1 column2 column3 column4 column5
a 1 8 10 7 4
A 1 7 2 -3 -3

我们发现A数组中只有A[2]和A[4+1]的数变化。(等式的性质)

想想为什么吧

于是,我们反推,只O(1)修改A数组的两个值,之后便可O(n)咨询出a数组的值。

修改

A[l] += k;
A[r + 1] -= k;

查询

for (int i = 1; i <= n; i++)
{
    a[i] = a[i - 1] + A[i];
    cout << a[i] << " ";
}

模板代码

#include <iostream>
using namespace std;
int a[1000], A[1000];
int n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        A[i] = a[i] - a[i - 1];
    }
    char cmd;
    while (true)
    {
        cin >> cmd;
        switch (cmd)
        {
        case 'p':
            int l, r, k;
            cin >> l >> r >> k;
            A[l] += k;
            A[r + 1] -= k;
            break;
        case 'v':
            for (int i = 1; i <= n; i++)
            {
                a[i] = a[i - 1] + A[i];
                cout << a[i] << " ";
            }
            cout << endl;
            break;
        case 's':
            return 0;
        }
    }
}