分析

真的是好题。我们考虑并不是所有线段都是有用的，如果有两条线段相交，那么其实我们只需要切断第一个 就行了。所以我们可以形式化的表达当 则 时，这才是个合法图。而我们就是要求这个图转换为合法图之后的最小答案。我们考虑线性 。令 以 结尾的最小代价。那么我们的转移为 。我们发现其实后面的是一堆常数。那么这又是一个满足 的形式了。所以我们考虑李超线段树来维护这个凸壳。

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL read() {
    LL x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f=1;ch=getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch=getchar();}
    return f?-x:x;
}
const LL N = 5e5 + 100,inf = 0x3f3f3f3f3f3f3f3f,M = 1e6+10;
struct Node{LL u,v;}e[N],p[N];
bool cmp(Node a,Node b) {return a.u < b.u;}
LL n,m,A[N],B[N],U[N],D[N],f[N],K[N];
LL clac(LL id,LL pos) {return K[id] * pos + f[id];}
LL top2;
LL lc[N],rc[N],size,t[N],rt;
void insert(LL &u,LL l,LL r,LL id) {
    if(!u) u = ++size;
    if(!t[u]) {t[u] = id;return;}
    LL mid = l + r >> 1;
    LL val_L = clac(id,l),val_R = clac(id,r),val_l = clac(t[u],l),val_r = clac(t[u],r);
    if(val_L <= val_l && val_R <= val_r) {t[u] = id;return;}
    if(val_l <= val_L && val_r <= val_R) {return;}
    insert(lc[u],l,mid,id);insert(rc[u],mid+1,r,id);
}
LL query(LL u,LL l,LL r,LL pos) {
    if(!u || !t[u]) return inf;
    LL ans = clac(t[u],pos);
    LL mid = l + r >> 1;
    if(pos <= mid) return min(ans,query(lc[u],l,mid,pos));
    else return min(ans,query(rc[u],mid+1,r,pos));
}
int main() {
    n = read();m = read();
    for(LL i = 1;i <= n;i++) U[i] = read();
    for(LL i = 1;i <= n;i++) D[i] = read();
    memset(A,0x3f,sizeof(A));memset(B,0x3f,sizeof(B));
    A[1]=U[1];for(LL i = 1;i <= n;i++) A[i] = min(A[i-1],U[i]);
    B[n]=D[n];for(LL i = n;i >= 1;i--) B[i] = min(B[i+1],D[i]);
    for(LL i = 1;i <= m;i++) {e[i].u = read();e[i].v = read();}
    sort(e+1,e+1+m,cmp);
    LL mx = 0;
    for(LL i = 1;i <= m;i++) {
        if(e[i].v > mx) {
            p[++top2] = e[i];
            mx = e[i].v;
        }
    }
    K[top2 + 1] = A[p[1].u-1];f[top2 + 1] = 0;
    insert(rt,1,M,top2+1);
    for(LL i = 1;i <= top2;i++) {
        f[i] = query(rt,1,M,B[p[i].v+1]);
        K[i] = A[p[i + 1].u - 1];
        insert(rt,1,M,i);
    }
    cout << f[top2] << endl;
}