题面

CODE

稍微分析一下，发现把(i,pi)(i,p_i)(i,pi)看做二维数点，就是求极长上升子序列的权值最小值。

直接李超线段树

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200005;

const int INF = 0x3f3f3f3f;

int n, v, mxr, p[MAXN];

int mx[MAXN<<2], vl[MAXN<<2], val[MAXN<<2];

int cal(int i, int l, int r, int R) {

	if(l == r) return mx[i] > R ? val[i] : INF;

	int mid = (l + r) >> 1;

	if(mx[i<<1|1] >= R) return min(vl[i], cal(i<<1|1, mid+1, r, R));

	else return cal(i<<1, l, mid, R);

}

void insert(int i, int l, int r, int x, int pos, int V) {

	if(l == r) { mx[i] = pos; val[i] = V; return; }

	int mid = (l + r) >> 1;

	if(x <= mid) insert(i<<1, l, mid, x, pos, V);

	else insert(i<<1|1, mid+1, r, x, pos, V);

	mx[i] = max(mx[i<<1], mx[i<<1|1]);

	vl[i] = cal(i<<1, l, mid, mx[i<<1|1]);

}

void query(int i, int l, int r, int x) {

	if(r <= x) { v = min(v, cal(i, l, r, mxr)); mxr = max(mxr, mx[i]); return; }

	int mid = (l + r) >> 1;

	if(x > mid) query(i<<1|1, mid+1, r, x);

	query(i<<1, l, mid, x);

}

int main () {

	scanf("%d", &n);

	for(int i = 1; i <= n; ++i) scanf("%d", &p[i]);

	memset(vl, 0x3f, sizeof vl);

	for(int i = 1, c; i <= n; ++i) {

		scanf("%d", &c);

		v = INF, mxr = 0, query(1, 1, n, p[i]);

		insert(1, 1, n, p[i], i, (v == INF ? 0 : v) + c);

	}

	v = INF, mxr = 0, query(1, 1, n, n);

	printf("%d\n", v);

}

巴特西

【CSP模拟赛】God knows （李超线段树）

题面

CODE

最新文章

热门文章