題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟣 P6047 丝之割

Problem Statement

題目簡述

有 nn 個上方固定點、nn 個下方固定點，以及 mm 條弦。每條弦可表示為 (u,v)(u,v)，連接上方第 uu 個點與下方第 vv 個點。
一次切割可以選擇兩個下標 (i,j)(i,j)，花費 aibja_i b_j，並破壞所有滿足 u>iu>i 且 v<jv<j 的弦。
可以切割任意次，求破壞所有弦的最小總花費。

Constraints

約束條件

  • 1≤n,m≤3×1051 \le n,m \le 3\times 10^5
  • 2≤u≤n2 \le u \le n
  • 1≤v≤n−11 \le v \le n-1
  • 1≤ai,bi≤1061 \le a_i,b_i \le 10^6

思路：支配關係刪弦 + 斜率優化 DP

這題的訓練點是：先把幾何切割關係轉成偏序支配，再把剩下的弦按順序分段刪除。真正困難的地方不在「怎麼切一刀」，而是要看出很多弦其實不需要單獨考慮。

先看一刀能刪掉什麼

根據題意，若選擇切割點 (i,j)(i,j)，會被破壞的弦 (u,v)(u, v) 必須滿足 u>iu > i 且 v<jv < j。反過來看，若想破壞某條弦 (u,v)(u,v)，選擇的切割點 (i,j)(i,j) 必須滿足 i<ui < u 且 j>vj > v。

因此，一旦某次切割能破壞 (u,v)(u,v)，那麼所有滿足 u′≥uu' \ge u 且 v′≤vv' \le v 的弦 (u′,v′)(u',v') 也會被同時破壞。

可以搭配圖形來理解，若兩條弦在平面上交叉 (X)，在破壞左上右下 (\) 的那條弦時，另外一條右上左上 (/) 的弦也會被順帶破壞。

為方便說明，以下稱能在消除其他弦時被順帶消除的弦是「被支配」的，因為破壞支配它的弦時也會被破壞，因此被其他元素支配的元素不需要單獨保留。

刪掉被支配的弦

這裡有兩種方法可以刪掉被支配的弦：

1. 基於排序的刪除 O(mlog⁡m)O(m\log m)

先從最直觀的排序去重講起。把所有弦 (u,v)(u,v) 按照下面的關鍵字排序：

(u,v)↦(u,−v)(u,v)\mapsto (u,-v)

也就是 uu 升序；若 uu 相同，則 vv 降序。排序後得到序列

(u1,v1),(u2,v2),…,(um,vm)(u_1,v_1),(u_2,v_2),\ldots,(u_m,v_m)

滿足對任意 i<ji<j，都有 ui<uju_i<u_j，或 ui=uju_i=u_j 且 vi≥vjv_i\ge v_j。

接著從左到右掃描，維護

Mi=max⁡{vt∣1≤t<i, (ut,vt) 已被保留}M_i=\max\{v_t\mid 1\le t<i,\ (u_t,v_t)\text{ 已被保留}\}

也就是掃描到第 ii 條弦前，已保留弦中的最大下方端點。此時判斷 (ui,vi)(u_i,v_i)：

  • 若 vi≤Miv_i\le M_i，則存在某條已保留弦 (uj,vj)(u_j,v_j) 滿足 j<ij<i 且 vj=Mi≥viv_j=M_i\ge v_i。由排序可知 uj≤uiu_j\le u_i，所以 (uj,vj)(u_j,v_j) 支配 (ui,vi)(u_i,v_i)，第 ii 條弦可以刪掉。
  • 若 vi>Miv_i>M_i，則對所有 j<ij<i 都有 vj<viv_j<v_i，前面的弦不可能同時滿足 uj≤uiu_j\le u_i 與 vj≥viv_j\ge v_i，所以 (ui,vi)(u_i,v_i) 不能被前面任何弦支配，必須保留。

同一個 uu 要讓 vv 降序，是為了讓同組最大的 vv 先出現。若有 (u,va)(u,v_a) 與 (u,vb)(u,v_b) 且 va>vbv_a>v_b，那麼 (u,va)(u,v_a) 支配 (u,vb)(u,v_b)；降序後，較小的 vbv_b 一定會因為 vb≤Miv_b\le M_i 被跳過。

最後留下的弦滿足：

u1<u2<⋯<uk,v1<v2<⋯<vku_1<u_2<\cdots<u_k,\qquad v_1<v_2<\cdots<v_k

也就是一組不再互相支配的弦。排序版的時間複雜度是 O(mlog⁡m)\mathcal{O}(m\log m)。

為什麼不能只保留某個全域最大或最小？

支配關係同時看兩個座標：上方端點要 ≥\ge、下方端點要 ≤\le。單看其中一維會漏掉真正不可被支配的弦，所以必須按一維排序，維護另一維的前綴最大值。

2. 基於值域的刪除 O(n+m)O(n+m)

但注意到 uu 與 vv 的值域都是 [1,n][1,n]，可以不用真的排序。對每個上方端點 uu，先記錄所有以 uu 為上方端點的弦中，最大的下方端點：

max_v[u]=max⁡{v∣(u,v) 是一條弦}\mathrm{max\_v}[u]=\max\{v\mid (u,v)\text{ 是一條弦}\}

若不存在上方端點為 uu 的弦，則 max_v[u]=0\mathrm{max\_v}[u]=0。這一步等價於排序版中「同一個 uu 只保留最大的 vv」。

接著按照 u=1,2,…,nu=1,2,\ldots,n 掃描，維護掃描到 uu 之前，已保留下方端點的最大值：

Mu=max⁡1≤x<umax_v[x]M_u=\max_{1\le x<u}\mathrm{max\_v}[x]

此時只需要判斷 max_v[u]\mathrm{max\_v}[u] 與 MuM_u 的大小：

  • 若 max_v[u]=0\mathrm{max\_v}[u]=0，代表沒有上方端點為 uu 的弦，直接跳過。
  • 若 0<max_v[u]≤Mu0<\mathrm{max\_v}[u]\le M_u，則存在某個 x<ux<u 滿足 max_v[x]≥max_v[u]\mathrm{max\_v}[x]\ge \mathrm{max\_v}[u]，所以 (x,max_v[x])(x,\mathrm{max\_v}[x]) 支配 (u,max_v[u])(u,\mathrm{max\_v}[u])，不用保留。
  • 若 max_v[u]>Mu\mathrm{max\_v}[u]>M_u，則對所有 x<ux<u 都有 max_v[x]<max_v[u]\mathrm{max\_v}[x]<\mathrm{max\_v}[u]，前面沒有任何弦能支配 (u,max_v[u])(u,\mathrm{max\_v}[u])，因此保留 (u,max_v[u])(u,\mathrm{max\_v}[u])。

保留後更新前綴最大值：

Mu+1=max⁡(Mu,max_v[u])M_{u+1}=\max(M_u,\mathrm{max\_v}[u])

這和排序去重得到的結果相同，但不需要 O(mlog⁡m)\mathcal{O}(m\log m) 排序，時間降為 O(n+m)\mathcal{O}(n+m)。

分段刪除剩餘弦

令最後保留下來的 kk 條弦依序為

(u1,v1),(u2,v2),…,(uk,vk)(u_1,v_1),(u_2,v_2),\ldots,(u_k,v_k)

由保留條件 max_v[ui]>Mui\mathrm{max\_v}[u_i]>M_{u_i} 可知，對任意 1≤i<j≤k1\le i<j\le k，都有

ui<uj,vi<vju_i<u_j,\qquad v_i<v_j

也就是：

u1<u2<⋯<uk,v1<v2<⋯<vku_1<u_2<\cdots<u_k,\qquad v_1<v_2<\cdots<v_k

所以剩下的是一組沒有交叉、也不再互相支配的弦。

接下來只需要考慮這 kk 條弦。現在考慮一次切割刪掉其中一段連續弦，例如第 ll 到第 rr 條。

若要讓這段中的第一條弦被破壞，切割的上方下標必須小於 ulu_l；若要讓這段中的最後一條弦被破壞，切割的下方下標必須大於 vrv_r。由於中間弦的兩個座標都夾在這兩者之間，所以同一刀也會破壞整段。

因此，刪除一段連續弦的最小代價是：

cost⁡(l,r)=min⁡i<ul,  j>vraibj\operatorname{cost}(l,r)=\min_{i<u_l,\;j>v_r} a_i b_j

因為 aia_i 和 bjb_j 的選擇互不影響，可以拆成兩個最小值相乘：

cost⁡(l,r)=Cl⋅Dr\operatorname{cost}(l,r)=C_l\cdot D_r

其中：

Cl=min⁡1≤x<ulax,Dr=min⁡vr<x≤nbxC_l=\min_{1\le x<u_l} a_x,\qquad D_r=\min_{v_r<x\le n} b_x

這兩組值可以用前綴最小值與後綴最小值預處理。

為什麼一段一定是連續的？

剩餘弦的兩個座標都遞增。若一刀能同時破壞第 ll 條與第 rr 條，那麼介於它們之間的弦也會滿足同樣的切割條件，所以會被一起破壞。於是每次操作在剩餘序列上自然對應到刪除一段連續區間。

劃分型 DP

現在問題變成：有一串剩餘弦，每次可以刪除一段連續區間，刪除第 ll 到第 rr 條的代價是 ClDrC_lD_r，求刪完整串的最小代價。這就是典型的劃分型 DP：把前綴劃分成若干段，每一段對應一次切割操作。

定義 f[i]f[i] 表示刪掉前 ii 條保留弦的最小花費，初始值為 f[0]=0f[0]=0。

若最後一次操作刪掉的是第 j+1j+1 到第 ii 條，則前 jj 條弦已經用最小花費 f[j]f[j] 刪除，最後一段的代價是 cost⁡(j+1,i)\operatorname{cost}(j+1,i)，所以先得到一般轉移式：

f[i]=min⁡0≤j<i{f[j]+cost⁡(j+1,i)}=min⁡0≤j<i{f[j]+Cj+1Di}\begin{aligned} f[i] &=\min_{0\le j<i}\{f[j]+\operatorname{cost}(j+1,i)\}\\ &=\min_{0\le j<i}\{f[j]+C_{j+1}D_i\} \end{aligned}

直接枚舉最後一段起點是 O(k2)\mathcal{O}(k^2)，而 kk 最多接近 3×1053\times 10^5，需要繼續優化。

轉成內積最小值後進行斜率優化(Convex Hull Trick)

Convex Hull Trick 觀念引用

這一段會用到和 [[LeetCode/Hard/3826. Minimum Partition Score|LC 3826. Minimum Partition Score]] 相同的 CHT 觀念：把 DP 轉移中的枚舉項改寫成「一組候選點」與「一個查詢向量」的內積，之後只需要在凸包上找內積最小的點。

觀察轉移式：對固定右端點，要在所有歷史決策中最小化

f[j]+Cj+1Dif[j]+C_{j+1}D_i

這是一個「歷史值 + 兩項相乘」的形式，可以改寫成二維內積。

若把每個可作為區間左端點的決策看成一個候選點 vjv_j：

vj=(Cj+1,  f[j])v_j=\left(C_{j+1},\;f[j]\right)

把目前右端點看成查詢向量 pip_i：

pi=(Di,  1)p_i=\left(D_i,\;1\right)

那麼內積正好是：

pi⋅vj=Cj+1Di+f[j]p_i\cdot v_j=C_{j+1}D_i+f[j]

於是轉移變成在一組候選點中查詢最小內積，這就是凸包優化 DP。

不過若要用 Andrew 式維護下凸包，需要候選點的橫座標按遞增順序加入。隨著剩餘弦的上方端點遞增，可選的前綴最小值只會不增，所以 CC 是單調不增的。為了讓候選點橫座標變成單調不減，可以把第一維同時取相反數，改成定義：

vj=(−Cj+1,  f[j]),pi=(−Di,  1)v_j=\left(-C_{j+1},\;f[j]\right),\qquad p_i=\left(-D_i,\;1\right)

內積仍然相同：

pi⋅vj=(−Cj+1)(−Di)+f[j]=Cj+1Di+f[j]p_i\cdot v_j=(-C_{j+1})(-D_i)+f[j]=C_{j+1}D_i+f[j]

維護出下凸包後，對每個查詢向量 pip_i，可以在凸包上二分找到使內積最小的候選點，每次查詢花費 O(log⁡k)\mathcal{O}(\log k)。

進一步優化：單調隊列查詢

進一步看查詢向量的順序：剩餘弦的下方端點遞增，而後綴最小值在可選範圍縮小時只會不減，所以 DD 單調不減，−D-D 單調不增。

也就是說，查詢方向單調旋轉。在下凸包上，最優點只會沿著凸包往前移動，不會退回去。於是二分還可以再優化成單調隊列。若隊首點已經不如下一個點：

p⋅q0≥p⋅q1p\cdot q_0\ge p\cdot q_1

那麼之後它也不可能重新成為最優點，可以永久彈出，因此可以使用雙端佇列維護凸包，實現均攤 O(1)\mathcal{O}(1) 的單調隊列查詢。

小結

本題的完整鏈條是：先用二維支配關係刪掉冗餘弦，把問題壓成雙座標遞增序列；再把一次切割看成刪除一段連續區間；最後將分段 DP 的乘積代價改寫成內積最小值，用下凸包與單調隊列做到線性轉移。

複雜度分析

  • 令 kk 為刪掉被支配弦後，最後保留下來的弦數量，顯然 k≤mk\le m。
  • 時間複雜度：
    • 排序去重 + 二分查詢：O(mlog⁡m+klog⁡k+n)\mathcal{O}(m\log m+k\log k+n)。排序去重花費 O(mlog⁡m)\mathcal{O}(m\log m)，每次在凸包上二分查詢花費 O(log⁡k)\mathcal{O}(\log k)。
    • 值域去重 + 單調隊列：O(n+m)\mathcal{O}(n+m)。值域去重花費 O(n+m)\mathcal{O}(n+m)，凸包中每個候選點最多加入與彈出一次。
  • 空間複雜度：O(n+m)\mathcal{O}(n+m)。主要來自每個上方端點的最大下方端點、壓縮後弦序列、DP 陣列與凸包。

Code

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
"""
若選擇切割點 (i, j)，所有滿足 u > i 且 v < j 的弦 (u, v) 都會被消除。
反過來看，若要消除弦 (u, v)，切割點必須滿足 i < u 且 j > v。

因此，消除弦 (u, v) 時，所有滿足 u' >= u 且 v' <= v 的弦 (u', v') 也會被同時消除。
稱這些能被其他弦順帶消除的弦為「被支配」的弦。

對於相同上方端點 u 的所有弦，只需要保留最大的 max_v[u]。
接著按 u 遞增掃描，只保留下方端點能刷新前綴最大值的弦。
最後得到一組保留弦 (u_1, v_1), (u_2, v_2), ..., (u_k, v_k)，滿足
u_1 < u_2 < ... < u_k 且 v_1 < v_2 < ... < v_k。

刪除第 l 到第 r 條保留弦時，需要選擇 i < u_l 且 j > v_r，
所以 cost(l, r) = min_{i < u_l, j > v_r} A[i] * B[j]。
預處理 C[l] = min_{1 <= x < u_l} A[x]，D[r] = min_{v_r < x <= n} B[x]，
則 cost(l, r) = C[l] * D[r]。

令 f[i] 表示刪掉前 i 條保留弦的最小成本，則
f[i] = min_{0 <= j < i} f[j] + cost(j + 1, i)
    = min_{0 <= j < i} f[j] + C[j + 1] * D[i]

把每個決策 j 看成候選點 v_j = (C[j + 1], f[j])，目前右端點 i 看成查詢向量 p_i = (D[i], 1)，
則要查詢 min(p_i · v_j)。

由於 C[j + 1] 單調不增，為了用 Andrew 式維護下凸包，對第一維同時取反：
v_j = (-C[j + 1], f[j])，p_i = (-D[i], 1)。
內積不變，仍是 C[j + 1] * D[i] + f[j]。

可以用 query_bisect() 在下凸包上二分查詢；又因為 p_i 的 x 值單調不增，
最佳點索引單調往前移動，也可以用 query_mono() 做單調隊列查詢。
"""

from itertools import accumulate
from math import inf
from collections import deque


class Vec:
    __slots__ = "x", "y"

    def __init__(self, x: int, y: int):
        self.x = x
        self.y = y

    def __add__(self, b: "Vec") -> "Vec":
        return Vec(self.x + b.x, self.y + b.y)

    def __sub__(self, b: "Vec") -> "Vec":
        return Vec(self.x - b.x, self.y - b.y)

    def det(self, b: "Vec") -> int:
        return self.x * b.y - self.y * b.x

    def dot(self, b: "Vec") -> int:
        return self.x * b.x + self.y * b.y


class ConvexHull:
    """
    注意：
  - add() 的點需要依 x 遞增加入。
  - query_bisect() 不要求查詢向量單調，使用二分搜尋。
  - query_mono() 使用單調隊列優化，因此查詢向量 p 需要滿足最佳點索引單調往前移動。
    """

    def __init__(self):
        self.hull = deque()

    def add(self, v: Vec) -> None:
        hull = self.hull

        # 如果新點與最後一個點 x 相同，只保留對應 mode 下較優的 y
        if hull and hull[-1].x == v.x:
            if hull[-1].y <= v.y:
                return
            hull.pop()

        # 維護凸包性質，移除不可能成為凸包的中間點
        while len(hull) >= 2 and (hull[-1] - hull[-2]).det(v - hull[-1]) <= 0:
            hull.pop()

        hull.append(v)

    def query_bisect(self, p: Vec) -> int:
        hull = self.hull

        # 使用二分搜尋找到最佳點
        left, right = 0, len(hull) - 2
        while left <= right:
            mid = (left + right) // 2
            curr = p.dot(hull[mid])
            nxxt = p.dot(hull[mid + 1])
            if curr >= nxxt:
                left = mid + 1
            else:
                right = mid - 1

        return p.dot(hull[left])

    def query_mono(self, p: Vec) -> int:
        hull = self.hull

        # 使用單調隊列維護
        while len(hull) >= 2 and p.dot(hull[0]) >= p.dot(hull[1]):
            hull.popleft()
        return p.dot(hull[0])


def solve() -> None:
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    # 排序去重： O(m log m)
    chords = [tuple(map(int, input().split())) for _ in range(m)]
    chords.sort(key=lambda x: (x[0], -x[1]))
    records = []
    curr_v = 0
    for u, v in chords:
        if v > curr_v:
            curr_v = v
            records.append((u, curr_v))

    # 基於值域的去重： O(n + m)
    # max_v = [0] * (n + 1)
    # for _ in range(m):
    #     u, v = map(int, input().split())
    #     max_v[u] = max(max_v[u], v)

    # records = []
    # curr_v = 0
    # for u in range(1, n + 1):
    #     if max_v[u] > curr_v:
    #         curr_v = max_v[u]
    #         records.append((u, curr_v))

    k = len(records)

    pre_min = list(accumulate(A, func=min, initial=inf))
    suf_min = list(accumulate(B[::-1], func=min))[::-1]

    C = [0] * (k + 1)
    D = [0] * (k + 1)
    for idx, (u, v) in enumerate(records, start=1):
        C[idx] = pre_min[u - 1]
        D[idx] = suf_min[v]

    f = [0] * (k + 1)
    cht = ConvexHull()
    for i in range(1, k + 1):
        j = i - 1
        vj = Vec(-C[j + 1], f[j])  # 取反確保候選點 x 遞增
        cht.add(vj)

        p = Vec(-D[i], 1)
        # f[i] = cht.query_bisect(p)
        f[i] = cht.query_mono(p)

    print(f[k])


if __name__ == "__main__":
    solve()