AcWing 797. Diff

Topic source: [AcWing 797. Difference]

1. Description of the topic

Enter a length of n n nsequence of integers.

Next enter m m moperations, each containing three integers l , r , c l,r,c l,r,c, indicating that the sequence will be [ l , r ] [l,r] [l,r]each number between plus c c c。

Please output the sequence after all operations are performed.

Input format
The first line contains two integers n n nand m m m。

The second line contains n n nintegers, representing a sequence of integers.

next m m mlines, each containing three integers l l l, r r r, c c c, which represents an operation.

Output format
A total of one line, including n n nan integer representing the final sequence.

data range
1 ≤ n , m ≤ 100000 , 1≤ n, m ≤ 100000, 1≤n,m≤100000,
1 ≤ l ≤ r ≤ n , 1 ≤ l ≤ r ≤ n, 1≤l≤r≤n,
− 1000 ≤ c ≤ 1000 , −1000 ≤ c ≤ 1000, −1000≤c≤1000,
− 1000 ≤ −1000 ≤ −1000≤the value of an element in a sequence of integers ≤ 1000 ≤ 1000 ≤1000

Input sample:

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

Sample output:

3 4 5 3 4 2

Second, the algorithm idea

Definition of Difference

Difference is the inverse of prefix sum .

Suppose there is a sequence a 1 , a 2 , . . . , a n a_{1},a_{2},…,a_{n} a1​,a2​,…,an​, now we need to construct a sequence b 1 , b 2 , . . . , b n b_{1},b_{2},…,b_{n} b1​,b2​,…,bn​, use a i = b 1 + b 2 + . . . + b i a_{i}=b_{1}+b_{2}+…+b_{i} ai​=b1​+b2​+…+bi​, immediately a [ ] a[ ] a [ ] is b[ ] b[ ] the prefix sum of b[ ], then b [ ] b[ ] b [ ] is called a [ ] a[ ] Differenceof a [ ] .

The role of difference

  1. Only O(n) O(n) O ( n ) time complexity, by comparing b[ ] b[ ] b [ ] is the prefix sum, and the original array a [ ] a[ ] a[]
  2. Free O(1) O(1) O ( 1 ) time to complete the operation: given an interval [ l , r ] [l, r] [l,r ] , add a constant c c each elementthis intervalc。

in a a a sequence [ l , r ] [l, r] [l,r ] interval plus constant c c c   <=> <=> <=>   b l + c , b r + 1 − c b_l+c,b_{r+1}-c bl​+c,br+1​−c

In other words : if an array needs to frequently add or subtract a constant to one of its intervals , I can convert to constructing the difference of the array , and then use O(1) O(1) The addition and subtraction of the difference array is completed in O ( 1 ) time, and finallyafter frequent interval addition and subtraction is obtained byprefix sum of the difference

difference construction

There is a very simple construction: we can assume the sequence a 1 , a 2 , . . . , a n a_{1},a_{2},…,a_{n} a1​,a2​,…,an​Every number is 0 0 0 (not actually 0 0 0 ), then its difference sequence b 1 , b 2 , . . . , b n b_{1},b_{2},…,b_{n} b1​,b2​,…,bn​Also all 0 0 0 . then put the real a a a sequence as in [ 1 , 1 ] [1,1] [1,1 ] insert constant a 1 a_{1} a1​, in [ 2 , 2 ] [2,2] [2,2 ] insert constant a 2 a_{2} a2​, and so on.

3. Code

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int b[N], n, m;

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

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

    // Construct the initial difference sequence b from sequence a 
    for ( int i = 1 ; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        insert(i, i, x);
    }

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

    // prefix and sum the difference sequence to get a sequence 
    for ( int i = 1 ; i <= n; i++)
    {
        b[i] += b[i - 1];
        printf("%d ", b[i]);
    }
    puts("");

    return 0;
}

Leave a Comment

Your email address will not be published. Required fields are marked *