题解—God Knows

考场上以为就是转化成一个无向图然后以为无向图有什么性质可以搞出来来着。

果然应验了那句话，一个思路想太久想不出来一般是假的。

所以这种一看就需要转化的题要多尝试能往哪转化，而不是按住一个思路不动。

只要转化成求极长上升序列就能搞一个单调栈的暴力分。

神仙题一个，第二次见这么玩线段树的(\(minimax\)是第一个)

这种题果然是我这种弱鸡不配做的，考完磨了超级神犇土哥半天才搞明白。

首先第一步转化，就是把问题变成求\(p[i]\)序列里面的一个最小权极长上升子序列。

因为满足极长上升，所以一定是把所以跟他没有交集的线都选了，导致没选的都是跟他有交集的，那肯定都被消掉了。

求这个东西，可以发现如果我们设计状态\(f[i]\)表示选择\(i\)时的上升子序列，那么对于每个\(i\)，他的转移点一定是随着\(i\)增单调减的。

所以大佬\(zero4338\)直接维护了一下转移点，然后直接跳转移点，并通过了本题。

但是发现如果一个数前面的东西都是单调减的，那么转移点会有很多，导致直接跳会超时。

所以这个东西，我们其实是想动态的维护一个单调栈。

因为对于每个\(i\)，都需要找出若干个\(p[j]\)单调递减的\(j\)并且满足\(\forall p[j]<p[i]\)。

但是发现每个\(p[i]\)都不同，弄单调栈需要每次都重新扫一遍。

所以出现了本场主角——线段树维护单调栈。

\(\%\%\%\)学长写的\(blog\)，写的很清楚，放个链接

这个东西就是通过递归定义让\(calc\)函数和我们存的一个值不断套娃得到的解。

在原来那道题（楼房修建）中，我们开了一个额外的域，\(len\)。

保存\(x\)节点的右区间中大于左区间最大值并且单调上升的长度。

这是由于题目要求，如果一个楼房对应的斜率比较高，我们不能选择不看到它，因为我们不能透视不看他看到被他挡住的。

这句话看似很废，却是可以用这个方法解题的关键。

因为左边会对右边造成影响，所以我们需要把关键信息给被造成影响的区间，也就是右区间。

正是因为这个，所以我们在把\(len\)定义上上面那样，这样才能合并区间信息。

所以，在这道题中，我们需要动态维护比一个数小的单调递减（从1开始）的序列中\(dp\)值的最小值

其实如果我们从\(i\)开始来看他的话，他就是一个单调递增的序列。

和上面那道题一样，为了设计出来那个额外域的意义，需要观察题目的性质。

其实就是如果下标大的数值大，我们必须选择他。

画一个图来表示一下就是这样的。

假如下面小于\(p[i]\)是左区间和右区间的单调部分

我们需要选择

而不是

反正就是从\(i\)往\(1\)走的过程中只要比当前栈顶的\(p[i]\)大就必须入到栈中。

所以说，我们需要把状态设计成左区间的信息，因为右边会对左边造成影响。

结合题目要求，我们额外域里面存的就是

这个区间的左区间中大于右区间最大值并且满足单调递减的部分的\(dp\)值的最小值

\(calc\)为了和他套娃，需要计算

一个区间所有数都大于\(val\)并且满足单调递减的\(dp\)值的最小值

所以很好写出\(pushup\)和\(calc\)

int calc( int x , int val ){ // x的节点的区间中满足单调递减大于val的值数中的dp值的最小值

	if( l [x] == r [x] ){

		if( data [x].maxv > val ) return f [rl [l [x]]]; //f [rl [l [x]]]的意思就是这个位置的dp值

		else return Inf ; //不满足大于val,return inf

	}

	if( data [x << 1 | 1].maxv > val ) return min( data [x].ans , calc( x << 1 | 1 , val ) ) ;

	// 右区间最大值大于val，去递归右区间并且直接加上左区间之前计算好的贡献

	else return calc( x << 1 , val ) ;

	//否则直接去左区间找就行了，因为右区间最大值都不合法。

}

inline void ud( int x ){ //push_up

	data [x].maxv = max( data [x << 1].maxv , data [x << 1 | 1].maxv ) ;

	data [x].ans = calc( x << 1 , data [x << 1 | 1].maxv ) ; //套娃从这里开始

}

然后发现还有一个问题，如果我们线段树中保存下标的是\(i\)的话，我们每次都需要满足找到的东西小于\(p[i]\)这个要求。

很难实现。

所以把下标设置成\(p[i]\)，所以只用让\(i\)满足单调递减就行了，又因为我们是从\(1\)到\(i\)加进来的，所以大于\(i\)的线段树中肯定没有。

这样就解决了\(p[i]\)的限制，也是一步很神仙的转化（本弱想不到系列）。

然后\(ask\)的时候直接找从\(1\)到\(p[i]\)就行了，但是由于我们需要把线段树上的区间拼接起来，所以需要先去右边，再搜左边。

记录一下右边搜到的最大值，层层加限制就行了。

然后就可以\(logn\)计算出来\(f[i]\)了，最后直接找一下看哪个点可以做极长上升序列的结尾点，并统计他对\(ans\)的贡献就行了。

code

#include <cstdio>

#include <algorithm>

#include <cstring>

#define R register int

#define int long

#define printf Ruusupuu = printf

#define scanf Ruusupuu = scanf

#define freopen rsp_5u = freopen

int Ruusupuu ;

FILE * rsp_5u ;

using namespace std ;

typedef long long L ;

typedef long double D ;

typedef pair<int , int> PI ;

const int N = 2e5 + 10 ;

const int Inf = 0x3f3f3f3f ;

inline void of(){ freopen( "in.in" , "r" , stdin ) , freopen( "out.out" , "w" , stdout ) ; }

inline void cf(){ fclose( stdin ) , fclose( stdout ) ; }

inline int read(){

	int w = 0 ; bool fg = 0 ; char ch = getchar() ;

	while( ch < '0' || ch > '9' ) fg |= ( ch == '-' ) , ch = getchar() ;

	while( ch >= '0' && ch <= '9' ) w = ( w << 1 ) + ( w << 3 ) + ( ch - '0' ) , ch = getchar() ;

	return fg ? -w : w ;

}

bool fg [N] ;

int n , m , rl [N] ;

int p [N] , w [N] , f [N] ;

int l [N << 2] , r [N << 2] , lx , rx , pos , dlt ;

struct T{ int maxv , ans ; } data [N << 2] ;

//data [x].ans 保存，x的左边区间 大于 x的右边区间的最大值的 并且单调递减 的部分内 dp值的最小值

int calc( int x , int val ){ // x的节点的区间中满足单调递减大于val的值数中的dp值的最小值

	if( l [x] == r [x] ){

		if( data [x].maxv > val ) return f [rl [l [x]]];

		else return Inf ;

	}

	if( data [x << 1 | 1].maxv > val ) return min( data [x].ans , calc( x << 1 | 1 , val ) ) ;

	else return calc( x << 1 , val ) ;

}

inline void ud( int x ){

	data [x].maxv = max( data [x << 1].maxv , data [x << 1 | 1].maxv ) ;

	data [x].ans = calc( x << 1 , data [x << 1 | 1].maxv ) ;

}

void build( int x , int ll , int rr ){

	l [x] = ll , r [x] = rr ;

	data [x].ans = Inf , data [x].maxv = -Inf ;

	if( ll == rr ) return ;

	int mid = ( ll + rr ) >> 1 ;

	build( x << 1 , ll , mid ) ;

	build( x << 1 | 1 , mid + 1 , rr ) ;

	ud( x ) ;

}

int nowmax ;

int ask( int x ){

	if( l [x] >= lx && r [x] <= rx ){

		int t = calc( x , nowmax ) ;

		nowmax = max( nowmax , data [x].maxv ) ; //更新nowmax，为了满足单调性，接下来搜到的单调序列里面的数不能小于nowmax

		return t ;

	}

	int mid = ( l [x] + r [x] ) >> 1 , ans = 0x3f3f3f3f ;

	if( rx > mid ) ans = min( ans , ask( x << 1 | 1 ) ) ;

	if( lx <= mid ) ans = min( ans , ask( x << 1 ) ) ;

	return ans ;

}

void cge( int x ){

	if( l [x] == r [x] ){ data [x].maxv = rl [l [x]] ; return ; }

	int mid = ( l [x] + r [x] ) >> 1 ;

	if( pos <= mid ) cge( x << 1 ) ;

	else cge( x << 1 | 1 ) ;

	ud( x ) ;

}

inline int Ask( int x ){

	lx = 1 , rx = p [x] , nowmax = 0 ;

	int t = ask( 1 ) ;

	return ( ( t == Inf ) ? 0 : t ) ;

}

void sc(){

	n = read() ;

	for( R i = 1 ; i <= n ; i ++ ) p [i] = read() , rl [p [i]] = i ;

	for( R i = 1 ; i <= n ; i ++ ) w [i] = read() ;

	memset( f , 0x3f , sizeof( f ) ) ;

	build( 1 , 1 , n ) ;

}

void work(){

	int maxn = 0 , ansn = 0x3f3f3f3f ;

	for( R i = n ; i >= 1 ; i -- )

		if( p [i] > maxn ) maxn = p [i] , fg [i] = 1 ;

	for( R i = 1 ; i <= n ; i ++ ){

		f [i] = Ask( i ) + w [i] , pos = p [i] , dlt = f [i] , cge( 1 ) ;

		if( fg [i] ) ansn = min( ansn , f [i] ) ;

	}

	printf( "%ld\n" , ansn ) ;

}

signed main(){

//	of() ;

	sc() ;

	work() ;

//	cf() ;

	return 0 ;

}

巴特西

题解—God Knows

最新文章

热门文章