LCP 05-发 LeetCoin

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

力扣决定给一个刷题团队发LeetCoin作为奖励。同时，为了监控给大家发了多少LeetCoin，力扣有时候也会进行查询。

该刷题团队的管理模式可以用一棵树表示：

  1. 团队只有一个负责人，编号为1。除了该负责人外，每个人有且仅有一个领导（负责人没有领导）；
  2. 不存在循环管理的情况，如A管理B，B管理C，C管理A。

力扣想进行的操作有以下三种：

  1. 给团队的一个成员（也可以是负责人）发一定数量的LeetCoin；
  2. 给团队的一个成员（也可以是负责人），以及他/她管理的所有人（即他/她的下属、他/她下属的下属，……），发一定数量的LeetCoin；
  3. 查询某一个成员（也可以是负责人），以及他/她管理的所有人被发到的LeetCoin之和。

输入：

  1. N表示团队成员的个数（编号为1～N，负责人为1）；
  2. leadership是大小为(N - 1) * 2的二维数组，其中每个元素[a, b]代表b是a的下属；
  3. operations是一个长度为Q的二维数组，代表以时间排序的操作，格式如下：
    1. operations[i][0] = 1: 代表第一种操作，operations[i][1]代表成员的编号，operations[i][2]代表LeetCoin的数量；
    2. operations[i][0] = 2: 代表第二种操作，operations[i][1]代表成员的编号，operations[i][2]代表LeetCoin的数量；
    3. operations[i][0] = 3: 代表第三种操作，operations[i][1]代表成员的编号；

输出：

返回一个数组，数组里是每次 查询
的返回值（发LeetCoin的操作不需要任何返回值）。由于发的LeetCoin很多，请把每次查询的结果模1e9+7 (1000000007)。

示例 1：

**输入：** N = 6, leadership = [[1, 2], [1, 6], [2, 3], [2, 5], [1, 4]], operations = [[1, 1, 500], [2, 2, 50], [3, 1], [2, 6, 15], [3, 1]]
**输出：** [650, 665]
**解释：** 团队的管理关系见下图。
第一次查询时，每个成员得到的LeetCoin的数量分别为（按编号顺序）：500, 50, 50, 0, 50, 0;
第二次查询时，每个成员得到的LeetCoin的数量分别为（按编号顺序）：500, 50, 50, 0, 50, 15.

![](https://assets.leetcode-cn.com/aliyun-lc-
upload/uploads/2019/09/09/coin_example_1.jpg)

限制：

  1. 1 <= N <= 50000
  2. 1 <= Q <= 50000
  3. operations[i][0] != 3 时，1 <= operations[i][2] <= 5000

关注小爱老师的算法课堂 ，分享高质量算法视频与文字题解

题目分析：深度优先搜索 + 树状数组

首先，本题包括几种操作（为了便于叙述，我们将对象从 LeetCoin 变成分数）：

  1. 给某人加分
  2. 给一部分人加分
  3. 查询一部分人的分数之和

操作 1 可以通过两次操作 2 完成：给一部分人（包括指定的人）加分，并将这部分人中，指定的人以外的人减同样的分数。

所以，如果我们将“一部分”这个概念量化到某个数值区间上，本题相当于要求我们实现两种操作：

  1. 给指定区间 [l, r] 加上指令数值 value
  2. 查询指令区间 [l, r] 数值之和

所以，我们可以通过深度优先搜索，将题目给定的负责人及其管理人员量化到数轴上一段连续的区间；然后通过树状数组解决区间更新和区间查询的问题。所以在算法细节部分，我们分为两部分。第一部分介绍基于深度优先搜索的量化方法，第二部分介绍基于树状数组的区间处理问题。

算法细节：

DFS 解决量化问题

由于树状数组需要对连续区间进行处理，所以本部分我们要达成的目标是：

  1. 将所有人的编号映射到 [1, N] 的区间，其中负责人及其团队需要映射到一段连续的区间
  2. 能通过负责人的编号获取得到其团队的区间 [l, r]。

由于本题按照一棵树的形式，表达一个团队的管理模式，所以可以利用深度优先搜索来完成这件事情。

首先，我们定义一个全局变量 id，用于将所有成员的编号映射到数值上。

其次，我们定义两个数组 begin[i], end[i] ，记录编号为 i 的成员所管理团队映射到的区间 [l, r]。

下面我们开始 DFS 过程：

  1. 假设本次 DFS 搜索的是编号为 cur 的成员所管理的团队，那么我们首先将 begin[cur] 设为 id，表示该成员所管理团队的**起始 id**。
  2. 对 cur 所管理团队的所有成员进行新一轮的 DFS。
  3. 当遍历完 cur 管理的团队后，我们将 end[cur] 设为当前 id（遍历管理团队时，id 会更新），表示 cur 映射到了值 id 上。
  4. 我们将 id 加一，以便继续对还未映射的成员进行映射，并退出本轮搜索。

我们以本题的样例，让大家对本题的深搜过程有更清晰的了解：

我们对 1 进行 DFS，并记录 begin[1] = 1，开始搜索其团队 [2, 6, 4]

​ 我们对 2 进行 DFS，并记录 begin[2] = 1，开始搜索其团队 [3, 5]

​ 我们对 3 进行 DFS，并记录 begin[3] = 1，开始搜索其团队 []

​ 3 搜索完毕，映射到 id = 1，并记录在 end[3] = 1 中，更新 id = 2，退出搜索。

​ 我们对 5 进行 DFS，并记录 begin[5] = 2，开始搜索其团队 []

​ 5 搜索完毕，映射到 id = 2，并记录在 end[5] = 2 中，更新 id = 3，退出搜索。

​ 2 搜索完毕，映射到 id = 3，并记录在 end[2] = 3 中，更新 id = 4，退出搜索。

​ 我们对 6 进行 DFS，并记录 begin[6] = 4，开始搜索其团队 []

​ 6 搜索完毕，映射到 id = 4，并记录在 end[6] = 4 中，更新 id = 5，退出搜索。

​ 我们对 4 进行 DFS，并记录 begin[4] = 5，开始搜索其团队 []

​ 4 搜索完毕，映射到 id = 5，并记录在 end[4] = 5 中，更新 id = 6，退出搜索。

1 搜索完毕，映射到 id = 6，并记录在 end[1] = 6 中，更新 id = 7，退出搜索。

此时整个搜索过程完毕，我们来看一下 6 个人所对应的 begin 和 end：

begin[1] = 1, end[1] = 6，表示编号为 1 的人所管理的团队映射到的区间是 [1, 6]，本身映射到 6

begin[2] = 1, end[2] = 3，表示编号为 2 的人所管理的团队映射到的区间是 [1, 3]，本身映射到 3

begin[3] = 1, end[3] = 1，表示编号为 3 的人所管理的团队映射到的区间是 [1, 1]，本身映射到 1

begin[4] = 5, end[4] = 5，表示编号为 4 的人所管理的团队映射到的区间是 [5, 5]，本身映射到 5

begin[5] = 2, end[5] = 2，表示编号为 5 的人所管理的团队映射到的区间是 [2, 2]，本身映射到 2

begin[6] = 4, end[6] = 4，表示编号为 6 的人所管理的团队映射到的区间是 [4, 4]，本身映射到 4

LCP05 00_00_00-00_00_49.gif

树状数组解决区间处理问题

如果你还不熟悉树状数组，可以看我的这篇树状数组详解 呀！

在本题的代码实现中，直接利用树状数组的区间处理模板即可。

代码：

[]
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
using ll = long long;
const ll M = 1e9 + 7;

class BIT {
public:
	int n;
    vector<ll> sum;
    vector<ll> ntimessum;
   
    BIT(int _n): n(_n + 5), sum(_n + 10, 0), ntimessum(_n + 10, 0) {}
    ll lowbit(ll x) {
        return x & (-x);
    }
    
    void update(int pos, ll k) { // 在 pos 位置加上 k
        ll x = pos;
        while(pos <= n) {
            sum[pos] += k;
            ntimessum[pos] += k * (x - 1);
            pos += lowbit(pos);
        }
    }

    void update_internal(int l, int r, int k) { // 区间更新
        update(l, k);
        update(r + 1, -k);
    }
    
    ll askis(int pos) { // 区间更新 + 单点查询 
    	if(!pos) return 0;
        ll ret = 0;
        while(pos) {
            ret += sum[pos];
            pos -= lowbit(pos);
        }
        return ret;
    }
    
    ll asksi(int l, int r) { // 单点更新 + 区间查询
        if(l > r) {
            return 0;
        }
        return askis(r) - askis(l - 1);
    }
    
    ll askss(int pos) {	// 单点更新 + 单点查询
        return askis(pos) - askis(pos - 1);
    }
    
    ll askii(int pos) { // 区间更新 + 范围查询
    	if(!pos) return 0;
        ll ret = 0, x = pos;
        while(pos) {
            ret += x * sum[pos] - ntimessum[pos];
            pos -= lowbit(pos);
        }
        return ret;
	}

    ll asklr(int l, int r) { // 区间更新 + 区间查询
        return askii(r) - askii(l - 1);
    }
};

class Solution {
public:
    int id = 1;

    void dfs(int cur, vector<int>& begin, vector<int>& end, vector<vector<int>>& g) {
        begin[cur] = id;
        for(auto &child : g[cur]) dfs(child, begin, end, g);
        end[cur] = id;
        id++;
    }

    vector<int> bonus(int n, vector<vector<int>>& leadership, vector<vector<int>>& operations) {
        // 邻接表
        vector<vector<int>> g(n + 1);
        for(auto &l : leadership) g[l[0]].push_back(l[1]);

        // 深搜，构建
        vector<int> begin(n + 1), end(n + 1);
        dfs(1, begin, end, g);

        // 树状数组
        BIT *b = new BIT(n);
        vector<int> ret;
        for(auto &q : operations) {
            if(q[0] == 1) {
                b->update_internal(end[q[1]], end[q[1]], q[2]);
            } else if(q[0] == 2) {
                b->update_internal(begin[q[1]], end[q[1]], q[2]);
            } else {
                ll ans = b->asklr(begin[q[1]], end[q[1]]);
                ret.push_back((ans % M + M) % M);
            }
        }

        return ret;
    }
};
[]
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
M = int(1e9 + 7)

class BIT:
    def __init__(self, n):
        self.n = n + 5
        self.sum = [0 for _ in range(n + 10)]
        self.ntimessum = [0 for _ in range(n + 10)]
    
    def lowbit(self, x):
        return x & (-x)

    # 在 pos 位置加上 k
    def update(self, pos, k):
        x = pos
        while pos <= self.n:
            self.sum[pos] += k
            self.sum[pos] %= M
            self.ntimessum[pos] += k * (x - 1)
            self.ntimessum[pos] %= M
            pos += self.lowbit(pos)
    
    # 区间更新 + 单点查询
    def askis(self, pos):
        if not pos:
            return 0
        ret = 0
        while pos:
            ret += self.sum[pos]
            ret %= M
            pos -= lowbit(pos)
        return ret
    
    # 单点更新 + 区间查询
    def asksi(self, l, r):
        if l > r:
            return 0
        return askis(r) - askis(l - 1)
    
    # 单点更新 + 单点查询
    def askss(self, pos):
        return askis(pos) - askis(pos - 1)
    
    # 区间更新 + 区间查询
    def askii(self, pos):
        if not pos:
            return 0
        ret = 0
        x = pos
        while pos:
            ret += x * self.sum[pos] - self.ntimessum[pos]
            ret %= M
            pos -= self.lowbit(pos)
        return ret

class Solution:
    def bonus(self, n: int, leadership: List[List[int]], operations: List[List[int]]) -> List[int]:
        
        # 邻接表
        g = [[] for _ in range(n + 1)]
        begin = [0 for _ in range(n + 1)]
        end = [0 for _ in range(n + 1)]
        id = 1

        for l in leadership:
            g[l[0]].append(l[1])
        
        # 深搜
        def dfs(cur):
            nonlocal id
            begin[cur] = id
            for child in g[cur]:
                dfs(child)
            end[cur] = id
            id += 1
        dfs(1)
        
        # 树状数组
        b = BIT(n)
        ret = []
        for q in operations:
            if q[0] == 1:
                b.update(end[q[1]], q[2])
                b.update(end[q[1]] + 1, -q[2])
            elif q[0] == 2:
                b.update(begin[q[1]], q[2])
                b.update(end[q[1]] + 1, -q[2])
            else:
                ans = b.askii(end[q[1]]) - b.askii(begin[q[1]] - 1)
                ret.append((ans % M + M) % M)

        return ret

复杂度分析：

  • 时间复杂度：O(qnlgn)，其中 q 为查询次数，n 为团队成员个数
  • 空间复杂度：O(n)
 Comments
On this page
LCP 05-发 LeetCoin
  1. 题目分析：深度优先搜索 + 树状数组
  2. 算法细节：
  3. 代码：
  4. 复杂度分析：