原文：
给定大小为n的数组和给定的大小为m的命令集。 每个命令由四个整数q, l, r, k组成。 这些命令具有以下类型：
-
如果
q = 0，则将k添加到范围a至b的所有整数中（1 <= a <= b <= n）。 -
如果
q = 1，则将a到b范围内的所有整数减去k（1 <= a <= b <= n）。
注意：最初，所有数组元素都设置为 0，而数组索引从 1 开始。
input : n = 5
commands[] = {{0 1 3 2}, {1 3 5 3},
{0 2 5 1}}
output : 0 2 -1 -1 -3
explanation
first command: add 2 from index 1 to 3
>= 2 2 2 0 0
second command: subtract 3 from index 3 to 5
>= 2 2 -1 -3 -3
third command: add 1 from index 2 to 5
>= 2 3 0 -2 -2
简单方法是通过从左索引（l）到右索引（r）进行迭代来执行每个命令，并根据给定命令更新每个索引。 该方法的时间复杂度为o(n * m)。
更好的方法是使用分域树（bit）或段树。 但这只会最优化log(n)时间，即整体复杂度将变为o(m * log(n))。
高效方法是使用简单的数学方法。 由于所有命令都可以离线处理，因此我们可以将所有更新存储在临时数组中，然后最后执行它。
-
对于命令 0，在第
l个第r 1个索引元素中添加k和-k。 -
对于命令 1，在第
l个第r 1个索引元素中添加k和-k。
之后，对每个索引i的所有元素求和，从第一个索引开始，即a[i]将包含索引从 1 到i的所有元素的和。 这可以通过动态规划轻松实现。
c
// c program to find modified array
// after executing m commands/queries
#include
using namespace std;
// update function for every command
void updatequery(int arr[], int n, int q, int l,
int r, int k)
{
// if q == 0, add 'k' and '-k'
// to 'l-1' and 'r' index
if (q == 0){
arr[l-1] = k;
arr[r] = -k;
}
// if q == 1, add '-k' and 'k'
// to 'l-1' and 'r' index
else{
arr[l-1] = -k;
arr[r] = k;
}
return;
}
// function to generate the final
// array after executing all
// commands
void generatearray(int arr[], int n)
{
// generate final array with the
// help of dp concept
for (int i = 1; i < n; i)
arr[i] = arr[i-1];
return;
}
// driver program
int main()
{
int n = 5;
int arr[n 1];
//set all array elements to '0'
memset(arr, 0, sizeof(arr));
int q = 0, l = 1, r = 3, k = 2;
updatequery(arr, n, q, l, r, k);
q = 1 , l = 3, r = 5, k = 3;
updatequery(arr, n, q, l, r, k);
q = 0 , l = 2, r = 5, k = 1;
updatequery(arr, n, q, l, r, k);
// generate final array
generatearray(arr, n);
// printing the final modified array
for (int i = 0; i < n; i)
cout << arr[i] << " ";
return 0;
}
java
// java program to find modified array
// after executing m commands/queries
import java.util.arrays;
class gfg {
// update function for every command
static void updatequery(int arr[], int n,
int q, int l, int r, int k)
{
// if q == 0, add 'k' and '-k'
// to 'l-1' and 'r' index
if (q == 0){
arr[l-1] = k;
arr[r] = -k;
}
// if q == 1, add '-k' and 'k'
// to 'l-1' and 'r' index
else{
arr[l-1] = -k;
arr[r] = k;
}
return;
}
// function to generate the final
// array after executing all
// commands
static void generatearray(int arr[], int n)
{
// generate final array with the
// help of dp concept
for (int i = 1; i < n; i)
arr[i] = arr[i-1];
}
//driver code
public static void main(string arg[])
{
int n = 5;
int arr[] = new int[n 1];
//set all array elements to '0'
arrays.fill(arr, 0);
int q = 0, l = 1, r = 3, k = 2;
updatequery(arr, n, q, l, r, k);
q = 1 ; l = 3; r = 5; k = 3;
updatequery(arr, n, q, l, r, k);
q = 0 ; l = 2; r = 5; k = 1;
updatequery(arr, n, q, l, r, k);
// generate final array
generatearray(arr, n);
// printing the final modified array
for (int i = 0; i < n; i)
system.out.print(arr[i] " ");
}
}
// this code is contributed by anant agarwal.
python3
# python3 program to find modified array
# after executing m commands/queries
# update function for every command
def updatequery(arr, n, q, l, r, k):
# if q == 0, add 'k' and '-k'
# to 'l-1' and 'r' index
if (q == 0):
arr[l - 1] = k
arr[r] = -k
# if q == 1, add '-k' and 'k'
# to 'l-1' and 'r' index
else:
arr[l - 1] = -k
arr[r] = k
return
# function to generate the final
# array after executing all commands
def generatearray(arr, n):
# generate final array with the
# help of dp concept
for i in range(1, n):
arr[i] = arr[i - 1]
return
# driver code
n = 5
arr = [0 for i in range(n 1)]
# set all array elements to '0'
q = 0; l = 1; r = 3; k = 2
updatequery(arr, n, q, l, r, k)
q, l, r, k = 1, 3, 5, 3
updatequery(arr, n, q, l, r, k);
q, l, r, k = 0, 2, 5, 1
updatequery(arr, n, q, l, r, k)
# generate final array
generatearray(arr, n)
# printing the final modified array
for i in range(n):
print(arr[i], end = " ")
# this code is contributed by anant agarwal.
c
// program to find modified
// array after executing
// m commands/queries
using system;
class gfg {
// update function for every command
static void updatequery(int[] arr, int n, int q,
int l, int r, int k)
{
// if q == 0, add 'k' and '-k'
// to 'l-1' and 'r' index
if (q == 0) {
arr[l - 1] = k;
arr[r] = -k;
}
// if q == 1, add '-k' and 'k'
// to 'l-1' and 'r' index
else {
arr[l - 1] = -k;
arr[r] = k;
}
return;
}
// function to generate final
// array after executing all
// commands
static void generatearray(int[] arr, int n)
{
// generate final array with
// the help of dp concept
for (int i = 1; i < n; i)
arr[i] = arr[i - 1];
}
// driver code
public static void main()
{
int n = 5;
int[] arr = new int[n 1];
// set all array elements to '0'
for (int i = 0; i < arr.length; i )
arr[i] = 0;
int q = 0, l = 1, r = 3, k = 2;
updatequery(arr, n, q, l, r, k);
q = 1;
l = 3;
r = 5;
k = 3;
updatequery(arr, n, q, l, r, k);
q = 0;
l = 2;
r = 5;
k = 1;
updatequery(arr, n, q, l, r, k);
// generate final array
generatearray(arr, n);
// printing the final modified array
for (int i = 0; i < n; i)
console.write(arr[i] " ");
}
}
// this code is contributed by anant agarwal.
输出：
output: 2 3 0 -2 -2
时间复杂度：o(max(m, n))。
辅助空间：o(n)。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
