周赛399(240526)

这场掉分了，第四题没思路，而且罚时太多了😥

第三题3164. 优质数对的总数 II

题目大意： 给定两个整数数组nums1和nums2，以及一个正整数k。如果nums1[i]可以被nums2[j]*k整除，则称数对(i, j)为优质数对。要求计算优质数对的总数。

实现思路：

  1. 首先，使用Counter统计nums1中可以被k整除的数除以k的结果，得到c1。
  2. 然后，找到c1中的最大值mx，如果c1为空，则mx为0。
  3. 使用Counter统计nums2中各个数出现的次数，得到c2。
  4. 初始化结果res为0。
  5. 遍历c2中的每个数nm和其出现的次数c，对于每个数nm，从nm开始递增到mx，步长为nm，计算c * c1[j]并累加到res中。
  6. 最终返回res作为优质数对的总数。
class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        c1 = Counter(nm//k for nm in nums1 if nm%k==0)
        mx = max(nm for nm, _ in c1.items()) if c1 else 0
        c2 = Counter(nums2)

        res = 0
        for nm, c in c2.items():
            for j in range(nm, mx+1, nm):
                res += c * c1[j]
        
        return res

第四题3165. 不包含相邻元素的子序列的最大和

题目大意

给定一个整数数组 nums 和一个二维数组 queries，其中 queries[i] = [posi, xi] 表示对于每个查询 i，首先将 nums[posi] 设置为 xi，然后计算查询 i 的答案。答案为 nums 中不包含相邻元素的子序列的最大和。最终返回所有查询的答案之和。

实现思路

  1. 构建线段树：使用线段树维护区间的最大和。
    • 线段树节点 tr[u] 存储了四个值，分别表示：
      1. 不跨越区间的最大和（无相邻元素）。
      2. 区间左端点为起点的最大和（无相邻元素）。
      3. 区间右端点为起点的最大和（无相邻元素）。
      4. 区间的最大和。
    • 定义 pushup 函数更新节点值，定义 build 函数构建线段树。
  2. 更新操作：更新线段树中的节点值。
    • 定义 update 函数更新线段树中的节点值。
  3. 遍历查询：对每个查询，更新 nums 中对应位置的值，并计算当前的最大和。
  4. 最终返回所有查询的答案之和，记得对结果取模。
class Solution:
    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:
        def pushup(u):
            l, r = tr[u<<1], tr[u<<1|1]
            tr[u][0] = max(l[1]+r[0], l[0]+r[2])
            tr[u][1] = max(l[0]+r[3], l[1]+r[1])
            tr[u][2] = max(l[2]+r[2], l[3]+r[0])
            tr[u][3] = max(l[2]+r[3], l[3]+r[1])

        def build(u, l, r):
            if l==r:
                tr[u][3] = max(nums[l], 0)
            else:
                mid = l+r>>1
                build(u<<1, l, mid)
                build(u<<1|1, mid+1, r)
                pushup(u)
            
        def update(u, l, r, x, val):
            if l==r:
                tr[u][3] = max(0, val)
                return 
            
            mid = l+r>>1
            if x<=mid:
                update(u<<1, l, mid, x, val)
            else:
                update(u<<1|1, mid+1, r, x, val)
            
            pushup(u)
        
        n = len(nums)
        tr = [[0]*4 for _ in range(1<<n.bit_length() + 1)]
        mod = int(1e9) + 7
        res = 0
        build(1, 0, n-1)
        for pos, x in queries:
            update(1, 0, n-1, pos, x)
            res = (res + tr[1][3])%mod
        
        return res