模拟赛G题题解 - 洛谷保存站

## 题意
给一个数组$a_1,a_2,\cdots,a_n$, 你希望固定尽量少的元素, 满足对于剩下未固定的元素$a_x$, 它左右都有固定的元素。令$a_l,a_r$是左右两边最靠近它的固定的元素, 能满足 $a_l\le a_x\le a_r$或$a_l\ge a_x\ge a_r$。

输出最少的固定元素的个数。

**保证a数组两两不同**，$0\le n\le 10^5$
## 题解
容易发现必须固定$a_1$到$a_n$最小值和最大值，怎么证明？

设最小值为$a_k$，若$a_k$未固定，令$a_l$，$a_r$是左右两边最靠近它的固定的元素\
则$a_l>a_k<a_r$，与题意不符\
$\therefore a_k$必须固定\
同理最大值也必须固定

考虑另一种情况。当$a_l,a_{l+1},\cdots,a_n$未固定，$a_{l-1}$固定且$a_{l-1}<min(a_l,a_{l+1},\cdots,a_n)$时，\
对$[l-1,n]$使用刚才的结论得$[l,n]$中最大值必须固定\
对$[1,r]$同理，对固定最大值同理

考虑递归。设$solve(l,r,L,R)$中$[l,r]$表示当前区间，\
$L=0,1,2$分别代表区间左端没有数，有区间$[l-1,r]$最大值，有区间$[l-1,r]$最小值，\
$R=0,1,2$分别代表区间右端没有数，有区间$[l,r+1]$最大值，有区间$[l,r+1]$最小值\
由刚才的结论，$solve$函数是封闭的

线段树维护即可，时间复杂度$O(nlogn)$

代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,a[100005],tree[800005],tree2[800005];
void build(int p,int pl,int pr){
	if(pl==pr){
		tree[p]=tree2[p]=a[pl];
		return;
	}
	int mid=(pl+pr)>>1;
	build(p*2,pl,mid);
	build(p*2+1,mid+1,pr);
	tree[p]=max(tree[p*2],tree[p*2+1]);
	tree2[p]=min(tree2[p*2],tree2[p*2+1]);
	return;
}//建树
int query(int p,int pl,int pr,int l,int r){
	if(pl>=l&&pr<=r)return tree[p];
	if(pl>r||pr<l)return 0;
	int mid=(pl+pr)>>1;
	return max(query(p*2,pl,mid,l,r),query(p*2+1,mid+1,pr,l,r));
}//求最大值
int query2(int p,int pl,int pr,int l,int r){
	if(pl>=l&&pr<=r)return tree2[p];
	if(pl>r||pr<l)return 0x3f3f3f3f;
	int mid=(pl+pr)>>1;
	return min(query2(p*2,pl,mid,l,r),query2(p*2+1,mid+1,pr,l,r));
}//求最小值
map<int,int>mp;//求一个数的位置
int solve(int l,int r,int L,int R){
	if(L==3-R)return 0;
	if(l>r)return 0;
	if(l==r)return 1;
	int x=mp[query(1,1,n,l,r)],y=mp[query2(1,1,n,l,r)];
	if(L)return 1+solve((L==1?x:y)+1,r,3-L,0);
	if(R)return 1+solve(l,(R==1?x:y)-1,0,3-R);
	if(x<y)return 2+solve(l,x-1,0,2)+solve(y+1,r,1,0);
	return 2+solve(l,y-1,0,1)+solve(x+1,r,2,0);
}
int main(){
	freopen("seq.in","r",stdin);
	freopen("seq.out","w",stdout);
	cin>>n;
	if(n==0){
		cout<<0;
		return 0;
	}//特判，不然build会炸
	for(int i=1;i<=n;i++)cin>>a[i],mp[a[i]]=i;
	build(1,1,n);
	cout<<solve(1,n,0,0);
	return 0;
}
```

正在渲染内容...