赛氪练习

2022.1.19 1.3.4 区间问题

题目

Description

Uncle-lu 现在有一个长度为 n 的序列，淘气的 uncle-lu 对这个序列进行了多次的修改，每次修改的方式都是，对该序列的一段区间整体加上一个数。多次修改之后，uncle-lu 想知道该序列中的某一些位置的值是多少，聪明的你一定能帮帮他。

Input

第一行为一个正整数 n 表示该序列的长度

第二行为 n 个正整数，表示该序列

第三行为一个正整数 q 表示接下来有 q 次修改

接下来q行每行3个整数 a b v，其中 a , b 表示修改的区间 [ a, b ]，v 表示对该区间中的每个数增加的值。

接下来一行为一个整数 p 表示接下来有 p 次询问。

接下来 p 行每行11个整数 c 表示 uncle-lu 想知道序列中第 c 位置的值是多少。

Output

输出共 p 行，每行对应输入的询问，输出经过修改后该位置的值。

Sample Input 1

1
2
3
4
5
6
7
8
9
5
4 3 2 5 1
3
1 3 4
2 4 -1
3 5 2
2
3
2

Sample Output 1

1
2
7
6

Hint

题解

思路

思路就是差分数组，推荐阅读：

小而美的算法技巧：差分数组 :: labuladong的算法小抄 (gitee.io)

改写一下差分数组工具类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 差分数组工具类
class Difference {
    // 差分数组
    private int[] diff;
    
    /* 输入一个初始数组，区间操作将在这个数组上进行 */
    public Difference(int[] nums) {
        assert nums.length > 0;
        diff = new int[nums.length];
        // 根据初始数组构造差分数组
        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    /* 给闭区间 [i,j] 增加 val（可以是负数）*/
    public void increment(int i, int j, int val) {
        diff[i] += val;
        if (j + 1 < diff.length) {
            diff[j + 1] -= val;
        }
    }

    /* 返回结果数组 */
    public int[] result() {
        int[] res = new int[diff.length];
        // 根据差分数组构造结果数组
        res[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cmath>

using namespace std;

int main()
{
   int n = 0;
   while (scanf("%d", &n) != EOF)
   {
      int num[n];
      for (int i = 0; i < n; i++)
      {
         scanf("%d", &num[i]);
      }

      int q = 0;
      scanf("%d", &q);

      // 创建查分数组并初始化
      int diff[n];
      diff[0] = num[0];
      for (int i = 1; i < n; i++)
      {
         diff[i] = num[i] - num[i - 1];
      }
      
      for (int i = 0; i < q; i++)
      {
         int a, b, v;
         scanf("%d %d %d", &a, &b, &v);
         diff[a - 1] += v;
         diff[b] -= v;
      }

      // 算得结果
      int res[n];
      res[0] = diff[0];
      for (int i = 1; i < n; i++)
      {
         res[i] = res[i - 1] + diff[i];
      }
      
      // 输出结果
      int p;
      scanf("%d", &p);
      int c[p];
      for (int i = 0; i < p; i++)
      {
         scanf("%d", &c[i]);
      } 
      for (int i = 0; i < p; i++)
      {
         printf("%d\n", res[c[i] - 1]);
      }
      
   }
   
   return 0;
}