前言

本文章主要写的是有关差分的相关习题

差分的定义

差分就是前一个数减去后一个数的值， a[i+1] – a[i];

给定一个数组a[5]

a[5] = {1, 2, 3, 4, 5};

其差分数组为：

d[] = {1, 1, 1, 1, 1};

如果对其进行一次前缀和得到以下数组

s[] = {1, 2, 3, 4, 5};

我们发现s[] = a[] ，所以差分和前缀和互为逆运算

差分的性质

给定数组

a[] = {0, 1, 2, 3, 4, 5, 6, 4};

如果想给区间[2, 5]每一个数都加上3，一般的方法就是从开始遍历到下标2， 然后每个元素加3，遍历到下标5停止，但是，如果当a[]中的元素很大的情况下，这种方法就会浪费大量时间。所以我们可以这样做，在差分数组的对应下标2上加3，下标5+1减3，然后再求前缀和，结果得到以下数组：

//差分
a[] = {0, 1, 1, 1, 1, 1, 1, -2}

//在2，5下标位置加上3
a[] = {0, 1, 4, 1, 1, 1, -2, -2};

//前缀和
a[] = {0, 1, 5, 6, 7, 8, 6, 4};

发现原数组的[2, 5]都增加了3， 使用这种方法可以很便利的对指定区间内的所有元素同时加上一个或减一个数。

差分还可以用来判断数组的增减性：

a[4] = {1, 2, 3, 4, 5};
b[4] = {5, 4, 3, 2, 1};
c[4] = {2, 3, 3, 4, 4};

对于以上数组进行差分

a[4] = {1, 1, 1, 1, 1};
b[4] = {-1, -1, -1, -1, -1};
c[4] = {2, 1, 0, 1, 0}

发现当原数组是递增的时候，其差分数列全部大于零，反之全部小于零。当有相邻元素相等时，差分数列就会出现0。

题目：

2128重新排序

题目链接：https://www.lanqiao.cn/problems/2128/learning/?page=1&first_category_id=1&second_category_id=3&problem_id=2128

分析：

这道题给定了多个区间[L, R],先求在原数组在这多个区间的总和，然后对原数组进行排序，使得重新排列后的数组在多个[L, R]区间内的和仅可能的大，最后求出其差；

每当给出一个区间，该区间的数就被覆盖一次，所以给出多个区间，其对应位置就会被覆盖多次，如果想求出来的和最大，那么就需要尽可能覆盖较大的数。换句话说覆盖次数就是要计算的次数

例如，给定以下数组和区间

1 2 3 4 5
1 3
2 5

1-3区间被覆盖一次，2-5区间被覆盖一次，其对应位置被覆盖的次数：

1 2 2 1 1 

所以我们需要将原数列中较大的数放入覆盖次数较多的位置。

代码实现：

//这题刚开始就只是想到区间之间会覆盖，将族大的数放在覆盖最多的地方
/*
1.使用差分找到每个位置覆盖的权重 
2.将差分数组和原数组进行排序
3.将两个数组大的相乘求和就行
*/
//注意使用long long 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
    long long n;
    cin >> n;
    vector<long long> a(n+1);       //存储原数组 注意要多开一位，这样对应边界就是对应下标
    vector<long long> s(n+1);       //前缀和，用于求对应区间和，也要多开一位，这样对应边界就是对应下标
    a[0] = 0;
    s[0] = 0;
    for(long long i = 1; i <= n; i++){
        cin >> a[i];
        s[i] = s[i-1] + a[i];
    }
    // for(int i = 1; i <= n; i++){
    //     cout << s[i] << endl;
    // }

    //求出原数组的区间和
    long long m;
    cin >> m;
    long long sum = 0;
    vector<long long> diff(n+1);        //覆盖次数数组，也要多开一位，这样对应边界就是对应下标
    for(long long i = 0; i < m; i++){
        long long l, r;
        cin >> l >> r;
        diff[l] += 1;
        diff[r+1] -= 1;
        sum += (s[r] - s[l-1]);
    }
    //cout << sum << endl;
    for(long long i = 1; i <= n; i++){
        diff[i] += diff[i-1];
        //cout << diff[i] << " ";
    }
    //对差分数组和原数组进行
    sort(a.begin(), a.end() );
    sort(diff.begin(), diff.end());

    // for(int i = 0; i <= n; i++){
    //     cout << diff[i] << " "; 
    // }
    long long new_sum = 0;
    for(long long i = 0; i <= n; i++){
        new_sum += (a[i] * diff[i]); 
    }
    cout << new_sum - sum << endl;
    
}