20210715

God Knows

code
const int N = 2e5+5, inf = 0x3f3f3f3f;
int n,p[N];

int res,now; // now: 当前的j(要求递增) 
struct Node {
	int l,r,ri,lmn,f;
	// ri: 最大的i;
	// lmn: 预处理(否则查询会变成n\logn) 
} t[N*4];

#define ls (u<<1)
#define rs (u<<1|1)
void build(int u,int l,int r) {
	t[u].l = l, t[u].r = r, t[u].lmn = inf;
	if( l == r ) return;
	int mid = l+r>>1;
	build(ls,l,mid), build(rs,mid+1,r);
}
int calc(int u,int qr) { // t[u].l<=p[j]<=t[u].r,j>qr的min{f[j]} 
	if( t[u].l == t[u].r ) return t[u].ri > qr ? t[u].f : inf;
	if( t[rs].ri >= qr ) return min(t[u].lmn,calc(rs,qr));
	return calc(ls,qr);
}
void insert(int u,int x,int y,int z) { // (p[i]=x,i=y),f[i]=z
	if( t[u].l == t[u].r ) { t[u].ri = y, t[u].f = z; return; }
	if( x <= t[ls].r ) insert(ls,x,y,z);
	else insert(rs,x,y,z);
	t[u].ri = max(t[ls].ri,t[rs].ri), t[u].lmn = calc(ls,t[rs].ri);
}
void query(int u,int x) {
	if( t[u].r <= x ) {
		res = min(res,calc(u,now)), now = max(now,t[u].ri);
		return;
	}
	if( t[rs].l <= x ) query(rs,x);
	query(ls,x);
}

signed main() {
	read(n);
	For(i,1,n) read(p[i]);
	build(1,1,n);
	For(i,1,n) {
		int c; read(c);
		res = inf, now = 0, query(1,p[i]);
		insert(1,p[i],i,(res==inf?0:res)+c);
	}
	res = inf, now = 0, query(1,n);
	printf("%d",res);
	return ioclear();
}
上一篇:MVC二维码条形码


下一篇:P4074 [WC2013]糖果公园