1713. 得到子序列的最少操作次数

发表于2024-07-17更新于2024-07-17字数统计2.8k阅读时长29分阅读次数

摘要
Title:
Categories: lis、lcs、树状数组、二分、线段树

Powered by:NEFU AB-IN

Link

1713. 得到子序列的最少操作次数

题意

给你一个数组 target ，包含若干 互不相同 的整数，以及另一个整数数组 arr ，arr 可能 包含重复元素。

每一次操作中，你可以在 arr 的任意位置插入任一整数。比方说，如果 arr = [1,4,1,2] ，那么你可以在中间添加 3 得到 [1,4,3,1,2] 。你可以在数组最开始或最后面添加整数。

请你返回 最少 操作次数，使得 target 成为 arr 的一个子序列。

一个数组的 子序列 指的是删除原数组的某些元素（可能一个元素都不删除），同时不改变其余元素的相对顺序得到的数组。比方说，[2,7,4] 是 [4,2,3,7,2,1,4] 的子序列（加粗元素），但 [2,4,2] 不是子序列。

思路

思路参考 https://leetcode.cn/problems/minimum-operations-to-make-a-subsequence/solutions/896482/de-dao-zi-xu-lie-de-zui-shao-cao-zuo-ci-hefgl/

运用了 给你一个数组 target ，包含若干 互不相同 的整数 的性质，互不相同

性质：当其中一个数组元素各不相同时，最长公共子序列问题（LCS）可以转换为最长上升子序列问题（LIS）进行求解。同时最长上升子序列问题（LIS）存在使用「维护单调序列 + 二分」的贪心解法，复杂度为 O(nlogn)，当然也可以采取树状数组或者线段树进行优化，这里介绍树状数组的思路，线段树同理。

离散化和树状数组的使用逻辑

  1. 维护离散化后的值：

    • 通过离散化，将原数组中的元素映射到一个较小的整数范围内，使得每个元素都能用一个唯一的整数表示。这些整数表示的是元素的相对大小。

  2. 查询前缀最大值：

    • 每次我们需要找到当前元素之前的最长递增子序列的长度时，首先查询树状数组中当前元素之前的所有元素的最大值。这保证了我们只考虑比当前元素小的元素。

步骤 1: 先查询

  • 保证查询原数组 [0, i] 的数：
    • 在遍历数组时，对于每个元素 arr[i]，我们通过查询树状数组来找到该元素之前的所有元素的最大值。

步骤 2: 前缀保证

  • 只查询比当前数小的离散化值：
    • 离散化后的数组中的值表示元素的相对大小。因此，通过查询离散化后的前缀，我们只查询比当前元素小的所有元素。这确保了我们不会考虑比当前元素大的值。
    • 树状数组的索引表示离散化后的值，而树状数组中的值表示对应索引处的最长递增子序列的长度。

步骤 3: 最大值

  • 查询前缀最大值：
    • 在动态规划（DP）问题中，我们需要找到当前元素之前的最大DP值。通过查询树状数组中的前缀最大值，我们可以找到在当前元素之前的最大DP值。
    • 这个最大值代表了在当前元素之前的最长递增子序列的长度。

代码

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
'''
Author: NEFU AB-IN
Date: 2024-07-15 14:58:34
FilePath: \LeetCode\1713\1713.py
LastEditTime: 2024-07-17 18:55:50
'''
# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Dict, List, Tuple, TypeVar, Union

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(int(2e9))


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class IO:
    input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
    read = staticmethod(lambda: map(int, IO.input().split()))
    read_list = staticmethod(lambda: list(IO.read()))


class Std:
    class bisect:
        @staticmethod
        def bisect_left(a, x, key=lambda y: y, lo=0, hi=None):
            """The insertion point is the first position where the element is not less than x."""
            if hi is None:
                hi = len(a)
            left, right = lo, hi
            while left < right:
                mid = (left + right) >> 1
                if key(a[mid]) < x:
                    left = mid + 1
                else:
                    right = mid
            return left

        @staticmethod
        def bisect_right(a, x, key=lambda y: y, lo=0, hi=None):
            """The insertion point is the first position where the element is greater than x."""
            if hi is None:
                hi = len(a)
            left, right = lo, hi
            while left < right:
                mid = (left + right) >> 1
                if key(a[mid]) <= x:
                    left = mid + 1
                else:
                    right = mid
            return left

    class BinaryTree:
        """Binary Indexed Tree (Fenwick Tree) for efficient prefix sum and range queries, with optional custom operation tracking."""

        def __init__(self, n, operation=lambda x, y: x + y, initial_value=0, array=None):
            self.n = n
            self.operation = operation
            self.initial_value = initial_value
            self.tree = Arr.array(initial_value, self.n + 1)

            if array:
                for i, value in enumerate(array, 1):
                    self.update(i, value)

        def update(self, i, value):
            """Update the value at index i."""
            while i <= self.n:
                self.tree[i] = self.operation(self.tree[i], value)
                i += i & -i

        def query(self, i):
            """Query the result of the operation up to index i."""
            result = self.initial_value
            while i > 0:
                result = self.operation(result, self.tree[i])
                i -= i & -i
            return result

        def range_query(self, l, r):
            """Query the result of the operation from index l to r."""
            return self.query(r) - self.query(l - 1)

        @staticmethod
        def discretize(array):
            """Discretize the array and return the mapping dictionary. Index starts from 1"""
            sorted_unique = sorted(set(array))
            mapping = {val: idx + 1 for idx, val in enumerate(sorted_unique)}
            return [mapping[val] for val in array], mapping

    class DifferenceBinaryTree:
        """Difference Array using Binary Indexed Tree (Fenwick Tree) for range updates and point queries."""

        def __init__(self, n, array=None):
            if array is None:
                array = []
            self.n = n
            self.diff_tree = Std.BinaryTree(self.n, lambda x, y: x + y)
            if array:
                for i in range(1, self.n + 1):
                    delta = array[i - 1] - (array[i - 2] if i > 1 else 0)
                    self.diff_tree.update(i, delta)

        def update_add(self, l, r, delta):
            """Update the values in the range [l, r] by adding delta"""
            self.diff_tree.update(l, delta)
            self.diff_tree.update(r + 1, -delta)

        def query_value(self, i):
            """Query the value at index i"""
            return self.diff_tree.query(i)

# ————————————————————— Division line ——————————————————————


class Solution:
    def minOperations(self, target: List[int], arr: List[int]) -> int:
        map_ = Counter()
        for i in range(len(target)):
            map_[target[i]] = i
        arr = [map_[num] for num in arr if num in map_]

        discretized_arr, mapping = Std.BinaryTree.discretize(arr)
        bit = Std.BinaryTree(n=len(discretized_arr), operation=Math.max, initial_value=0)

        for val in discretized_arr:
            max_val = bit.query(val - 1) + 1
            bit.update(val, max_val)
        return len(target) - bit.query(len(discretized_arr))


class Solution:
    def minOperations(self, target: List[int], arr: List[int]) -> int:
        map_ = Counter()
        for i in range(len(target)):
            map_[target[i]] = i
        arr = [map_[num] for num in arr if num in map_]

        lis = []
        for x in arr:
            pos = Std.bisect.bisect_left(lis, x)
            if pos == len(lis):
                lis.append(x)
            else:
                lis[pos] = x

        return len(target) - len(lis)

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
'''
Author: NEFU AB-IN
Date: 2024-07-17 18:58:41
FilePath: \LeetCode\1713\1713.1.py
LastEditTime: 2024-07-17 21:01:51
'''
# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Dict, List, Tuple, TypeVar, Union

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(int(2e9))


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class IO:
    input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
    read = staticmethod(lambda: map(int, IO.input().split()))
    read_list = staticmethod(lambda: list(IO.read()))


class Std:
    class SegmentTree:
        """A Segment Tree implementation supporting range queries and updates.

        This Segment Tree can perform various operations such as sum, min, max,
        and supports point updates, range add, and range multiply updates.
        """
        class Node:
            def __init__(self, l: int = 0, r: int = 0):
                self.l = l
                self.r = r
                self.val = 0
                self.add_tag = 0
                self.mul_tag = 1

        def __init__(self, n: int, operation=lambda x, y: x + y, initial_value=0):
            """initial the tree, n can not be 0 !!!"""
            self.n = n
            self.tr = Arr.array(lambda: Std.SegmentTree.Node(0, 0), n << 2)
            self.operation = operation
            self.initial_value = initial_value

        def pushup(self, p: int):
            """Push up the values to the parent node based on the operation"""
            self.tr[p].val = self.operation(self.tr[p << 1].val, self.tr[p << 1 | 1].val)

        def pushdown(self, p: int):
            """Push down the tags to the children nodes"""
            if self.tr[p].add_tag != 0 or self.tr[p].mul_tag != 1:
                ls, rs = p << 1, p << 1 | 1
                if self.tr[p].mul_tag != 1:
                    self.apply(p, ls)
                    self.apply(p, rs)
                if self.tr[p].add_tag != 0:
                    self.apply(p, ls)
                    self.apply(p, rs)
                self.tr[p].add_tag = 0
                self.tr[p].mul_tag = 1

        def apply(self, p: int, child: int):
            """Apply the tags to a child node"""
            self.tr[child].val = self.tr[child].val * self.tr[p].mul_tag + self.tr[p].add_tag * (self.tr[child].r - self.tr[child].l + 1)
            self.tr[child].mul_tag *= self.tr[p].mul_tag
            self.tr[child].add_tag = self.tr[child].add_tag * self.tr[p].mul_tag + self.tr[p].add_tag

        def build(self, p: int, l: int, r: int, a: list = []):
            """Build the segment tree based on the given array or default value"""
            self.tr[p].l = l
            self.tr[p].r = r
            if l == r:
                self.tr[p].val = a[l] if a else self.initial_value
                return
            mid = (l + r) >> 1
            self.build(p << 1, l, mid, a)
            self.build(p << 1 | 1, mid + 1, r, a)
            self.pushup(p)

        def update_point(self, p: int, idx: int, value: int):
            """Point update for the segment tree at index idx"""
            if self.tr[p].l == self.tr[p].r:
                self.tr[p].val = value
                return
            mid = (self.tr[p].l + self.tr[p].r) >> 1
            if idx <= mid:
                self.update_point(p << 1, idx, value)
            else:
                self.update_point(p << 1 | 1, idx, value)
            self.pushup(p)

        def update_range_add(self, p: int, l: int, r: int, d: int):
            """Range add update for the segment tree within the range [l, r]"""
            if l <= self.tr[p].l and self.tr[p].r <= r:
                self.tr[p].val += d * (self.tr[p].r - self.tr[p].l + 1)
                self.tr[p].add_tag += d
                return
            self.pushdown(p)
            mid = (self.tr[p].l + self.tr[p].r) >> 1
            if l <= mid:
                self.update_range_add(p << 1, l, r, d)
            if mid < r:
                self.update_range_add(p << 1 | 1, l, r, d)
            self.pushup(p)

        def update_range_mul(self, p: int, l: int, r: int, d: int):
            """Range multiply update for the segment tree within the range [l, r]"""
            if l <= self.tr[p].l and self.tr[p].r <= r:
                self.tr[p].val *= d
                self.tr[p].mul_tag *= d
                self.tr[p].add_tag *= d
                return
            self.pushdown(p)
            mid = (self.tr[p].l + self.tr[p].r) >> 1
            if l <= mid:
                self.update_range_mul(p << 1, l, r, d)
            if mid < r:
                self.update_range_mul(p << 1 | 1, l, r, d)
            self.pushup(p)

        def query(self, p: int, l: int, r: int) -> int:
            """Query the segment tree within the range [l, r]"""
            if l <= self.tr[p].l and self.tr[p].r <= r:
                return self.tr[p].val
            self.pushdown(p)
            mid = (self.tr[p].l + self.tr[p].r) >> 1
            res = self.initial_value
            if l <= mid:
                res = self.operation(res, self.query(p << 1, l, r))
            if r > mid:
                res = self.operation(res, self.query(p << 1 | 1, l, r))
            return res

        @staticmethod
        def discretize(array):
            """Discretize the array and return the mapping dictionary. Index starts from 1"""
            sorted_unique = sorted(set(array))
            mapping = {val: idx + 1 for idx, val in enumerate(sorted_unique)}
            return [mapping[val] for val in array], mapping
# ————————————————————— Division line ——————————————————————


class Solution:
    def minOperations(self, target: List[int], arr: List[int]) -> int:
        map_ = Counter()
        for i in range(len(target)):
            map_[target[i]] = i
        arr = [map_[num] for num in arr if num in map_]
        n = len(arr)

        if not arr:
            return len(target)

        discretized_arr, mapping = Std.SegmentTree.discretize(arr)
        seg = Std.SegmentTree(n, Math.max, 0)
        seg.build(1, 0, n - 1)
        for val in discretized_arr:
            max_val = seg.query(1, 0, val - 1) + 1
            seg.update_point(1, val, max_val)
        return len(target) - seg.query(1, 0, n - 1)

使用搜索：谷歌必应百度