差分数组 | SCHeng

对于一个数组D,要求其前i项和,$ SUM = \sum\limits_{i=1}^{n} {D_i}$ 令$f[i] = D[i] - D[i-1] i \in [2, n]$, 当i=1时$f[1] = D[1] - 0 = D[1]$ 简单性质: D[i]的值是f[i]的前缀和,即$D[i] = \sum\limits_{j=1}^{i} {f_i}$ 计算D[i]的前缀和, $ SUM = \sum\limits_{i=1}^{n} {D_i} = \sum\limits_{i = 1} ^{n} \sum\limits_{j = 1}^{i}{f_j} = ( n - i + 1 ) * {f_i}$ 这种结构可以快速处理一段区域数据的频繁的加减操作,只需要$f[L] += item, f[R+1] -= item $就可以了.其中$f[R + 1] = D[R+1] - D[R]$ $ f[R + 1] - item = D[R+1] - (D[R] + item) $,对区间的两个端点进行操作,就不必对一段区域进行操作了. 相关例题: HDU1556 差分数组的模板题. $arr[i] = arr[i-1] + f[i]; 是对f[i] = arr[i] - arr[i-1]$的一个变形

#include  <bits/stdc++.h>

using namespace std;
int t, a, b;
vector<int> arr, f;
int main()
{
    while ( scanf("%d", &t) && t )
    {
        arr.clear();f.clear();
        arr.resize(t + 1);
        f.resize(t + 1);
        //f[1] = arr[1];
        int tmp = t;
        while ( tmp -- )
        {
            scanf("%d %d", &a, &b);
            f[a] ++; f[b+1] --;
        }
        for ( int i = 1; i <= t; i ++  ) 
        {
            arr[i] = arr[i-1] + f[i];
            printf("%d",arr[i]);
            if ( i != t ) printf(" ");
        }
        printf("\n");
    }
    return 0;
}

luogu_P1083

二分查找+差分数组.用二分查找来寻找m中不能使条件满足的第一个请求. $f[i]$表示$arr[i]$的差分数组,对租借天数的$left$和$right$进行操作:

1 2	f[arr[i].left] += arr[i].weight; f[arr[i].right+1] -= arr[i].weight;

根据性质1, 如果$f[i]$的前缀和超过了那一天的教师数量$a[i]$就说明这一次的请求是需要修改的.

#include  <bits/stdc++.h>

using namespace std;

struct node
{
    int left, right, weight;
}  arr[1000010];

long long int f[1000010], n, m, a[1000010];

bool check( int day )
{
    long long int sum = 0;
    memset(f, 0, sizeof(f));
    for ( int i = 1; i <= day; i ++ )
    {   
        f[arr[i].left] += arr[i].weight;
        f[arr[i].right+1] -= arr[i].weight;
    }
    for ( int i = 1; i <= n; i ++ )
    {
        sum += f[i];
        if ( sum > a[i] ) return 0;
    }
    return 1;
}

int main()
{

    scanf("%lld %lld", &n, &m);
    for ( int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);
    for ( int i = 1; i <= m; i ++ ) scanf("%d %d %d", &arr[i].weight, &arr[i].left, &arr[i].right);
    if ( check(m) ) { printf("0\n"); return 0; }
    int left = 1, right = m;
    while ( right > left )
    {
        int mid = ( left + right ) / 2;
        if ( check(mid) ) left = mid + 1 ;
        else right = mid;
    }
    //cout << left << ' '<<right <<endl;
    printf("-1\n%d\n",right);

    return 0;
}

codeforce1355C

$x_i \in [A, B]$ $y_i \in [B, C]$ $z_i \in [C, D]$ 只要满足$x_i + y_i > z_i$, 观察可得,需要求满足$[x_i + B, x_i + C]>[C, D]$的那些组合的个数. 设置一个差分数组$a[i], a[i]$记录长度为i的边(或者边的和)的个数. 设置一个maxn, 为题目所给的ABCD相加不会超过的一个值先遍历一遍区间$x \in [A, B]$求出$[x_i + B, x_i + C]$也就是

for ( int i = a; i <= b; i ++ )
    {
        arr[b + i] ++;
        arr[c + i + 1] --;
    }

再根据性质1就能够求出两边和为i的数量了

1	for ( int i = 1; i <= maxn; i ++ ) arr[i] += arr[i-1];

再进行一次累加,求出前缀和.

1	for ( int i = c; i <= d; i ++ ) sum += ( arr[maxn] - arr[i] );

$arr[maxn] - arr[i]$表示比$z_i$大的两边和的总数.

#include <bits/stdc++.h>

using namespace std;

int a, b, c, d;
const int maxn = 1000080;
long long int arr[maxn+1];

int main()
{
    scanf("%d %d %d %d", &a, &b, &c, &d);
    memset(arr, 0, sizeof(arr));
    for ( int i = a; i <= b; i ++ )
    {
        arr[b + i] ++;
        arr[c + i + 1] --;
    }
    for ( int i = 1; i <= maxn; i ++  ) arr[i] += arr[i-1];
    //求两边和为i的项目的个数
    for ( int i = 1; i <= maxn; i ++  ) arr[i] += arr[i-1];
    //前缀和
    long long int sum = 0;
    for ( int i = c; i <= d; i ++ ) sum += ( arr[maxn] - arr[i] );
    printf("%lld\n",sum);
    return 0;
}

updated at 2022-02-02

# differentialarray