n < = 2 e 5 n<=2e5 n<=2e5
设 f i f_i fi为删除 ( i , p i ) (i,p_i) (i,pi)的线段并使得不存在线段 ( a , b ) , a < i , b < p i (a,b),a<i,b<p_i (a,b),a<i,b<pi的最少花费。 那么容易发现可以转移到 f i f_i fi的 f j f_j fj一定满足 p j p_j pj是 k = i − 1 , i − 2.... j k=i-1,i-2....j k=i−1,i−2....j中最大的满足 p k < p i p_k<p_i pk<pi的 p k p_k pk。 也就是说在 k = i − 1 , i − 2....1 k=i-1,i-2....1 k=i−1,i−2....1且满足 p k < p i p_k<p_i pk<pi这个序列中 j j j是前缀最大值。 那么我们的问题就转化为了求前缀最大值的所有位置 j j j上的 f j f_j fj的最小值。 那么先从 i = 1 , 2.... n i=1,2....n i=1,2....n的顺序插入 ( i , p i ) (i,p_i) (i,pi)，用一个李超线段树维护 p k < p i p_k<p_i pk<pi的 k k k所形成的序列的前缀最大值的位置上的 f f f的最小值。 解法类似于楼房重建
A C C o d e \rm AC\ Code AC Code
#include<bits/stdc++.h> #define maxn 200005 #define inf 0x7f7f7f7f #define lc u<<1 #define rc u<<1|1 using namespace std; int n,p[maxn],c[maxn],f[maxn]; struct data{ int a,c; data(int a=0,int c=inf):a(a),c(c){} data operator +(const data &B)const{ return B.a<=0?*this:data(B.a,min(B.c,c)); } }s[maxn<<2],sl[maxn<<2]; data cal(int u,int l,int r,int h){ if(l==r) return s[u].a>h?s[u]:data(); int mid = (l+r) >> 1; if(s[rc].a>h) return cal(rc,mid+1,r,h)+sl[u]; return cal(lc,l,mid,h); } void upd(int u,int l,int r){ s[u] = s[rc] + (sl[u] = cal(lc,l,(l+r)>>1,s[rc].a)); } void Insert(int u,int l,int r,int p,data v){ if(l==r){ s[u]=v;return; } int mid = (l+r) >> 1; if(p <= mid) Insert(lc,l,mid,p,v); else Insert(rc,mid+1,r,p,v); upd(u,l,r); } data d; void Query(int u,int l,int r,int ql,int qr){ if(ql>qr) return; if(ql<=l&&r<=qr){ d=d+cal(u,l,r,d.a); return;} int mid = (l+r) >> 1; if(qr>mid) Query(rc,mid+1,r,max(ql,mid+1),qr); if(ql<=mid) Query(lc,l,mid,ql,min(mid,qr)); } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&p[i]); for(int i=1;i<=n;i++) scanf("%d",&c[i]),f[i]=inf; f[1]=c[1],Insert(1,1,n,p[1],data(1,f[1])); for(int i=2;i<=n;i++){ d=data();Query(1,1,n,1,p[i]-1); int t = d.c;if(t >= inf) t = 0; Insert(1,1,n,p[i],data(i,f[i]=min(f[i],t+c[i]))); } d=data();Query(1,1,n,1,n); printf("%d\n",d.c); }考场上写的 C D Q \rm CDQ CDQ分治+ z k w \rm zkw zkw线段树。 主要就是按第一维分治求左半对右半的贡献， 按第二维 p p p从小到大枚举，左半能贡献的只有 p i < = p_i<= pi<=当前枚举的 p p p的所有 i i i中的后缀最大值，用线段树维护给右边，右边每一个点能接受的区间要看他前一个前缀最大值，故左右都需要用单调栈维护。
A C C o d e \rm AC \ Code AC Code
#include<bits/stdc++.h> #define maxn 200005 #define inf 0x7f7f7f7f #define lc u<<1 #define rc u<<1|1 using namespace std; int n,p[maxn],c[maxn],f[maxn]; struct data{ int a,c; data(int a=0,int c=inf):a(a),c(c){} data operator +(const data &B)const{ return B.a<=0?*this:data(B.a,min(B.c,c)); } }s[maxn<<2],sl[maxn<<2]; data cal(int u,int l,int r,int h){ if(l==r) return s[u].a>h?s[u]:data(); int mid = (l+r) >> 1; if(s[rc].a>h) return cal(rc,mid+1,r,h)+sl[u]; return cal(lc,l,mid,h); } void upd(int u,int l,int r){ s[u] = s[rc] + (sl[u] = cal(lc,l,(l+r)>>1,s[rc].a)); } void Insert(int u,int l,int r,int p,data v){ if(l==r){ s[u]=v;return; } int mid = (l+r) >> 1; if(p <= mid) Insert(lc,l,mid,p,v); else Insert(rc,mid+1,r,p,v); upd(u,l,r); } data d; void Query(int u,int l,int r,int ql,int qr){ if(ql>qr) return; if(ql<=l&&r<=qr){ d=d+cal(u,l,r,d.a); return;} int mid = (l+r) >> 1; if(qr>mid) Query(rc,mid+1,r,max(ql,mid+1),qr); if(ql<=mid) Query(lc,l,mid,ql,min(mid,qr)); } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&p[i]); for(int i=1;i<=n;i++) scanf("%d",&c[i]),f[i]=inf; f[1]=c[1],Insert(1,1,n,p[1],data(1,f[1])); for(int i=2;i<=n;i++){ d=data();Query(1,1,n,1,p[i]-1); int t = d.c;if(t >= inf) t = 0; Insert(1,1,n,p[i],data(i,f[i]=min(f[i],t+c[i]))); } d=data();Query(1,1,n,1,n); printf("%d\n",d.c); }