# Description
Luogu 传送门
# Solution
斜率优化 dp
非常好的一道斜率优化，完全理解题目都用了好长时间 QwQ
其实如果你已经完全理解了这道题也不是特别难了。
我们可以选两个下标，然后把经过这两个下标的线全部删掉。
不难发现，交叉的线是没有用的，所以对于上方的一个点，我们只保留它与下方连边中最右边的点即可。
然后这张图就变成了好多不相交的线，这样就可以列出朴素 了。
设 表示把前 条弦全部切掉的最小花费，那么有转移方程：
分别是 的前缀最小值，和 的后缀最小值。
然后这就已经是一个斜率优化可以做的式子了。
注意：标准的斜率优化式子为 ，而这里是加法，所以求斜率时要取反。
# Code
#include <bits/stdc++.h> | |
#define int long long | |
using namespace std; | |
namespace IO{ | |
inline int read(){ | |
int x = 0; | |
char ch = getchar(); | |
while(!isdigit(ch)) ch = getchar(); | |
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); | |
return x; | |
} | |
template <typename T> inline void write(T x){ | |
if(x > 9) write(x / 10); | |
putchar(x % 10 + '0'); | |
} | |
} | |
using namespace IO; | |
const int N = 3e5 + 10; | |
const int INF = 2e18; | |
int n, m; | |
struct node{ | |
int l, r; | |
inline bool operator < (const node &b) const{ | |
return l != b.l ? l < b.l : r > b.r; | |
} | |
}p[N]; | |
int a[N], b[N], ml[N], mr[N]; | |
int u[N], v[N], tot; | |
int f[N], q[N]; | |
inline double X(int i) {return 1.0 * ml[u[i + 1] - 1];} | |
inline double Y(int i) {return 1.0 * f[i];} | |
inline double K(int i) {return 1.0 * mr[v[i] + 1];} | |
inline double slope(int i, int j) {return (X(i) == X(j)) ? INF : 1.0 * (Y(i) - Y(j)) / (X(j) - X(i));} | |
signed main(){ | |
// freopen("P6047.in", "r", stdin); | |
n = read(), m = read(); | |
for(int i = 1; i <= n; ++i) a[i] = read(); | |
for(int i = 1; i <= n; ++i) b[i] = read(); | |
for(int i = 1; i <= m; ++i) p[i] = (node){read(), read()}; | |
sort(p + 1, p + 1 + m); | |
int mx = 0; | |
for(int i = 1; i <= m; ++i){ | |
if(p[i].r > mx) u[++tot] = p[i].l, v[tot] = p[i].r; | |
mx = max(mx, p[i].r); | |
} | |
m = tot; | |
ml[0] = mr[n + 1] = INF; | |
for(int i = 1; i <= n; ++i) ml[i] = min(ml[i - 1], a[i]); | |
for(int i = n; i >= 0; --i) mr[i] = min(mr[i + 1], b[i]); | |
int head = 1, tail = 1; | |
for(int i = 1; i <= m; ++i){ | |
while(head < tail && slope(q[head], q[head + 1]) < K(i)) head++; | |
int j = q[head]; | |
f[i] = f[j] + K(i) * X(j); | |
while(head < tail && slope(q[tail], q[tail - 1]) > slope(q[tail], i)) tail--; | |
q[++tail] = i; | |
} | |
write(f[m]), puts(""); | |
return 0; | |
} | |
// X.K. |
